第8章 排序 8．1排序基本概念 8．2插入类排序 8．3交换类排序 8．4选择类排序 8．5归并排序 8．6基数排序 8．1排序基本概念 8．2插入类排序 8．3交换类排序 8．4选择类排序 8．5归并排序 8．6基数排序 8．7各类排序方法的比较 8．8外部排序

8. 1 排序基本概念 1.内排序与外排序: 内排序:数据对象全部存放在内存； 8. 1 排序基本概念 1.内排序与外排序: 内排序:数据对象全部存放在内存； 外排序:对象个数太多，不能同时存放在内存，根据需要，不断在内、外存间移动。

2.稳定排序与不稳定排序 假设Ki=Kj，排序前序列Ri领先于Rj； 稳定排序：排序后序列中Ri领先于Rj。 例， 3 15 8 8 6 9 排序后 3 6 8 8 9 15 稳定 排序后 3 6 8 8 9 15 不稳定

两种基本操作： (1)比较两个关键字的大小； (2)将记录从一个位置移动到另一个位置。 常见的存储表示方法： 向量结构 链表结构 记录向量与地址向量结合

8．2 插入类排序 在一个已排好序的记录子集的基础上，将下一个待排序的记录有序地插入到已排好序的记录子集中，直到所有待排记录全部插入为止。

8．2．1直接插入排序 当插入第i 个对象时，前面v[0], v[1], …, v[i-1]已经排好序。用v[i]的关键码与v[i-1], v[i-2], …的关键码顺序进行比较，找到插入位置即将v[i]插入，原来位置上的对象向后顺移。

各趟排序结果 49 25 25* 21 16 08 0 1 2 3 4 5 49 25 25* 25 21 16 i = 1 08 0 1 2 3 4 5 temp 49 49 25 25* 21 16 i = 2 08 0 1 2 3 4 5 temp

49 25 25* 25* 21 16 i = 3 08 0 1 2 3 4 5 49 25 25* 21 16 16 i = 4 08 0 1 2 3 4 5 temp 49 25 25* 21 16 i = 5 08 08 0 1 2 3 4 5 temp

49 25 25* 21 16 完成 08 0 1 2 3 4 5 i = 4 时的排序过程 49 i = 4 j = 3 16 25 25* 21 16 16 08 0 1 2 3 4 5 temp 49 49 i = 4 j = 2 16 25 25* 21 16 08 0 1 2 3 4 5 temp

i = 4 j = 1 49 16 25 25* 25* 21 16 08 0 1 2 3 4 5 i = 4 j = 0 49 16 25 25 25* 21 16 08 0 1 2 3 4 5 temp i = 4 j = -1 49 16 25 25* 21 21 16 08 0 1 2 3 4 5 temp

void InsSort(RecordType r[],int length) /*对数组r做直接插入排序，length为长度*/ { for(i=2;i<length;i++) {r[0]=x=r[i];j=i-1; /*将待插入记录存放x中*/ while(x.key<r[j].key)/*寻找插入位置*/ { r[j+1]=r[j];j=j-1;} r[j+1]=r[0]; /*待插入记录插入已排序的序列中*/ } }

算法分析 最好情况，排序前对象有序，每趟只需与有序对象序列的最后一个比较 ，共比较n-1次。 待排序的对象个数为n，该算法执行n-1趟。 最好情况，排序前对象有序，每趟只需与有序对象序列的最后一个比较 ，共比较n-1次。 最坏情况，第 i 趟时第 i 个对象必须与前面 i 个对象都做关键码比较，并且每做 1 次比较就要做 1 次移动。则总的比较次数KCN和移动次数RMN为：

时间复杂度为 o(n2)。 稳定排序。

8．2．2希尔排序 排序序列有 n 个对象，首先取一个整数 gap < n 作为间隔，将全部对象分为 gap 个子序列，所有距离为 gap 的对象放在同一个子序列中，对每一个子序列直接插入排序。然后缩小间隔 gap，取 gap = gap/2，重复，直到最后取 gap =1为止。

49 25 25* 21 16 08 0 1 2 3 4 5 i = 1 49 Gap = 3 25 25* 21 16 08 49 25 25* 21 16 08 49 25 25* 21 16 08

49 25* 25 21 16 08 0 1 2 3 4 5 i = 2 49 Gap = 2 25* 25 21 16 08 49 25* 25 21 16 08 49 25* 25 21 16 08

