在了解了简单排序之后，我们仍不满足简单排序的效率，在此驱动之下，又有效率更高的排序算法被设计出来

希尔排序

在学习了冒泡和插入排序之后，我们发现，对于同一数列而言，采用冒泡排序和采用插入排序所进行的交换次数是一致的，进而可以得知，排序实际是消除逆序对的过程，由此我们可以有以下思路

实现思路

  • 冒泡和插入排序每次只消除一个逆序对

  • 既然排序是为了消除逆序对，那么能不能通过一次交换消除多个逆序对呢

  • 显然，我们可以采用隔几个数字的方式来进行排序，这样一来，进行一次交换就可消除不止一个逆序对

  • 结和以上思路，便实现了希尔排序的一般实现方式

代码1

1
2
3
4
5
6
7
8
9
10
11
void ShellSort(ELEMENT_TYPE a[], int n) {   // 希尔1
    int i, j, k;
    for (i = n/2; i > 0; i /= 2) {
        for (j = i; j < n; j++) {
            ELEMENT_TYPE temp = a[j];
            for (k = j; k >= i && a[k - i] > temp; k -= i)
                a[k] = a[k - i];
            a[k] = temp;
        }
    }
}

简单的希尔排序如上，也就是分别隔n/2``n/4...... 直至n = 1

但是采用这种方法可能出现尴尬的情况

1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16
1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16
1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16
1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

也就是数列刚好每隔n/2``n/4...... 都是排序完成的，那么扫描就成了无用功

发现上述问题之后，有专家就提出来一个交换间隔的数列

  • Hibbard 增量序列

    • \(D_K\) = \(2^k\) - 1（\(D_k\)为间隔数）
    • 最坏情况：\(T = Θ{(N^{\frac{2}{3}})}\)
    • 猜测：\(T_{avg} = O(N{\frac{5}{4}})\)

  • Sedgewick增量序列

    • {1, 5, 19, 41, 109, ...}

      —— \(9\times4^i - 9\times2^i + 1\) 或者 \(4^i - 3\times2^i + 1\)

    • 猜想：\(T_{avg} = O(N^\frac{7}{6})\) , \(T_{worst} = O(N\frac{4}{3})\)

则改进后的代码为：（只写Sedgewick）

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ShellSort(ELEMENT_TYPE a[], int n) {   // 希尔2
    int si, i, j, k;
    int Sedgewick[] = {929, 505, 20, 109, 41, 19, 5, 1, 0};
    for (si = 0; Sedgrwick[si] >= N; si++) {
        for (i = Sedgrwick[si]; i > 0; i = Sedgrwick[++si]) {
            for (j = i; j < n; j++) {
                ELEMENT_TYPE temp = a[j];
                for (k = j; k >= i && a[k - i] > temp; k -= i)
                    a[k] = a[k - i];
                a[k] = temp;
            }
    	}
    }  
}

堆排序

那么简单排序中的选择排序是否可以优化呢？答案是肯定的

实现思路

  • 首先选择排序的外层循环是不可变的，优化的只能是内层循环，即寻找数列之中最小的元素的过程
  • 选择排序中，此过程运用了遍历数组的方式，复杂度为 \(O(N)\)
  • 而在之前，我们学习了堆的知识，所以我们可以利用最小堆来进行寻找

代码1

1
2
3
4
5
6
7
8
9
void HeapSort(ELEMENT_TYPE a[], int n) {    // 堆
    int i;
    ELEMENT_TYPE tmpA;
    BuildHeap(a);
    for (i = 0; i < n; ++i)
        tmpA = DeleteMin(a);
    for (i = 0; i < n; ++i)
        a[i] = tmpA[i];
}
  • 如上代码，首先将a调整为一个最小堆
  • 之后取出依次最小的元素置于一个新临时数组中
  • 最后，将排好序的tmpA数组中的元素复制回原数组

这样，虽然将时间复杂度降到了\(O(log(n))\) ，但是空间复杂度提升了一倍，在数据量较大之时应用不是很方便

代码2

1
2
3
4
5
6
7
8
9
void HeapSort(ELEMENT_TYPE a[], int n) {    // 堆
    int i;
    for (i = N / 2; i >= 0; --i)
        PercDown(a, i, n);
    for (i = 0; i < n; --i) {
        Swap(&a[0], &a[i]);
        PercDown(a, i, n);
    }
}
  • 首先通过第一个循环将其建为最大堆
  • 将最大堆的根与a[0]交换，之后再将a调整为最大堆
  • 重复2步骤，n次

由定理可知，其平均比较次数为 \(2NlogN - O(Nlog(logN))\)

归并排序

归并排序的核心就是有序子列的归并，也就是将两个已经排好序的数列，归并到一个更大的数列中去

实现思路

  • 分别设立两个指针，从两个数组的开头扫到结尾，比较指针所在处数组的值，将小值复制到大数组中，之后将小值所在数组的指针后移一位
  • 重复步骤一，直至所有数字都挪入大数组

核心理解之后就可以进行排序了，也就是将需排序的数组拆分成若干已排序的小数组直接进行归并

递归代码

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
void Merge(int a[], int l, int r, int rightEnd, int temp[]){
    int leftEnd = r-1 ;
    int left = l, tmp = l;

    while (l <= leftEnd && r <= rightEnd){ // 当左右子序列均不空
        if (a[l] > a[r])
            temp[tmp++] = a[r++];
        else
            temp[tmp++] = a[l++];
    }
    while (l <= leftEnd)
        temp[tmp++] = a[l++];
    while (r <= rightEnd)
        temp[tmp++] = a[r++];
    for (int i = left; i < rightEnd + 1; i++)
        a[i] = temp[i];
}

