第九章 排序 (Sort) 2007.9

主要内容 9.1 排序的基本概念 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 各种排序方法的比较 9.1 排序的基本概念 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 各种排序方法的比较 排序（Sorting）是数据处理中一种很重要的运算，同时也是很常用的运算，一般数据处理工作25%的时间都在进行排序。

9.1 排序的基本概念

排序的对象：表 排序的依据：关键字（key） 排序的顺序： 排序定义： 由一组记录组成的文件。 升序/降序 排序定义： 将一组记录按某关键字递增或递减排列的过程。 内部排序与外部排序： 文件是否整个存放于内存，排序时是否需要涉及内、外 存的数据交换。

算法的性能评价 比较次数、移动次数、数据规模、数据的初 始状态 辅助空间 时间复杂度： 空间复杂度： 稳定性 算法的复杂度 对于具有同一排序关键字的多个记录，若排序后，记 录的相对次序不变，则称此排序方法是稳定的，否则 称为不稳定的。 算法的复杂度

表的存储结构 typedef struct { char * no; char * name; int mark1; int mark2; int aver; } student; student class[50]; 数组 typedef struct { int key; datatype other; } rectype R[N]; 链表 索引表 学号 姓名 年龄 性别 99001 王晓佳 18 男 99002 林一鹏 19 99003 谢宁 17 女 99004 张丽娟 99005 周涛 20 99006 李小燕 16 学生档案表

基本的内部排序方法 插入 （ Insert ） 直接插入（Straight Insertion Sort） 希尔排序（Shell Sort） 交换（Swap） 冒泡排序 （Bubble Sort） 快速排序（Quick Sort） 选择 （Select） 直接选择 （ Straight Selection Sort） 堆排序 （Heap Sort） 归并（Merge Sort ）

9.2 插入排序

9.2 插入排序Insertion Sorting） 基本思想： 依次将无序表中的记录插入有序表的适当位置。 基本算法 直接插入排序（ Straight Insertion sort） 希尔排序 （Shell sort）

9.2.1 直接插入排序 1．直接插入排序的基本思想 n个待排序的元素看成为一个有序表和一个无序 表 9.2.1 直接插入排序 1．直接插入排序的基本思想 n个待排序的元素看成为一个有序表和一个无序 表 依次将各个数据插入已排序好的有序子表中。

例如，n=6，数组R的六个排序码分别为：17，3，25，14， 20，9。它的直接插入排序的执行过程如图所示。 1 2 3 4 5 初始状态 17 25 14 20 9 第1次插入 第2次插入 第3次插入 第4次插入 第5次插入

2．直接插入的算法实现 void insert_sort ( rectype R[] ) //待排序元素存于数组R[ ]，数据从R[1]起，R[0]有特别用处。 { int i, j; for ( i=2; i<n; i++) { R[0] = R[i]; j=i-1; while ( R[0].key < R[j].key ) { R[j+1] = R[j]; j - - ; } R[j+1] = R[0]; } //插入R[2]…R[n-1] //把待排序元素暂存于 R[0] // 顺序比较和移动