开始 gap 值较大，子序列中对象较少，排序速度较快；随着gap 值变小，子序列中对象逐渐变多，由于大多数已基本有序，所以排序速度仍然很快。 49 25* 25 21 16 08 0 1 2 3 4 5 i = 3 49 Gap = 1 25* 25 21 16 08 开始 gap 值较大，子序列中对象较少，排序速度较快；随着gap 值变小，子序列中对象逐渐变多，由于大多数已基本有序，所以排序速度仍然很快。

void ShellInsert(RecordType r[],int length，int delta) /*对数组r做一趟希尔排序,length为长度,dalta为增量*/ { int i; for(i=1+delta;i<=length;i++) /*l+delta为第一个子序列的第二个元素的下标*/ if(r[i].key<r[i-delta].key) { r[0]=r[i]; /*备份r[i]*/ for(j=i-delta;j>0&&r[0].key<r[j].key;j-=delta) r[j+delta]=r[j]; r[j+delta]=r[0]; }} ShellSort(RecordType r[],int length,int delta[],int delta_len) /*对数组r做希尔排序，length为长度*/ { int i; for(i=0;i<delta_len;++i) ShellInsert(r, length ,delta[i]); }

8.2.3 折半插入排序 void BinSort(RecordType r[]，int length) 8.2.3 折半插入排序 void BinSort(RecordType r[]，int length) /*对记录r进行折半插入排序，length为长度*/ { for(i=1;i<= length;++i) { x=r[i]; low=1;high=i-1; while(low<=high) /*确定插入位置*/ { mid=(low+high)/2; if(x.key<r[mid].key)high=mid-1; else low=mid+1; } for(j=i-1;j>=low;--j) r[j+1]=r[j] ; /*记录向后移动*/ r[low]=x ;/*插入记录*／}}

算法分析 插入一个元素比较的次数最大为折半判定树的深度，如插入第i个元素时，需log2i次，插入n-1个元素的平均比较次数为O(n log2n)。 与直接插入排序法相比，比较次数减少，数据移动次数并未改变，时间复杂度为O(n2)。稳定排序。

8．3 交换类排序 8．3．1冒泡排序 相邻数据两两比较，如果逆序就交换，一趟比较交换后，最后一个位置的数据必然有序，然后继续下一趟，如此往复，直到序列全部有序为止。

49 25 25* 21 16 08 0 1 2 3 4 5 49 i = 1 25 25* 21 16 08 chang=TRUE 49 i = 2 25 25* 21 16 08 chang=TRUE 49 i = 3 25 25* 21 16 08 chang=TRUE

设置一个标记change： 开始前，change= FALSE ， 发生交换令change =TRUE， 49 i = 4 25 25* 21 16 08 chang=FALSE 0 1 2 3 4 5 设置一个标记change： 开始前，change= FALSE ， 发生交换令change =TRUE， 通过判断change，确定是否结束。

时间复杂度为O(n2) 。稳定排序。 void BubbleSort(RecordType r[]，int length) /*对记录数组r做冒泡排序，length为长度*/ {n=length;change=TRUE; for(i=1;i<=n-1&&change;++i) { change=FALSE; for(j=1;j<=n-i;++j) if(r[j].key>r[j+1].key) {t=r[j];r[j]=r[j+1];r[j+1]=t;change=TRUE;}} } 时间复杂度为O(n2) 。稳定排序。

8.3.2 快速排序 取某个对象作基准，划分为左右两个子序列： 左侧子序列中所有对象的关键码小于或等于基准对象的关键码 右侧子序列中所有对象的关键码大于基准对象的关键码 然后对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。

i = 1 i = 2 i = 3 pivot 49 25 25* 21 16 08 0 1 2 3 4 5 pivot pivot 49 0 1 2 3 4 5 pivot pivot 49 25 i = 1 25* 21 16 08 pivot 49 i = 2 25* 25 21 16 08 49 i = 3 25* 25 21 16 08

快速排序算法： QKSort(RecordType r[ ]，int low，int high) /*对记录数组r[low．．high]用快速排序算法排序*/ { if(low<high) { pos=QKPass(r，low，high)； QKSort(r，low，pos-1)； QKSort(r，pos+l，high)； } } /*QKPass*/

一趟快速排序算法： int QKPass(RecordType r[],int left,int right) /*对r中的r[1eft]至r[right]部分进行一趟排序，得到基准的位置，使得排序后的结果满足其之后(前)的记录的关键字均不小于(大于)基准记录*/ {t=r[left]; /*选择基准记录*/ low=left;high=right; while(low<high) {while(low<high&&r[high].key>=t.key) /*high从右到左找小于t.key的记录*/ high--; if(low<high){r[low]=r[high];low++;} /*找到小于t.key的记录，则进行交换*/ while(low<high&&r[low].key<t.key) /*low从左到右找大于t.key*/ low++; if(low<high){r[high]=r[low];high--;} /*找大于t.key的记录，则交换*/ } r[low]=t; /*将基准记录保存到low=high的位置*/ return low; /*返回基准记录的位置*/ }/*QKPass*/

快速排序共需进行多少趟排序，取决于递归调用深度。 (1)最好情况：每趟将序列一分两半，正好在表中。同折半查找log2n，总的比较次数C(n)≤n+2C(n／2)。 (2)最坏情况：已经排好序，第一趟经过n-1次比较，第1个记录定在原位置，左部子表为空表，右部子表为n-1个记录。第二趟n-1个记录经过n-2次比较，第2个记录定在原位置，左部子表为空表，右部子表为n-2个记录，依此类推，共需进行n-1趟排序，其比较次数为： 执行次数为： T(n)≤Cn+2T(n／2)≤2n+4T(n／4)≤3n+4T(n／8)≤nlog2n+nT(1)≈O(n log2n) 其中Cn是常数，表示n个元素排序一趟所需时间。

8．4 选择类排序 8．4．1简单选择排序 第i趟简单选择排序是指通过n-i次关键字的比较，选出关键字最小的记录，并与第i个记录进行交换。

i = 0 i = 1 i = 2 初始 最小者 08 交换21,08 最小者 16 交换25,16 最小者 21 交换49,21 49 25* 21 16 08 0 1 2 3 4 5 49 最小者 08 交换21,08 i = 0 25 25* 21 16 08 49 最小者 16 交换25,16 i = 1 25 25* 21 16 08 49 最小者 21 交换49,21 25* 25 i = 2 21 16 08

i = 3 i = 4 最小者 25* 无交换 最小者 25 无交换 结果 各趟排序后的结果 49 25* 25 21 16 08 0 1 2 3 4 5 49 最小者 25 无交换 i = 4 25* 25 21 16 08 49 结果 25* 25 21 16 08 各趟排序后的结果

i =1时选择排序的过程 49 25 25* 21 16 08 0 1 2 3 4 5 49  25 i k j 49 25 25* 21 16 08 25*  25 i k j 49 25 25* 21 16 08 16 < 25 i k j

49 25 25* 21 16 08 0 1 2 3 4 5 21  16 i k j k 指示当前序列中最小者

简单选择排序算法： void SelectSort(RecordType r[],int length) /*对数组r做简单选择排序，length为长度*/ { n=length; for(i=1;i<n-1;++i) {k=i; for(j=i+1; j<n;++j) if(r[j].key<r[k].key)k=j； if(k!=i) {x=r[i]；r[i]=r[k]；r[k]=x；} } }/*SelectSort*/

算法分析 最好情况为正序排列，不需要移动记录。最坏情况为逆序排列，移动记录的次数最多3(n-1)。当i=1时，进行n-1次比较；当i=2时，进行n-2次比较，… ，共需要进行的比较次数是 时间复杂度为O(n2)。

8.4.2 堆排序 堆是完全二叉树，每个结点的关键字值均不小于（或不大于）左、右孩子结点的关键字值。分为大顶堆和小顶堆。

创建堆，取堆顶结点并把剩余结点调整成堆，继续…….，为堆排序。 完成两个操作： （1）把一个待排序的数据序列创建成一个堆。 （2）把取出堆顶的剩余结点调整成堆。

建立大顶堆 21 i i 21 1 1 2 2 25 49 25 49 3 4 5 3 4 5 25* 16 08 25* 16 08 21 25 49 25* 16 08 21 25 49 25* 16 08 初始关键码集合 i = 2 时的局部调整

i 21 49 1 1 2 2 25 49 25 21 3 4 5 3 4 5 25* 16 08 25* 16 08 21 25 49 25* 16 08 49 25 21 25* 16 08 i = 1 时的局部调整 i = 0 时的局部调整 形成最大堆

基于初始堆进行堆排序 最大堆中V[0] 与V[n]对调，最大关键码交换到最后，再对前面的n-1个对象，使用堆的调整算法FilterDown(0, n-1)，重新建立最大堆。结果具有次最大关键码的对象又上浮到堆顶，即V[0]位置。 再对调V[0]和V[n-1]，调用FilterDown(0, n-2)，对前n-2个对象重新调整，…。 如此反复，得到排序好的对象序列。

49 08 1 1 2 2 25 21 25 21 3 4 5 3 4 5 25* 16 08 25* 16 49 49 25 21 25* 16 08 08 25 21 25* 16 49 初始最大堆 交换 0 号与 5 号对象, 5 号对象就位

25 16 1 1 2 2 25* 21 25* 21 3 4 5 3 4 5 08 16 49 08 25 49 25 25* 21 08 16 49 16 25* 21 08 25 49 从 0 号到 4 号 重新 调整为最大堆 交换 0 号与 4 号对象, 4 号对象就位

25* 08 1 1 2 2 16 21 16 21 3 4 5 3 4 5 08 25 49 25* 25 49 25* 16 21 08 25 49 08 16 21 25* 25 49 从 0 号到 3 号 重新 调整为最大堆 交换 0 号与 3 号对象, 3 号对象就位

21 08 1 1 2 2 16 08 16 21 3 4 5 3 4 5 25* 25 49 25* 25 49 21 16 08 25* 25 49 08 16 21 25* 25 49 从 0 号到 2 号 重新 调整为最大堆 交换 0 号与 2 号对象, 2 号对象就位

16 08 1 1 2 2 08 21 16 21 3 4 5 3 4 5 25* 25 49 25* 25 49 16 08 21 25* 25 49 08 16 21 25* 25 49 从 0 号到 1 号 重新 调整为最大堆 交换 0 号与 1 号对象, 1 号对象就位

8．5 归并排序 归并排序是通过不断地把若干个较小的有序表合并成较大的有序表。 8．5 归并排序 归并排序是通过不断地把若干个较小的有序表合并成较大的有序表。 序列长度为n，n个长度为1的有序序列，从头开始两两合并，得到(int)((n+1)/2)个长度≤2的有序序列，对这些序列继续两两合并，如此往复，直到合并成一个有序序列为止，这种排序方法称为2-路归并排序。

例，序列 { 49 , 38 , 65 , 97 , 76 , 13 , 27 } 初始 [49] [38] [65] [97] [76] [13] [27] [27] 一趟归并 [65 97] [13 76] [38 49] 二趟归并 [38 49 65 97] [13 27 76] 三趟归并 [13 27 38 49 65 76 97]

8．6 基数排序 采用“分配”与“收集”的办法。 假设待排序数据序列的关键字K拆分成m个位： （K0，K1，…，Km-2，Km-1。

1、最高位优先法 按Km-1对序列排序，再按Km-2对序列排序，依次重复，最后K0对序列排序。 2、最低位优先法 按K0对序列排序，再按K1对序列排序，依次重复，最后按Km-1对序列排序。

基数排序的“分配”与“收集”过程 第一趟 614 738 921 485 637 101 215 530 790 306 第一趟分配（按最低位 i = 3 ） re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9] 790 101 215 530 921 614 485 306 637 738 fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9] 第一趟收集 530 790 921 101 614 485 215 306 637 738