void MergeSort(int a[], int l, int rightEnd, int temp[]) {
    int center;
    if (l < rightEnd) {
        center = (l + rightEnd) / 2;
        MergeSort(a, l, center, temp);
        MergeSort(a, center + 1, rightEnd, temp);
        Merge(a, l, center+1, rightEnd, temp);
    }
}

void Merge_sort(int a[], int n){
    int* tmpA;
    tmpA = malloc(n * sizeof(int));
    if (tmpA != NULL){
        MergeSort(a, 0, n-1, tmpA);
        free(tmpA);
    } else {
        printf("ERROR");
    }
}
  • 三个函数，分别为归并函数，主函数，和接口函数
  • 归并函数就是将两个有序数组归并为一个大数组
  • 主函数起到将数组左边右边分别进行归并的作用，也就是当数组分割到只有一个元素之后，直接进行归并
  • 接口函数为了使其符合排序函数的规律，仅传入数组及其长度

循环代码

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
44
45
46
void Merge(int a[],  int temp[], int l, int r, int rightEnd){
    int leftEnd = r-1 ;
    int left = l, tmp = l;

    while (l <= leftEnd && r <= rightEnd){
        if (a[l] > a[r])
            temp[tmp++] = a[r++];
        else
            temp[tmp++] = a[l++];
    }
    while (l <= leftEnd)
        temp[tmp++] = a[l++];
    while (r <= rightEnd)
        temp[tmp++] = a[r++];
    for (int i = left; i < rightEnd + 1; i++)
        a[i] = temp[i];
}

void MergePass(ELEMENT_TYPE a[], ELEMENT_TYPE tmpA[], int n, int length) {
    int i, j;
    for (i = 0; i <= n - 2*length; i += 2*length)
        Merge(a, tmpA, i, i+length, n-1);
    if (i + length < n)
        Merge(a, tmpA, i, i+length, n-1);
    else 
        for (j = i; j < n; j++)
            tmpA[j] = a[j];
}

void MergeSort (ELEMENT_TYPE a[], int n) {
    int length;
    ELEMENT_TYPE* tmpA;
    length = 1;
    tmpA = malloc(n*sizeof(ELEMENT_TYPE));
    if (tmpA != NULL) {
        while (length < n) {
            MergePass(a, tmpA, n, length);
            length *= 2;
            MergePass(a, tmpA, n, length);
            length *= 2;
        }
        free(tmpA);
    } else {
        printf("空间不足");
    }
}

简单的递归可以用循环代替，所以也就有了上面的代码

  • 即先将数组元素，相邻的两个一对进行归并
  • 之后相邻的元素便排序完成，再四个一对进行归并，同理，之后就是八个......

快速排序

快排是很有名的一个排序算法，在许多语言的库函数中直接调用的排序函数就是快速排序，据说快排是在实际应用中最快的算法，其由归并排序衍生而来，也主要采用递归的方法来实现，其主要原理寻找主元和针对主元对数组进行调整的过程

选主元

主元的选择是快排中至关重要的一个环节，如果主元失误的话就整个排序就容易废掉，那么如何选取主元呢?

  • 随机选择主元，rand() 函数也是需要时间的
  • 取数组头，中，尾三个数字中的中位数
  • 等等 等等......

这里采取选取三者中位数的方式来选取主元

代码：

1
2
3
4
5
6
7
8
9
10
11
12
ELEMENT_TYPE Media3 (ELEMENT_TYPE a[], int left, int right) {
    int center = (left + right) / 2;
    if (a[left] > a[center])
        Swap(&a[left], &a[center]);
    if (a[left] > a[right])
        Swap(&a[left], &a[right]);
    if (a[center] > a[right])
        Swap(&a[center], &a[right]);

    Swap(&a[center], &a[right-1]);
    return a[right-1];
}
  • 功能就是将三个数排列，并将中位数置于right-1的位置，并返回主元

子集划分

  • 子集划分主要由两个 “指针” 从两端进行查找，将比主元小的元素调整到数组左边，比主元大的元素调整到数组的右边
  • 之后将主元移动到数组固定的位置

在子集划分之后，采用递归处理， 将数组左边进行快排，右边进行快排

了解了子集划分之后，就又有了新的问题，因为快排的实现方式是采用递归的方法，所以对于小规模数据的排序可能还不如插入排序，所以我们应该设置一个阈值，在数据量低于此阈值的情况下直接采用插入排序

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void QSort (ELEMENT_TYPE a[], int left, int right) {
    int pivot, cutoff = 10000, low, high;
    if (cutoff <= right - left) {
        pivot = Media3(a, left, right);
        low = left;
        high = right -1;
        for (; ;) {
            while (a[++low] < a[right-1]);
            while (a[--high] > a[right-1]);
            if (low < high)
                Swap(&a[low], a[high]);
            else
                break;
        }
        Swap(&a[low], &a[right-1]);
        QSort(a, left, low-1);
        QSort(a, low+1, right);
    } else
        InsertionSort(a+left, right-left+1);
}
  • 此段代码最精髓之处我觉得是采用两个while循环进行子集划分的操作，很帅
  • pivot为主元 cutoff为阈值 我将其设为1000

之后对接口进行统一化处理

代码：

1
2
3
void QuickSort (ELEMENT_TYPE a[], int n){
    QSort(a, 0, n-1);
}