Sorting Algorithms

Table of Contents

1 排序算法简介

A sorting algorithm is an algorithm that puts elements of a list in a certain order.

参考:
Donald Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition

1.1 稳定排序和不稳定排序

稳定排序和不稳定排序的区别如图 1 所示。

Sorry, your browser does not support SVG.

Figure 1: 稳定排序和不稳定排序

1.2 内部排序和外部排序

If the number of objects is small enough to fits into the main memory, sorting is called internal sorting. If the number of objects is so large that some of them reside on external storage during the sort, it is called external sorting.

本文重点介绍内部排序。

2 冒泡排序

冒泡排序(Bubble sort)算是最容易实现的排序算法了。

冒泡排序的思想:依次比较相邻的两个数,将小数放在前面,大数放在后面。如果从后往前比较,则可以把最小的数放到第一位(方式一);如果从前往后比较,则可以把最大的数放到最后一位(方式二)。

方式一:每趟(从后往前遍历一次无序区)把无序区的最小的数“冒出来”,直到无序区仅有一个元素就可以结束。
\[\underbrace{r_0 \leq r_1 \leq r_2 \cdots \leq r_{k-1}}_{\text{sorting is finished}} \mid \underbrace{r_{k} r_{k+1} \cdots r_{n-1}}_{\text{unsorted}}\]

方式二:每趟(从前往后遍历一次无序区)把无序区中最重的泡(最大的数)下沉!
\[\underbrace{r_0 r_1 \cdots r_{k-1}}_{\text{unsorted}} \mid \underbrace{r_{k} \leq r_{k+1} \cdots \leq r_{n-1}}_{\text{sorting is finished}}\]

2.1 冒泡排序实现

#include<stdio.h>
#include<stdlib.h>

//方式一,每次append最小的数到“有序区”的后面。数组前部分为有序区,后部分为无序区。
void bubble_sort1(int a[], int n) {
    int i,j;
    int tmp;
    for (i=0; i<n; i++) {
        for (j=n-1; j>i; j--) {  //从后向前“冒出”最小的数。
            if (a[j-1] > a[j]) {
                tmp = a[j-1];
                a[j-1] = a[j];
                a[j] = tmp;
            }
        }
    }
}