基数排序的“分配”与“收集”过程 第二趟 530 790 921 101 614 485 215 306 637 738 第二趟分配（按次低位 i = 2 ） re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9] 738 306 215 637 101 614 921 485 790 530 fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9] 第二趟收集 101 306 614 215 921 530 637 738 485 790

基数排序的“分配”与“收集”过程 第三趟 101 306 614 215 921 530 637 738 485 790 第三趟分配（按最高位 i = 1 ） re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9] 637 790 101 215 306 485 530 614 738 921 fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9] 第三趟收集 101 215 306 485 530 614 637 738 790 921

算法分析 假设每个数据的关键字位数为d，每个关键字的取值范围为rd个非负整数，时间复杂度为O(d(n+rd))，其中每趟分配的时间复杂度为O(n)，每趟收集的时间复杂度为O(rd)，整个排序过程需要d趟分配与收集。另外，需要2rd个队列指针的辅助空间，由于采用链式存储结构，故还增加了n个指针域的空间。

8.7 各类排序方法的比较 性能: 时间复杂度和空间复杂度。 8.7 各类排序方法的比较 性能: 时间复杂度和空间复杂度。 对于时间复杂度为O(n2)的简单排序方法（包括直接插入排序法、折半插入排序法、简单选择排序法、冒泡排序法等）适用于待排序数据序列长度较小的情况，当待排序数据序列长度较大时，则应该使用希尔排序、快速排序或堆排序等。

8．8 外部排序 当待排序的对象数目特别多时，在内存中不能一次处理。必须把它们以文件的形式存放于外存，排序时再把它们一部分一部分调入内存进行处理。排序过程中不断地在内存与外存之间传送数据。

外排序的基本过程: 当对象以文件形式存放于磁盘上的时候，通常是按物理块存储的。 物理块也叫做页块，是磁盘存取的基本单位。 每个页块可以存放几个对象。操作系统按页块对磁盘上的信息进行读写。

结 束！