R[0]的作用：暂存R[i]；监视是否j<1 void insert-sort2 (rectype R[ ]) { int i, j; rectype t; // t 为中间变量 for ( i=2; i<n; i++) { x=R[i]; //把待排序元素赋给 x j=i-1; while ((j>=0)&& ( x.key<R[j].key)) { R[j+1]=R[j]; j - -; } // 顺序比较和移动 R[j+1]=x; }

3．直接插入排序的效率分析 从空间来看，它只需要一个元素的辅助空间，用于元素的位 置交换。 从时间分析， 首先外层循环要进行n-1次插入， 每次插入最少比较一次（正序），移动两次； 最多比较i次，移动i＋2次（逆序）（i=1，2，…，n-1）。 因此，直接插入排序的时间复杂度为O（n2）。 直接插入算法的元素移动是顺序的，该方法是稳定的。

9.2.2希尔排序 1．希尔排序的基本思想 希尔排序, 又称为“缩小增量排序”。是1959年由D.L.Shell提出来的。 该方法的基本思想是： 先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序， 待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。 因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上有较大提高。

2.希尔排序的算法 void shell_sort(int R[N+d1],int d[t]) { int I,j,k,h; rectype temp; for(i=0; i<d[0];i++) R[i].key = - maxint; k = 0; do { h=d[k]; /*取本趟增量*/ for ( i=h+d1; i<n+d1; i++) //按增量分组将数据插入有序区 { temp=R[i]; j = i-h; while ( temp.key < R[j].key) { R[j+h] = R[j]; j = j –h; } R[j+h] = temp; } K++； } while ( h!=1);

3．希尔排序的效率分析 虽然我们给出的算法是三层循环，最外层循环为 log2n数量级，中间的for循环是n数量级的，内循环远 远低于n数量级，因为当分组较多时，组内元素较少 ，此循环次数少；当分组较少时，组内元素增多， 但已接近有序，循环次数并不增加。因此，希尔排 序的时间复杂性在O（nlog2n）和O（n2 ）之间，大致 为O（n1.3）。 由于希尔排序对每个子序列单独比较，在比较时进 行元素移动，有可能改变相同排序码元素的原始顺 序，因此希尔排序是不稳定的。 如：4，9，7，6，5，4，1

9.3 交换排序（Exchange Sorting） 基本思想： 两两比较，不符次序即交换，直至无交换。 基本算法 冒泡排序（Bubble sort） 快速排序 （Quick sort）

9.3.1 冒泡排序 1．冒泡排序的基本思想 对序列从后向前（从n-1至0），依次比较相邻元素的排序 码，若发现逆序则交换。再次扫描序列，…，直至无交换 发生，排序完成。 第 i 趟排序后，将无序表中的最小元素放在R[i]。 冒泡排序名称的由来：使排序码较小的元素逐渐从后部移 向前部（从下标较大的单元移向下标较小的单元），就象 水底下的气泡一样逐渐向上冒。 2.冒泡排序的过程 如n=6，数组R的六个排序码分别为：17，3，25，14，20，9。 给出冒泡排序算法的执行过程。

3．冒泡排序的算法实现 因为排序的过程中，各元素不断接近自己的位置，所 以效率较直接插入排序要好。 如果一趟比较下来没有进行过交换，就说明序列有序 ，因此要在排序过程中设置一个标志exchange判断元 素是否进行过交换。从而减少不必要的比较。 exchange =0,无交换 exchange =1,有交换

void BubbleSort(SeqList R)    {//采用自下向上扫描，对R做冒泡排序      int i，j；     Boolean exchange； //交换标志      for(i=1;i<n;i++){ //最多做n-1趟排序        exchange=FALSE； //本趟排序开始前，交换标志应为假        for(j=n-1;j>=i；j--) //对当前无序区R[i..n]自下向上扫描         if(R[j+1].key<R[j].key) {//交换记录           R[0]=R[j+1]； //R[0]不是哨兵，仅做暂存单元           R[j+1]=R[j]；           R[j]=R[0]；           exchange=TRUE；//发生了交换，故将交换标志置为真          }        if(!exchange) //本趟排序未发生交换，提前终止算法              return；      } //endfor(外循环)     } //BubbleSort

4．冒泡排序的效率分析 若待排序的元素为正序，则只需进行一趟排序，比较 次数为（n-1）次，移动元素次数为0； 若待排序的元素为逆序，则需进行n-1趟排序，比较次 数为n(n-1)/2，移动次数为3n(n-1 )/2， 因此冒泡排序算法的时间复杂度为O（n2）。 由于其中的元素移动较多，所以属于内排序中速度较 慢的一种。 因为冒泡排序算法只进行元素间的顺序移动，所以是 一个稳定的算法。 改进方法：双向冒泡排序。

void maopao(int source[],int n) { int start=0,end=n-1; int t;    int i;    while(start<=end)/*如果还有元素没有确定其位置*/    {       for(i=start;i<end;i++)/*寻找剩余元素的最大数*/          if(source[i]>source[i+1])          {   t=source[i];     source[i]=source[i+1];    source[i+1]=t;          }       end--;/*找到最大数*/       for(i=end;i>start;i--)/*寻找剩余元素的最小元素*/            if(source[i]<source[i-1])            {   t=source[i];   source[i]=source[i-1]; source[i-1]=t;            }       start++;/*找到一个最小数*/    } }

9.3.2 快速排序 1．快速排序的基本思想 选一记录作为分界记录，通过一趟排序，交换，以分界 记录为界，将待排元素分成两部分，小的在前，大的在 后。 再分别对这两部分重复以上方法，直至分得的部分为0或 1个记录。

快速排序（Quick Sorting）是迄今为止所有内排序算法 中速度最快的一种。 快速排序是对冒泡排序的一种改进方法，算法中元素 的比较和交换是从两端向中间进行的，排序码较大的 元素一次就能够交换到后面单元，排序码较小的记录 一次就能够交换到前面单元，记录每次移动的距离较 远，因而总的比较和移动次数较少。

2.快速排序的过程 例如，给定排序码为：46，55，13，42，94，05，17，70，快速排序第一趟过程如图所示。 46 55 13 42 i j i, j 分界数据 46

快速排序第二趟过程 快速排序第三趟过程 17 05 13 42 46 94 55 70 i j i,j 94 17 13 05 17 42

从图可知，通过一次划分，将一个区间以基准值分成两个子区间，左子区间的值小于等于基准值，右子区间的值大于基准值。对剩下的子区间重复此划分步骤，则可以得到快速排序的结果。 2．快速排序的算法实现 下面给出快速排序算法的递归算法如下：

void quicksort(NODE array[],int start , int end) { int i , j; NODE mid; if (start>=end) return; i=start; j=end; mid=array[i]; while (i<j) { while (i<j && array[j].key>mid.key ) j--; if (i<j) { array[i] = array[j]; i++; } while (i<j && array[i].key<=mid.key) i++; if (i<j) { array[j]=array[i]; j--; } } //一次划分得到基准值的正确位置 array[i]=mid; quicksort(array,start,i-1); //递归调用左子区间 quicksort(array,i+1,end); }//递归调用右子区间

3．快速排序的效率分析 时间复杂度 若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点 数n与二叉树深度h应满足log2n<h<log2n+1 ，所以总的比较次数不会超过 (n+1) log2n。因此，快速排序的最好时间复杂度应为O（nlog2n）。 在理论上已证明，快速排序的平均时间复杂度也为O（nlog2n）。 若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是 空），则这时得到的二叉树是一棵单分枝树，得到的非空子区间包含有 n-i个(i代表二叉树的层数（1≤i≤n）元素，每层划分需要比较n-i+2次，所 以总的比较次数为（n2+3n-4）/2。因此，快速排序的最坏时间复杂度为 O(n2)。 空间复杂度 快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为 O（log2n），最坏的空间复杂度为O(n)。 稳定性 快速排序是一种不稳定的排序方法。

9.4 选择排序（Selection Sorting） 基本思想： 每次从无序表中选择最小（最大）的记录，放在有序表 的最后。 基本算法： 直接选择排序（Straight Selection Sorting） 堆排序（Heap Sorting）

9.4.1 直接选择排序 1．直接选择排序的基本思想 2.排序过程 依次从无序表中选出Key值最小的记录，放在有序表的最 后。 第i次从i~n-1中选取min，放到R[ i ]。 n个记录需通过n-1次选择，得到一个按排序码从小到大 排列的有序序列。 2.排序过程 给定n=8，数组R中的8个元素的排序码为：（8，3，2，1 ，7，4，6，5），则直接选择排序过程如图所示。

3.直接选择排序的算法 void selectsort( rectype R[ ] ) { int i,j,k; rectype temp; for ( i=0; i<n-1; i++ ) { k=i; for ( j=i+1; j<n; j++ ) if ( R[ j ].key < R[ k ].key) k=i; if ( k != i ) { temp=R[ i ]; R[ i ]=R[ k ]; R[ k ]=temp;} }

4．直接选择排序的效率分析 在直接 选择排序中，共需要进行n-1次选择和交换，每 次选择需要进行n-i次比较（1≤i≤n-1），而每次交换最多 需3次移动，因此，总的比较次数C=n(n-1)/2，总的移动 次数M=3(n-1)。由此可知，直接选择排序的时间复杂度 为O(n2)数量级，所以当记录占用的字节数较多时，通 常比直接插入排序的执行速度要快一些。 由于在直接选择排序中存在着不相邻元素之间的互换， 因此，直接选择排序是一种不稳定的排序方法。 例如，给定排序码为3，7，3，2，1， 排序后的结果为1，2，3，3，7。

9.4.2 堆排序 1．堆的定义 若序列k1，k2，…，kn，满足： ki ≤ k2i 且 ki ≤ k2i+1 （小根堆） 或 9.4.2 堆排序 1．堆的定义 若序列k1，k2，…，kn，满足： ki ≤ k2i 且 ki ≤ k2i+1 （小根堆） 或 ki ≥ k2i 且 ki ≥ k2i+1 （大根堆） 称k1，k2，k3，…，kn为一个堆。 判断以下序列是否为堆： (1) 2,9,5,10,14,7,13,12 (2) 2,10,5,9,13,7 (3) 9,4,5,2,3,1

2. 堆的判断 将序列按顺序排成一棵完全二叉树， 若二叉树的所有根结点值 <= 左右孩子的值称为小根堆 2. 堆的判断 将序列按顺序排成一棵完全二叉树， 若二叉树的所有根结点值 <= 左右孩子的值称为小根堆 若二叉树的所有根结点值 >= 左右孩子的值称为大根堆 ？判断以下序列是否为堆： (1) 2,9,5,10,14,7,13,12 (2) 2,10,5,9,13,7 (3) 9,4,5,2,3,1

3.如何建堆？/ 如何将序列调整为堆？ ----”筛选法” （小根堆）左右子树已是堆，将根沿着较小的分枝 往下筛，直至不能往下筛为止，使该树调整为堆。 例如，给定排序码： 49，38，65，97，76，13，27，49， 建立初始堆的过程如图。

49，38，65，97，76，13，27，49，

4. 堆排序的思想 堆的特点： 堆排序包含两个阶段: 1.建立初始堆 利用“筛选算法”将无序表调整为堆 2.利用堆进行排序 4. 堆排序的思想 堆的特点： 小根堆，根为选出来的最小元素 大根堆，根为选出来的最大元素 堆排序包含两个阶段: 1.建立初始堆 利用“筛选算法”将无序表调整为堆 2.利用堆进行排序 1)将堆顶与无序表的最后一个记录交换， 2) 利用“筛选算法”将无序表调整为堆。 3)转至1)继续。 小根堆，可实现逆序排序 大根堆，可实现正序排序 这样在序列的尾部构建有序表。

堆排序过程

堆排序对直接选择排序的改进 直接选择排序中， 但后面一趟的比较有可能在前一趟中已经做过， 由于没有保存，需要在后一趟排序时重新做过。 第一趟，从N个元素中选择一个元素需进行N-1次比较， 第二趟，从N-1个元素中选择一个元素需进行N-2次比较， 如此继续。 但后面一趟的比较有可能在前一趟中已经做过， 由于没有保存，需要在后一趟排序时重新做过。 在堆排序中，“调整为堆”的过程中保留了部分比 较结果，因此能减少比较次数。

5.堆排序的相关算法 筛选算法: Heapify函数 建立堆算法：BuildHeap函数 堆排序算法：HeapSort函数

6．堆排序的效率分析 时间复杂度： 在整个堆排序中，共需要进行n+n/2 -1次筛选运算，每次筛选运算进行双亲和孩子或兄弟结点的排序码的比较和移动次数都不会超过完全二叉树的深度，所以，每次筛选运算的时间复杂度为O(log2n)，故整个堆排序过程的时间复杂度为O(nlog2n)。 空间复杂度 堆排序所需辅助空间为1，供交换元素用，故空间复杂度为O（1）。 稳定性 堆排序是一种不稳定的排序方法。 如给定排序码：2，1，2，它的排序结果为：1，2，2。

9.5 归并排序 1.二路归并排序的基本思想: 将两个有序子区间（有序表）合并成一个有序子区间。 一次合并完成后，有序子区间的数目减少一半，而区间的长度增加一倍，当整个区间变为一个时，排序完成。

2. 二路归并排序过程 给定排序码46，55，13，42，94，05，17，70，

3．二路归并排序的效率分析 二路归并排序的时间复杂度等于归并趟数与每一趟时间复杂度的乘积。时间复杂度为O(nlog2n)。 利用二路归并排序时，需要利用与待排序数组相同的辅助数组作临时单元，故该排序方法的空间复杂度为O(n)，比前面介绍的其它排序方法占用的空间大。 由于二路归并排序中，每两个有序表合并成一个有序表时，若分别在两个有序表中出现有相同排序码，则会使前一个有序表中相同排序码先复制，后一有序表中相同排序码后复制，从而保持它们的相对次序不会改变。所以，二路归并排序是一种稳定的排序方法。

9.6 基数排序 借助多关键字排序的思想。 例：扑克牌的排序 关键步骤：分配、收集 两种方法： 最高位优先（MSD） 最低位优先（MSD）

9.7 各种内排序方法的比较和选择 排序方法 时间 空间 稳定性 直接插入 O（n2) O（1） 稳定 希尔排序 O（n1.3) 不稳定 冒泡排序 快速排序 O（nlog2n） O(log2n) 直接选择 堆排序 归并排序 O(n)

9.7.1 各种内排序方法的比较 1．从时间复杂度比较 从平均时间复杂度来考虑，直接插入排序、冒泡排序、直接选择排序是三种简单的排序方法，时间复杂度都为O(n2)，而快速排序、堆排序、二路归并排序的时间复杂度都为O(nlog2n)，希尔排序的复杂度介于这两者之间。 若从最好的时间复杂度考虑，则直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它的最好情形同平均情形相同。 若从最坏的时间复杂度考虑，则快速排序的为O(n2)，直接插入排序、冒泡排序、希尔排序同平均情形相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情形对直接选择排序、堆排序和归并排序影响不大。

2．从空间复杂度比较 归并排序的空间复杂度最大，为O(n)，快速排序的空间复杂度为O(log2n)，其它排序的空间复杂度为O（1）。 3.从稳定性比较 直接插入排序、冒泡排序、归并排序是稳定的排序方法，而直接选择排序、希尔排序、快速排序、堆排序是不稳定的排序方法。 4．从算法简单性比较 直接插入排序、冒泡排序、直接选择排序都是简单的排序方法，算法简单，易于理解，而希尔排序、快速排序、堆排序、归并排序都是改进型的排序方法，算法比简单排序要复杂得多，也难于理解。

9.7.2 各种内排序方法的选择策略 1．从时间复杂度选择 对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法。 2．从空间复杂度选择 尽量选空间复杂度为O（1）的排序方法，其次选空间复杂度为O(log2n)的快速排序方法，最后才选空间复杂度为O（n）二路归并排序的排序方法。

3．一般选择规则 （1） 当待排序元素的个数n较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。 （2)当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。 （3）当待排序元素的个数n大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。 （4)当待排序元素的个数n小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序为宜。 (5)当待排序元素的个数n小，对稳定性不做要求时，则采用直接选择排序为宜，若排序码不接近逆序，也可以采用直接插入排序。冒泡排序一般很少采用。