排序

重新排列数组中的元素，使它们按照某一定义的顺序排列。

选择排序

选择排序遍历数组中每个元素的位置，查找在排序后的数组中应该占据该位置的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void SortIntegerArray(int array[], int n){
    int lh, rh, i, temp;
    for(lh=0; lh<n; lh++){
        rh = lh;
        for(i=lh+1; i<n; i++){
            if(array[rh] > array[i]){
                rh = i;
            }
        }
        if(rh != lh){
            temp = array[lh];
            array[lh] = array[rh];
            array[rh] = temp;
        }
    }
}

合并排序

合并排序的基本思想如下：

检查数组是否为空或是否只有一个元素。如果是，那么它一定是已排序的，函数不用做任何工作即可返回。这是递归的最简单情景；
把数组分解为两个子数组，每个新数组都是原数组长度的一半；
递归的为这两个数组排序；
把两个数组合并为一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void SortIntegerArray(int array[], int n){
    int n1, n2, *subarr1, *subarr2;
    if(n <= 1){
        return;
    }
    n1 = n / 2;
    n2 = n - n1;
    subarr1 = CopySubArray(array, 0, n1);
    subarr2 = CopySubArray(array, n1, n2);
    SortIntegerArray(subarr1, n1);
    SortIntegerArray(subarr2, n2);
    Merge(array, subarr1, n1, subarr2, n2);
    free(subarr1);
    free(subarr2);
}

static void Merge(int array[], int subarr1[], int n1, int subarr2[], int n2){
    int p, p1, p2;
    p = p1 = p2 = 0;
    while(p1<n1 && p2<n2){
        if(subarr1[p1] < subarr2[p2]){
            array[p++] = subarr1[p1++];
        }
        else{
            array[p++] = subarr2[p2++];
        }
    }
    while(p1 < n1){
        array[p++] = subarr1[p1++];
    }
    while(p2 < n2){
        array[p++] = subarr2[p2++];
    }
}

static int * CopySubArray(int array[], int start, int n){
    int i, *result;
    result = malloc(n * sizeof(int));
    for(i=0; i<n; i++){
        result[i] = array[start+i];
    }
    return result;
}

快速排序

快速排序的最简单情景和合并排序一样即认为对不含或仅含一个元素的数组顺序都是排好了的。递归部分如下：

选一个元素作为小元素与大元素的分界线，该元素常称为枢轴；
重排数组中的元素使大元素移到数组的末端而小元素移到数组首端，即分割数组；
为每一个子数组元素排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
typedef enum {false, true} bool;

void SortIntegerArray(int array[], int n){
    int boundary;
    if(n <= 1){
        return;
    }
    boundary = Partition(array, n);
    SortIntegerArray(array, boundary);
    SortIntegerArray(array+boundary+1, n-boundary-1);
}

static int Partition(int array[], int n){
    int pivot, lh, rh, temp;
    pivot = array[0];
    lh = 1;
    rh = n - 1;
    while(true){
        while(lh<rh && array[rh]>=pivot){
            rh--;
        }
        while(lh<rh && array[lh]<pivot){
            lh++;
        }
        if(lh == rh){
            break;
        }
        temp = array[lh];
        array[lh] = array[rh];
        array[rh] = temp;
    }

    if(array[lh] >= pivot){
        return 0;
    }
    else{
        array[0] = array[lh];
        array[lh] = pivot;
        return lh;
    }
}