//方式一,每次insert最大的数到“有序区”的前面。数组前部分为无序区,后部分为有序区。
void bubble_sort2(int a[], int n) {
    int i,j;
    int tmp;
    for (i=0; i<n-1; i++) {
        for (j=0; j<n-1-i; j++) {  //从前往后“下沉”最大的数。
            if (a[j] > a[j+1]) {
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
}

void print_array(int a[], int n) {
    int i;
    for (i=0; i<n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int main() {
    const int N=15;
    int a[N], b[N];
    int i;
    for (i=0; i<N; i++) {
        a[i] = b[i] = rand() % 100;  //这里没加入随机种子,每次都会得到同样的随机数。
    }
    print_array(a, N);   // 输出:7 49 73 58 30 72 44 78 23 9 40 65 92 42 87 

    bubble_sort1(a, N);
    bubble_sort2(b, N);

    print_array(a, N);   // 输出:7 9 23 30 40 42 44 49 58 65 72 73 78 87 92 
    print_array(b, N);   // 输出:7 9 23 30 40 42 44 49 58 65 72 73 78 87 92 
}

2.2 冒泡排序的简单优化

如果某一趟没有发生交换,则说明所以的元素都已经排序好了,不必再进行下一趟的排序。
设置一个变量exchange,在每趟开始前,设置为false,如果发生交换就将其置为true。每趟结束时检查exchange,如果为false,就提前结束排序。
这样当原数组有序时,一趟就可以结束算法了!

void bubble_sort2_optimize(int a[], int n) {
    int i,j;
    int tmp;
    int swapped=0;
    for (i=0; i<n-1; i++) {
        for (j=0; j<n-1-i; j++) {  //从前往后“下沉”最大的数。
            if (a[j] > a[j+1]) {
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
                swapped = 1;
            }
        }
        if (swapped == 0) { return; }
    }
}

3 直接插入排序

插入排序:每趟把无序区的第一个元素插入到有序区的恰当位置,直到没有无序区。
选择排序:每趟把无序区的最小元素找出来添加到有序区的末尾,直到没有无序区(这点和冒泡排序类似)。
\[\underbrace{r_0 \leq r_1 \leq r_2 \cdots \leq r_{k-1}}_{\text{有序区}} \mid \underbrace{r_{k} r_{k+1} \cdots r_{n-1}}_{\text{无序区}}\]

注1:插入排序程序开始时,可以把第一个元素看成是有序区,从第2个元素到最后一个元素看成是无序区。
注2:有序区和无序区的位置可以调换(即有序区也可以位于数组后部分),算法做对应调整即可。

3.1 直接插入排序实现

//直接插入排序:每趟把无序区的第一个元素插入到有序区的恰当位置,直到没有无序区。
void insert_sort(int a[], int n) {
    int i,j;
    int flag;
    for (i=1; i<n; i++) {
        flag = a[i];               //把无序区的第一个元素,也就是当前要插入的元素保存到flag中
        for (j = i-1; flag < a[j] && j >= 0; j--) {  //从无序区的前一个位置开始向前寻找插入位置
            a[j+1] = a[j];         //把比flag大的元素后移一位
        }
        a[j+1] = flag;             //找到插入位置,将原a[i]中的值存入第j+1个位置,本次插入完成
    }
}

注:上面的代码中j >= 0这个测试只在到达了数组的起始处时,它才为true。每次去判断显得多余,怎么改进才能去掉这个“多余的”判断?
思路是首先将数组中的最小元素放在数组的起始位置,让它做“哨兵”。详情请看下文。

3.1.1 哨兵及其作用

什么是“哨兵”?
凡是为简化边界条件的检测而引入的附加结点(元素)均可称为“哨兵”。单链表中的头结点常常是一个“哨兵”。

“哨兵”的作用是:
目的在于免去查找过程中每一步都要检测边界条件。
引入“哨兵”后使得测试循环条件的时间大约减少了一半,所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法,要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技,而应该深刻理解并掌握这种技巧。

3.1.2 带哨兵的直接插入排序

//直接插入排序的优化版本:利用“哨兵”使程序运行更高效
//首先把数组中的最小元素和数据第一个元素a[0]交换位置,然后利用a[0]作“哨兵”,省去了每次判断数组是否达到起始位置,提高程序效率。
void insert_sort_with_sentinel(int a[], int n) {
    int i,j;
    int flag = a[0];                  //开始用来暂存a[0],后来用来暂存无序区的第一个元素。
    j = 0;                            //j保存着最小值的下标,初始时设为0。
    for (i=1; i<n; i++) {
        if (a[i] < a[0]) {
            a[0] = a[i];              //a[0]保存着当前找到的最小值。
            j = i;                    //j赋值为当前找到的最小值的下标。
        }
    }
    a[j] = flag;                      //至此,a[0]已经和数组里的最小元素完成交换。

    for(i = 2; i < n; i++) {          //无序区可从第三个元素,即a[2]开始。从a[1]开始不会错,但这样多遍历了一次。
        flag = a[i];
        for(j = i-1; flag < a[j]; j--) { //不用判断j >= 0了,因为前面已使a[0]最小,当j减小到0时,flag < a[j]一定为false,循环退出。
            a[j+1] = a[j];
        }
        a[j+1] = flag;
    }
}

3.2 直接插入排序的时间复杂度分析

时间复杂度分析一般要从“最好情况”,“最坏情况”和“平均情况”三种情况入手。

为方便起见,把直接插入排序再次摘抄如下:

void insert_sort(int a[], int n) {
    int i,j;
    int flag;
    for (i=1; i<n; i++) {                            /* 外层循环 */
        flag = a[i];
        for (j = i-1; flag < a[j] && j >= 0; j--) {  /* 内层循环 */
            a[j+1] = a[j];
        }
        a[j+1] = flag;
    }
}

直接插入排序中,最坏情况是输入数据是反向排序的,这时,嵌套循环的每一个循环都花费 \(N\) 次迭代,从而运行时间会为 \(O(N^2)\) 。
直接插入排序中,最好情况是输入数据已经预先排序,这时,内层循环的检测条件总会不成立而导致内层循环终止,从而运行时间会为 \(O(N)\) 。事实上,如果输入数据几乎被排序,那么插入排序将运行得很快。
直接插入排序的平均时间复杂度和最坏情况一样,也是 \(O(N^2)\) (这里不证明,分析平均时间复杂度往往比较麻烦,它需要假定所有输入具有相同的可能性)。详情可参考:数据结构与算法分析——C语言描述(原书第2版),7.3 一些简单排序算法的下界

4 二分插入排序

插入排序是把无序区的第一个元素插入到有序区的恰当位置,前面的直接插入排序是从有序区的最后一个元素往前寻找恰当位置,当元素个数比较多时,我们容易想到用二分查找办法寻找恰当位置。但二分插入排序是先用二分查找找到恰当位置后,再把有序区中恰当位置后的元素后移;没有在一次迭代中完成,而前面我们实现的直接插入排序在寻找位置的同时就进行了元素的移动,所以并不见得二分插入排序比直接插入排序要好。有实验表明,仅当n较大时,二分插入排序性能略优于直接插入排序。

4.1 二分插入排序实现

//二分插入排序实现(仅当n较大时,性能略优于直接插入排序)
void binary_insert_sort(int a[], int n) {
    int low,high,mid;
    int temp;
    for (int i = 1; i < n; i++)
    {
        low = 0,
        high = i - 1;
        temp = a[i];
        while (low <= high)      //low>high时while循环结束。
        {
            mid = (low + high)/2;
            if (temp < a[mid])   //把<换成<=算法也能得到正确结果,但排序不稳定了。
                high = mid - 1;  //在前半区间进行查找
            else
                low = mid + 1;   //在后半区间进行查找
        } //while循环结束时low==high+1,记录着有序区中a[i]应当插入的位置。

        for (int j = i - 1; j >= low; j--)    //把所有大于a[low]的元素后移一位
        {
            a[j + 1] = a[j];
        }
        a[low] = temp;  //a[high+1] = temp;也正确,将原a[i]中的值存入a[low],本次插入完成
    }
}

说明1:二分插入排序的代码比较容易写错,把while (low <= high)写成while (low < high)将会得到错误结果,把if (temp < a[mid])写成if (temp <= a[mid])将会使排序不稳定,把a[low] = temp写为a[low+1] = temp也将得到错误结果。
说明2:二分插入排序和直接插入排序相比,仅减少了元素比较的次数,而元素移动次数没变。由于二分插入排序的查找和移动不是在同一个迭代中完成的(前面实现的直接插入排序是在查找插入位置的同时就进行了元素的移动),所有只有当n较大时其性能才略优于直接插入排序。

5 希尔排序

Shell sort 由Donald L.Shell于1959年提出。Shell排序又叫减小增量排序(Diminishing Increment Sort)。
希尔排序可看作是对直接插入排序的改进,允许交换不相邻的数据来提高效率。

希尔排序的思想:先取一个小于n的整数h作为第一个增量,把数组中全部元素分成h个组(所有距离为h的倍数的记录放在同一个组中)。先在各组内进行直接插人排序;然后,取第二个增量(小于h)重复上述的分组和排序,直至所取的增量降为1,即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。其算法演示如下:

sorting_shellsort.png

Figure 2: 希尔排序演示

从上图可以清楚地看到Shell排序过程,将整个记录序列分割为若干子序列,子序列内分别进行直接插入排序,子序列的数量由多变少(最后变成1),子序列的长度由短变长(最后变成整个序列)。

算法本质: 设增量序列: \(h_1,h_2,h_3 \cdots h_t\) 。增量值较大的排序(移动了相距较远的元素)会使得增量值较小的排序更加容易!只要最后一趟的增量值为1,就会产生一个排序好的数组。

问题:选择的增量序列不同,其排序效率有差别,那如何选择好的增量序列呢?这个问题难以回答。但好的增量序列都有个特点:应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
假设增量序列为:1、2、4、8、16、128……,这个增量序列的缺点是比较明显的,处于奇位置的元素直到最后一趟(即增量为1)时才会与偶位置的元素进行比较。

5.1 希尔排序实现

下面以两个不同的增量序列对Shell算法进行实现。一个是Shell本人建议的,一个是Knuth建议的。

实现一(使用Shell建议的增量序列):增量序列流行(但不好)的选择是满足 \(h_t = N/2, h_k = h_{k+1}/2\) ,这是Shell本人建议的。特别地,当N为2的次方时,这个序列变为了1、2、4、8……,关于这个序列的缺点前面有介绍。

//Shell排序实现:使用Shell建议的增量序列
//程序摘自:《The C Programming Language》第2版3.5节。
void shell_sort(int a[], int n) {
    int gap, i, j, temp;
    for(gap=n/2; gap>0; gap/=2) {     //设定步长
        for(i=gap; i<n; i++) {
            for(j=i-gap; j>=0 && a[j]>a[j+gap]; j-=gap) {  //比较相距gap的元素,逆序互换
                temp=a[j];
                a[j]=a[j+gap];
                a[j+gap]=temp;
            }
        }
    }
}

实现二(使用Knuth建议的增量序列):Knuth于1969年提出了一个步长序列:1、4、13、40、121、364、1093、3280、9841……

//Shell排序。增量序列选择的是Knuth推荐的序列。
void shell_sort_knuth(int a[], int n) {
    int h,i,j,temp;
    for(h=1; h<=n/9; h=h*3+1); //这个for循环仅仅是计算h的初值,使其为下列增量序列中小于等于N/9的最大值,所以最后一个分号是必要的。

    /* h = 1, 4, 13, 40, 121, 364... 3*h+1 */
    for(; h>0; h=h/3) {
        for(i=h; i<n; i++) {
            temp=a[i];
            for(j=i-h; j>=0&& a[j]>temp; j-=h) {
                a[j+h]=a[j];
            }
            a[j+h]=temp;
        }
    }
}

5.2 希尔排序的时间、空间复杂度和稳定性

Shell排序的时间复杂度:
Shell排序的时间复杂度很复杂,其运行时间公式还未得到,使用不同的增量序列其最坏情形运行时间不一样。如:使用希尔增量(1、2、4、8、16……)时,最坏情形运行时间为 \(\Theta(N^2)\) 。而使用Hibbard增量(1、3、7、15、……)时,最坏情形运行时间为 \(\Theta(N^{3/2})\) 。

Shell排序的空间复杂度:
没有使用额外的辅助空间,其空间复杂度为 \(O(1)\) 。

Shell排序的稳定性:
由于希尔排序采用多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以Shell排序是不稳定的。

6 选择排序(不稳定)

选择排序的思想:每趟把无序区的最小元素添加到有序区的末尾,直到没有无序区(假设有序区在前,无序区在后)。如图 3 所示。

sorting_selection_sort.gif

Figure 3: 选择排序gif动画演示

选择排序不是稳定的排序算法。 比如,对序列5,3,5,2进行选择排序。第一遍选择第1个元素5和最小的元素2交换,那么原序列中两个5的相对顺序就被破坏了,所以它不是一个稳定的排序算法。

6.1 选择排序实现

//简单选择排序
template<typename T>
void SelectionSort(T a[],int n)
{
  for(int i =0; i < n-1; i++) { // 不必用 i < n(因为到最后一趟时,最后一个元素肯定为最大)

    // 寻找最小元素下标
    int min = i;
    for(int j = i +1; j < n; j++) {
      if(a[j]< a[min]) min =j;
    }

    // 交换a[i]和a[min]
    if(min != i) {
      T tmp = a[min];
      a[min]= a[i];
      a[i]= tmp;
    }
  }
}

6.2 冒泡排序和选择排序的区别

冒泡排序每趟比较和移动相邻的两项,同时把小数交换到大数前;而选择排序每趟只会交换一次。
一般来说,冒泡排序和选择排序“元素比较”的次数相同,但冒泡排序的“元素交换”的次数要比选择排序要多。 冒泡排序是稳定排序,而选择排序不是稳定排序。

7 堆排序

堆排序是一种利用二叉堆(优先队列)对数组进行排序的方法。

堆排序的思路为:
第一步,从元素个数为 \(N\) 的无序数组中建立一个二叉堆,二叉堆BuildHeap的时间为 \(O(N)\) 。
第二步,执行 \(N\) 次DeleteMin操作。按照顺序,最小的元素先离开该堆,通过将这些元素记录到第二个数组然后再将数组拷贝回来,这样就得到了 \(N\) 个排序后的元素。由于每个DeleteMin花费的时间为 \(O(log_{2}N)\) ,因此总的运行时间为 \(O(N log_{2}N)\) 。

参考:数据结构与算法分析——C语言描述(原书第2版),7.5节 堆排序

8 归并排序(Merge sort)

归并排序的思想为:如果N=1,那么只有一个元素需要排序,答案是显然的。否则,递归地将前半部分数据和后半部分数据各自归并排序,得到排序后的两部分数据,然后使用合并算法再将这两部分合并到一起。归并排序是经典的分治策略,将问题分成一些小的问题然后递归求解,最后将解得的各个答案修补到一起。如图 4 所示。

Sorry, your browser does not support SVG.

Figure 4: 递归的归并排序算法演示

8.1 归并排序实现

// 归并排序C++实现
#include<iostream>
#include<cstdlib>
#include<algorithm>  // std::stable_sort;

#define N 100

//合并过程。
template<typename T>
void Merge(T a[], int low,int mid,int high) {
  int Lpos = low;
  int Rpos = mid +1;
  T * tmp = new T[(high - low +1)];

  int i =0;
  while(Lpos <= mid && Rpos <= high) { //两个序列中取小者复制给tmp。
    tmp[i++] = (a[Lpos]<= a[Rpos]) ? a[Lpos++] : a[Rpos++];
  }

  //上面while循环结束后,能保证前序列、后序列最多有一个为非空,所以后面2个while循环谁先谁后没关系
  while(Lpos <= mid) {                 //若前序列非空,则复制剩余的记录到tmp。
    tmp[i++]= a[Lpos++];
  }

  while(Rpos <= high) {                //若后序列非空,则复制剩余的记录到tmp。
    tmp[i++]= a[Rpos++];
  }

  for(i = low; i <= high; i++) {       //i <= high;必须要等号,因为函数参数传递进来就是数组下标了。
    a[i]= tmp[i-low];                  //把tmp[0..(high - low)]复制给a[low..high]。
  }
  delete[] tmp;
}

template<typename T>
void MSort(T a[],int low,int high) {
  if(low < high) {
    int mid =(low + high)/2;      //分解
    MSort(a,low,mid);             //递归对a[low..mid]排序
    MSort(a,mid+1,high);          //递归对a[mid+1..high]排序
    Merge(a,low,mid,high);        //合并。是Merge<T>(a,low,mid,high);的略写。
  }
}

//归并排序测试代码
int main() {
  int a[N],b[N];

  for(int i=0; i<N; i++) {
    b[i]= a[i]= std::rand()%(5*N); //这里没加入随机种子,每次都是同样随机数。
  }
  std::cout<<"排序前数组为:"<< std::endl;
  for(int i=0; i<N; i++) { std::cout<<a[i]<<" ";}

  std::stable_sort(b,b+N); //利用algorithm中的排序算法进行排序。
  std::cout<<std::endl<<"STL算法排序后数组为:"<<std::endl;
  for(int i=0; i<N; i++) { std::cout<<b[i]<<" ";}

  MSort<int>(a,0,N-1); //也可是MSort(a,0,N-1);函数模板的实参可省。
  std::cout<<std::endl<<"归并排序排序后数组为:"<<std::endl;
  for(int i=0; i<N; i++) { std::cout<<a[i]<<" ";}
  std::cout<<std::endl;
}

说明:由于Merge被调用了很多次,在Merge里动态分配和释放内存其效率可能不高。另外一个方案是在main中分配,通过参数传递下去。

参考:数据结构与算法分析——C语言描述(原书第2版),7.6节 归并排序

8.1.1 非递归实现归并排序

// 非递归实现归并排序
template<typename T>
void MSort(T a[],int n)
{
  for(int subListSize = 1; subListSize < n; subListSize *=2) {
    int part1Start = 0;
    while(part1Start + subListSize < n) {
      int part2Start = part1Start + subListSize;
      int part2End = (n < part2Start + subListSize -1) ? n : (part2Start + subListSize -1);
      Merge(a, part1Start, part2Start-1, part2End);
      part1Start = part2End + 1;
    }
  }
}

9 快速排序

快速排序(Quick sort)是C.R.A.Hoare于1962年提出的一种排序算法。正如它的名字所标示的,快速排序是在实践中最快的已知排序算法。和归并排序类似,快速排序也是一种分治算法。

快速排序的思想如下:
(1) 如果数组S中元素个数是0或者1,则返回。
(2) 取S中任一元素v,称它为枢纽元(pivot)。
(3) 重新排序数组,所有比pivot小的元素放在pivot前面,所有比pivot大的元素放到pivot后面(相同的数可以到任一边)。这称为分区(partition)操作。
(4) 递归地把上步中产生的“小于pivot的子数组”和“大于pivot的子数组”排序。

快速排序的各步演示如图 5 所示,快速排序gif动画演示如图 6 所示。

sort_qsort_example.png

Figure 5: 快速排序各步演示示例

sort_quicksort.gif

Figure 6: 快速排序gif动画演示(红色竖线是pivot元素,摘自https://en.wikipedia.org/wiki/Quicksort

如何实现分区操作是快速排序的关键。

9.1 Lomuto分区操作(单向扫描方式)

Lomuto分区操作的基本思想为:
一、选择最后一个元素作为pivot;
二、依次把前N-1个元素和pivot比较,通过后面步骤把“小数子数组”和“大数子数组”分开。发现正在测试的元素比pivot小时,就把这个小数移动到“大数子数组”的前面(具体操作是交换小数和“大数子数组”的第1个元素),这样在已经测试的元素中“小数子数组”和“大数子数组”一直是分开的。
三、把pivot元素和“大数子数组”的第一个元素交换。

Lomuto分区操作的gif动画演示如图 7 所示。

sort_lomuto_partition.gif

Figure 7: Lomuto partition

说明:Lomuto分区是一种从左到右的单向扫描方式,Hoare原版算法中采用的分区操作是从两端到中间的双向扫描方式(这里不介绍)。

9.2 快速排序实现(Lomuto版本)

下面是快速排序算法的一个实现(《算法导论(第3版)》中有介绍)。

// 快速排序实现(Lomuto版本)
#include<iostream>
#include<cstdlib>

#define N 100

void swap(int *x, int *y) {
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

int lomuto_partition(int A[], int l, int h) {
  int pivot = A[h];           /* 假定最后一个元素为枢纽元 */
  int i = l;
  int j;
  for (j=l; j < h; j++) {
    if (A[j] < pivot) {
      swap(&A[i], &A[j]);     /* 如果发现元素比枢纽元小,就把这个小数移动到“大数子数组”的前面
                                 (具体操作是该元素和“大数子数组”的第1个元素) */
      i++;                    /* i中保存着“大数子数组”第1个元素的下标 */
    }
  }

  swap(&A[i], &A[h]);        /* 把枢纽元放入到“小数子数组”和“大数子数组”中间 */
  return i;                  /* 返回枢纽元的下标  */
}

void quicksort(int A[], int l, int h) {
  int p;
  if (l < h) {
    p = lomuto_partition(A, l, h);
    quicksort(A, l, p-1);
    quicksort(A, p+1, h);
  }
}

int main() {
  int a[N];
  for(int i=0; i<N; i++) {
    a[i]= std::rand()%(5*N);   //这里没加入随机种子,每次都是同样随机数。
  }
  std::cout<<"array before sorting:"<<std::endl;
  for(int i=0; i<N; i++) { std::cout<<a[i]<<" "; }

  quicksort(a,0,N-1);

  std::cout<<std::endl<<"array after sorting:"<<std::endl;
  for(int i=0; i<N; i++) { std::cout<<a[i]<<" "; }
  std::cout<<std::endl;
}

上面实现的几个可能的改进点:
第1点:枢纽元素选择问题上采用“三数中值法”(在第一个,中间一个,最后一个元素中取一个中间大小的元素)。
第2点:对于小数组,快速排序不如插入排序好,而快速排序在递归过程中经常会遇到小数组,所以可以设置一个阈值,当元素小于这个值时采用插入排序。
关于这2点改进在《数据结构与算法分析——C语言描述(第2版)》7.7节中有介绍。
第3点:上面的实现是递归调用,当要排序的数据很多时,可能导致栈溢出,有优化方法可以减小栈的深度。详情可参考《算法导论(第3版)思考题7.4》,或 QuickSort Tail Call Optimization ,或 Efficient selection and partial sorting based on quicksort(说明:我们无法把快速排序修改为真正的“尾递归”,但可以利用尾递归思想减小栈的深度。)

9.3 快速排序的时间复杂度分析

完整的时间复杂度分析包括“最坏情况”,“最好情况”和“平均情况”下的时间复杂度分析。这里仅介绍最好情况下的时间复杂度分析。其它情况可以参考:数据结构与算法分析——C语言描述(原书第2版),7.7.5节 快速排序的分析

快速排序的运行时间等于 两个递归调用的运行时间加上花费在分割上的线性时间(枢纽元的选取仅花费常数时间)。

在最好的情况下,枢纽元正好位于中间,为了简化数字推导,我们假设两个子数组恰好各有为原数组的一半大小(忽略枢纽元),虽然这会给出稍微过高的估计,但是由于我们只关心大 \(O\) 答案,因此结果还是可以接受的。
\[T(N) = 2 T(N/2) + cN\]
根据 Master theorem 可得:
\[T(N) = O(N \log_{2} N)\]

9.4 快速选择(Quick Select)算法

选择问题(Selection problem)是指在 \(N\) 个数中找到第 \(k\) 大的数。

这个问题,可以用容量为 \(k\) 的最大堆(或者红黑树)来实现(依次读入数字,如果最大堆中已有的数字小于 \(k\) 个,则直接读入;如果最大堆满了,则找到堆中最大值,和待插入值比较,把较小的那个放入堆中),处理完所有数据后,最大堆堆顶元素就是第 \(k\) 大的数,其时间复杂度为 \(O(N \log_{2} k)\) 。这种算法不会修改原始数据,适合于海量数据处理。

快速选择算法是选择问题的另一种解法,其时间复杂度仅为 \(O(N)\) ,它借鉴了快速排序算法的思想。

/*
  快速选择算法
  返回A中第k大(其中l <= k <= h)的元素,会修改A本身
  比如,要找最小的元素:quickselect(A, 0, N-1, 0)
  要找最大的元素:quickselect(A, 0, N-1, N-1)
*/
int quickselect(int A[], int l, int h, int k) {
  if (l > k || l > h || k > h) {
    throw std::invalid_argument("argument error.");
  }

  if (l == h) {
    return A[l];
  }

  int p = lomuto_partition(A, l, h);
  if (k == p) {           // 已经找到,直接返回
    return A[k];
  } else if (k < p) {     // 去左边找
    return quickselect(A, l, p-1, k);
  } else {                // 去右边找
    return quickselect(A, p+1, h, k);   // 或者 return quickselect(A+p+1, 0, h-(p+1), k-(p+1));
  }
}

说明:快速选择算法尽管时间复杂度很小(为线性时间 \(O(N)\) ),但它也有缺点:会修改原始数据,不适合处理海量数据。

9.4.1 快速选择算法时间复杂度分析

快速选择算法的运行时间等于一个递归调用的运行时间加上花费在分割上的线性时间。

快速选择算法的最坏情况的时间复杂度和快速排序相同,也是 \(O(N^2)\) 。快速选择算法的“最好情况运行时间”和“平均运行时间”均为 \(O(N)\) 。其严格推导过程类似于快速排序的分析,可参考:《数据结构与算法分析——C语言描述(原书第2版)》,7.7.5节 快速排序的分析

这里,仅给出“枢纽元总是正好位于中间”这种特殊情况下的时间复杂度分析。在这种情况下,有:
\[T(N) = T(N/2) + c N\]
反复套用这个方程,有:
\[\begin{gathered}T(N/2) = T(N/4) + c N/2 \\ T(N/4) = T(N/8) + c N/4 \\ T(N/8) = T(N/16) + c N/8 \\ \vdots \\ T(2) = T(1) + c 2\end{gathered}\]
把所有上面这些公式加起来,有:
\[T(N) = T(1) + c N (1 + 1/2 + 1/4 + 1/8 + \cdots) < T(1) + 2cN\]
从而,在这种情况下 \(T(N) = O(N)\) 。

10 Timsort(后起之秀)

Timsort 算法是Tim Peters于2002年在Python中实现的一个排序算法。它结合了归并排序和插入排序算法,在实践应用中效果比较好。

相对于其它排序算法,Timsort算是后起之秀。从Python 2.3开始,Timsort是Python中的标准排序算法;从jdk 1.7开始,Arrays类的sort方法默认采用Timsort。

8 是Timsort的一个gif动画演示。本文不详细介绍Timsort。

sort_timsort.gif

Figure 8: Timsort

参考:
形式化方法的逆袭——如何找出Timsort算法和玉兔月球车中的Bug?:http://wrox.cn/article/100000653/

11 排序算法总结

9 是常见排序算法的一个简单总结。

sort_summary.jpg

Figure 9: Sort algorithm summary

参考:https://en.wikipedia.org/wiki/Sorting_algorithm


Author: cig01

Created: <2012-01-07 Sat 00:00>

Last updated: <2018-01-02 Tue 12:33>

Creator: Emacs 25.3.1 (Org mode 9.1.4)