常用排序算法——合并排序和快速排序

发表于 | 分类于 | 阅读次数

分治

分治(Divide and Conquer)是一场常见的算法策略。分治策略的基本思想就是对于一个问题规模为N的问题，将其划分为规模足够小的K个子问题，子问题由于规模足够小可以直接求解，最后将规模足够小的K的问题的解合并得出原问题的解。
分治策略的问题的求解过程的一般套路就是：

  1. 判断问题规模，足够小进入步骤2，否者进入步骤3
  2. 直接对问题进行求解，返回问题的解。
  3. 将问题拆分成K个小规模的问题，进入步骤2。并将解合并，得到原问题的解。

由于分治策略的步骤描述自带递归属性，因此分治策略的算法实现常采用递归来实现。递归的算法通常会含有三部分，第一部分是个基准情况(Base Case)，第二部分是问题拆分，并调用自身，第三部分是合并并返回结果。

分治策略中主要有两个关键过程：

  • 将原问题拆分Division
  • 将各子问题合并Combination

分治策略的主要时间开销发生在这两个过程，通常分治策略有两类

  1. 拆分容易，合并困难
  2. 拆分困难，合并简单

下文中的合并排序和快速排序分别属于上面的第1和第2类。

合并排序和快速排序

在常见排序算法中，合并排序和快速排序是典型的分治算法，其时间复杂度的平均性能均为nlgn。合并排序的最坏时间复杂度也能保持nlgn，而快速排序的最坏时间复杂度却为n*n。合并排序是稳定的，而快速排序不是稳定的。

另外合并排序是拆分容易，合并困难，而快速排序则是拆分困难，合并容易。

  1. 合并排序又称归并排序，主要的思想是：将待排序列拆分至数个足够小的子序列，然后将相邻子序列合并为一个有序子序列，重复合并相邻有序子序列直到整个序列有序。

  2. 快速排序的主要思想则是，选取一个枢纽（pivot）， 将待排序列拆分为左右两个子序列A,B，使得子序列A的元素都不大于pivot， 子序列B的元素都大于pivot。这样使得子序列A的元素都不大于子序列B，然后对子序列A，B递归进行这种拆分，直到待拆分的序列足够小，最后整个序列变成有序。

由于合并排序和快速排序每次元素的移动都不只移动了一个位置，因此每次元素的比较都不只消除了一个逆序对，因此对于插入排序这种每次比较只移动一个位置的算法，时间复杂度会得到改善。

快速排序的递归实现

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
int partition(int* a, int l, int h) {
    int pivot = a[l];
    int i,j;
    i = l - 1;
    j = h + 1;
    while(true) {
        while(a[--j] > pivot);
        while(a[++i] < pivot)
            if(i >= h)
                break;
        //i 、j cross
        if(i >= j)
            break;

        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    a[j] = pivot;
    return j;
}

void quickSort(int* a, int l, int h) {
    if(l >= h)
        return;
    int p = partition(a, l, h);
    quickSort(a, l, p);
    quickSort(a, p+1, h);
}

合并排序的递归实现

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
void merge(int* a, int l, int m, int h) {
    if(l == h)
        return;

    int* b = (int*)malloc(sizeof(int) * (h - l + 1));
    int i = l, j = m + 1;
    int k = 0;

    while(i <= m && j <= h)
        b[k++] = a[i] > a[j] ? a[j++] : a[i++];

    if(i <= m)
        while(i <= m)
            b[k++] = a[i++];
    if(j <= h)
        while(j <= h)
            b[k++] = a[j++];
    //回写
    i = l;
    k = 0;

    for(; i <= h;)
        a[i++] = b[k++];
}

void mergeSort(int* a, int l, int h) {
    if(l >= h)
        return;
    int m = (h + l) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m+1, h);
    merge(a, l, m, h);
}

合并排序的非递归实现

由于递归会导致函数调用栈的暴增，会引入额外的时间开销，例如现场保护和恢复之类的。通递归版本的算法都可以改写为迭代版本的算法。递归算法的优点是实现简单直观，易于理解，缺点是如果有时候调用深度过深，会带来栈内存溢出和额外的运行时间开销。迭代算法的有点是不会有额外的函数调用栈的增长， 缺点是难于理解且难于实现。

合并排序的迭代版本的实现相对来讲是比较简单直观的，大致思路就是：第1轮，待排序列S中相邻的长度为1的子序列进行合并，第2轮，序列S中相邻的长度为2的子序列进行合并，第i轮，待排序列S中相邻的长度为2的i-1次方的子序列进行合并。直到待合并的子序列数为1。

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
void merge(int* a, int l, int m, int h) {
    if(l == h)
        return;

    int* b = (int*)malloc(sizeof(int) * (h - l + 1));
    int i = l, j = m + 1;
    int k = 0;

    while(i <= m && j <= h)
        b[k++] = a[i] > a[j] ? a[j++] : a[i++];

    if(i <= m)
        while(i <= m)
            b[k++] = a[i++];
    if(j <= h)
        while(j <= h)
            b[k++] = a[j++];
    //回写
    i = l;
    k = 0;

    for(; i <= h;)
        a[i++] = b[k++];
}

//非递归版本
void mergeIteation(int* a, int n) {
    int offset = 1;
    while(offset <= n) {
        int i = 0;
        for(;i < n;) {
            merge(a,i, i+offset-1,i+offset*2 - 1);
            i = i + offset * 2;
            if(n - 1 - i < offset)
                break;
        }
        offset *= 2;
    }
}