《《算法与数据结构》教学课件第8章 排序C语言描述（第2版）张乃孝编著》由会员分享，可在线阅读，更多相关《《算法与数据结构》教学课件第8章 排序C语言描述（第2版）张乃孝编著（73页珍藏版）》请在金锄头文库上搜索。
1、第第8章章 排序排序 8.1 基本概念8.2 插入排序8.3 选择排序8.4 交换排序8.5 分配排序8.6 归并排序（1）排序的确切定义： 假设R0, R1, , Rn-1是由n个记录组成的文件， K0, K1, , Kn-1是排序码集合，所谓排序是将记录 按排序码不增（或不减）的次序排列。 排序码可以是主关键码，也可以是次关键码。 （2）稳定排序和不稳定排序 假设Ki=Kj(0=i,j=n-1,ij)，且在排序前的序列 中Ri领先于Rj(即ij)，若在排序后的序列中Ri仍领 先于Rj，则称所用的排序方法是稳定的，否则是不 稳定的。8.1 8.1 基本概念基本概念 （3）排序中的基本操作：
2、比较关键码大小 移动记录（4）待排序的记录在排序过程中全部存放在内存的称为内排序，如果排序过程中需要使用外存的称为外排序。本章讨论的都是内排序的方法，但有些方法(特别是归并排序的思想)也可以用于外排序。排序方法：一、插入排序二、选择排序三、交换排序四、分配排序五、归并排序六、外部排序* 评价排序算法好坏的标准主要有两条第一是执行算法所需的时间；第二是执行算法所需要的附加空间；另外算法本身的复杂程度也是考虑的一个因素。由于排序是经常使用的一种运算，因此，排序的时间开销是算法好坏的最重要的标志。而排序的时间开销又可以用算法执行中的比较和移动次数来衡量。 基本方法：每步将一个待排序的记录按其关键字基
3、本方法：每步将一个待排序的记录按其关键字大小插入到前面已排序表中的适当位置，直到全部插大小插入到前面已排序表中的适当位置，直到全部插入完为止。入完为止。8.2 8.2 插入排序插入排序 8.2.1 8.2.1 直接插入排序直接插入排序 8.2.2 8.2.2 二分法插入排序二分法插入排序 8.2.3 8.2.3 表插入排序表插入排序 8.2.4 8.2.4 ShellShell排序排序 假设待排序的假设待排序的n n个记录个记录R0,R1,Rn-1R0,R1,Rn-1存放存放在数组中，在数组中，直接插入法直接插入法在插入记录在插入记录Ri(iRi(i=1,2n-1)=1,2n-1)时，记录集合
4、被划分为两个区间时，记录集合被划分为两个区间R0R0，Ri-1 Ri-1 和和 RiRi，Rn-1 Rn-1 ，其中，前一个子区间已经排好序，其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将排序码后一个子区间是当前未排序的部分，将排序码KiKi与与Ki-1Ki-1，Ki-2Ki-2，K0K0依次比较，找出应该插入依次比较，找出应该插入的位置，将记录的位置，将记录RiRi插入，原位置的记录向后顺移。插入，原位置的记录向后顺移。直接插入排序直接插入排序采用采用顺序存储结构顺序存储结构。 8.2.1 8.2.1 直接插入排序直接插入排序 Straight Insert Sort算法算
5、法8.1 8.1 直接插入排序直接插入排序 初始： 49 38 65 97 76 13 27 49 i=1: 38 49 65 97 76 13 27 49 i=2: 38 49 65 97 76 13 27 49 i=3: 38 49 65 97 76 13 27 49 i=4: 38 49 65 76 97 13 27 49 i=5: 13 38 49 65 76 97 27 49 i=6: 13 27 38 49 65 76 97 49 i=7: 13 27 38 49 49 65 76 97 稳定排序 typedeftypedef intint KeyTypeKeyType; ;typ
6、edeftypedef intint DataTypeDataType; ;typedeftypedef atructatruct KeyTypeKeyType key; key; DataTypeDataType info; info; RecordNodeRecordNode; ;typedeftypedef structstruct intint n; n; RecordNodeRecordNode *record; *record; SortObjectSortObject; ;算法算法8.1 直接插入排序直接插入排序void insertSort(SortObject * pvect
7、or)/ 按增序进行直接插入排序按增序进行直接插入排序 int i, j; RecordNode temp; for( i = 1; i n; i+ ) /* 依次插入记录依次插入记录R1, R2Rn-1 */ temp = pvector-recordi; j = i-1; while (temp.key recordj.key)&(j=0) ) /* 由后向前找插入位置由后向前找插入位置 */ pvector-recordj+1 = pvector-recordj; /* 将排序码大于将排序码大于ki的记录后移的记录后移 */ j-; if( j!=(i-1) ) pvector-reco
8、rdj+1 = temp; 算法分析： 空间效率：只需要一个记录的辅助空间。 时间效率：比较记录的次数: 最小: n-1次;最大: n(n-1)/2次移动记录的次数: 最小: n-1 最大: (n+4)(n-1)/2 i-1 i-1 pjcj =(1/i)(j+1) =(i+1)/2 j=0 j=0 n-1 (i+1)/2 = O(n2) i=1平均情况：比较O(n2)，移动O(n2) 由于插入排序的基本操作是在有序表中进行查找,而查找的过程是可以用折半查找来实现的。由此实现的排序称为二分法插入排序。8.2.2 8.2.2 二分法插入排序二分法插入排序 二分法插入排序必须采用顺序存储方式。 二
9、分法插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数 算法8.2 二分法插入排序(1) 1327384965769749 left=0 mid=3right=6(2) 1327384965769749left=4 mid=5 right=6(3) 1327384965769749left=4 mid=4 right=4 49right 已找到插入位置left=4(4) 1327384949657697图8.2 二分法插入排序示例 算法分析： 空间效率：同直接插入排序 时间效率：仅减少了比较次数，移动记录次数不变。 n log2i nlog2n i=1最坏的情况为n2/2，最好的
10、情况为2n，平均移动次数为O(n2) 8.2.3 8.2.3 表插入排序表插入排序4938659776132749 prenow3849659776132749 prenow3849659776132749 prenow3849659776132749 prenow类型声明如下：struct Node;typedef struct Node ListNode;struct Node KeyType key; DataType info; ListNode *next; ;typedef ListNode * LinkList;算法 8.3 表插入排序算法分析： 空间效率：每个记录中增加了一个n
11、ext字段，所以，辅助空间为S(n)=O(n)。 时间效率： 用链表方式减少记录移动的次数，时间复杂度仍为O(n2)。算法由条件p.key=now.key保证表插入排序是稳定的。 shell排序又称缩小增量排序(Diminishing Increment Sort)。 先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序“时，再对全体记录进行一次直接插入排序，就可以完成整个的排序工作。 shell排序的一个特点是：子序列的构成不是简单“逐段分割”，而是将相隔某个增量的记录组成一个子序列。 8.2.4 shell.2.4 shell排序排序非形式算法如下所示：
12、 increment=d; /* d0) 相距 increment的记录为一组 对每组进行插入排序； increment=increment/2; ;Shell排序的平均比较次数和平均移动次数都为O(n1.3)左右。Shell排序算法中增加了一个辅助空间temp，因此算法的辅助空间为S(n)=O(1)。Shell排序是不稳定的。 算法 8.4 shell 排序例题待排序序列为49,38,65,97,13,76,27,49，请用 Shell排序法排序。 原始序列 49 38 65 97 13 76 27 491. d=4 2. d=2 13 38 27 49 49 76 65 97 3. d=1
13、 13 38 27 49 49 76 65 97 排序结果 13 27 38 49 49 65 76 978.3 8.3 选择排序选择排序 基本思想是：每一趟在n-i+1个记录中选取关键码最小的记录作为有序序列中第i个记录。 8.3.1 8.3.1 直接选择排序直接选择排序 8.3.2 8.3.2 堆排序堆排序直接选择排序的时间复杂度： 移动：最好时：0最坏时：3（n-1) 比较：n(n-1)/2 总的时间复杂度：O(n2)稳定性：不稳定 首先在所有记录中选出排序码最小的记录，与第一个记录交换，然后在其余的记录中再选出排序码最小的记录与第二个记录交换，以此类推，直到所有记录排好序。 直接选择排
14、序的比较次数与文件初始状态无关。 8.3.1 直接选择排序直接选择排序49 38 65 97 49 13 27 76 13 38 65 97 49 49 27 76 13 27 65 97 49 49 38 76 13 27 38 97 49 49 65 7613 27 38 49 97 49 65 7613 27 38 49 49 97 65 7613 27 38 49 49 65 97 7613 27 38 49 49 65 76 9713 27 38 49 49 65 76 97 算法8.5 直接选择排序void selectSort(SortObject * pvector)/ 按递增
15、序进行选择排序 int i, j, k; RecordNode temp; for( i = 0; i n-1; i+ )/* 做n-1趟选择排序 */ k=i; for(j=i+1; jn; j+) /* 在无序区内找出排序码最小的记录Rk*/ if(pvector-recordj.keyrecordk.key) k=j; if(k!=i) /* 记录Rk与Ri互换 */ temp=pvector-recordi; pvector-record i= pvector-record k; pvector-record k=temp; 选择排序选择排序的主要操作是比较比较，要提高它的速度必须减少
16、比较的次数。而实际上如果能利用以前的比较结果则可以提高排序速度。 树形选择排序树形选择排序(Tree Selection Sort)，又称锦标锦标赛排序赛排序(Tournament Sort)。其方法是：首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复直到选出最小关键字的记录为止。然后对剩下的记录作同样的操作，选出具有次小关键字的记录。这个过程可以用一个完全二叉树来表示。如下图。8.3.2 8.3.2 堆排序堆排序(Heap Sort)(Heap Sort)133813386513274938659776132788树形选择排序示例树形选择排序示例 该方法的
17、时间复杂度为O(nlog2n)。缺点是使用了较多的辅助空间，并且和“最大值”进行了多余的比较。1964年Willioms提出了堆排序堆排序。 堆的定义：n个元素的序列k1,k2,kn当且仅当满足如下关系时，称之为堆。 ki k2iki k2i ki k2i+1 ki k2i+1( i = 1, 2, , n/2 ) 或 若将和此序列对应的一维数组看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左右孩子结点的值。由此，若序列 k1,k2,kn 是堆，则堆顶元素必为序列中n个元素的最小值（或最大值）。如果在输出堆顶的最小值后，使得剩余n-1个元素的序列重又
18、建成一个堆，则得到次小值。反复执行便能得到所有记录的有序序列，这个过程称为堆排序。 现在剩下两个问题： （1）如何由一个无序序列建成一个堆； （2）如何在输出堆顶元素后，调整剩余元素为 一个新的堆。 在输出堆顶元素后，用堆中最后一个元素替代，此时根结点的左右子树均为堆，则仅需自上而下进行调整即可。首先堆顶元素和其左右孩子的值比较，把最小的值（假设为左孩子结点）调到根结点的位置，由于左子树的根结点发生了改变，因此需要对左子树进行上述一样的调整，直至叶子结点。这个自堆顶至叶子的调整过程称为筛选。 从一个无序序列建堆的过程就是一个反复筛选的过程。若将此无序序列看成是一个完全二叉树，则最后一个非终端结
19、点就是第n/2 个元素，因此筛选只需从第n/2 个元素起，筛选到第1个元素（即堆顶元素）。如下页图。例：初始序列为 26，5，77，1，61，11，59，15，48，1926057701611159154819（1）初始完全二叉树26057701611159154819(2)调整序号为4的结点 26057748611159150119(3)调整序号为3的结点 26057748611159150119(4)调整序号为2的结点 26617748191159150105(5)调整序号为1的结点 77615948191126150105(6)调整序号为0的结点 05615948191126150177
20、(7)结点77与结点5互换615915191126050177(8)重建堆48(9)结点61与结点1互换592615191101056177(10)重建堆4801591519112605617748(11)结点59与结点05互换052615191101596177(12)重建堆4848261505110159617719(12)结点48与结点1互换(13)重建堆0126150511485961771926111505014859617719(15)结点26与结点1互换(16)重建堆0111150526485961771919110105264859617715(17)结点19与结点5互换(18
21、)重建堆0511011926485961771515110119264859617705(19)结点15与结点1互换(20)重建堆0111151926485961770511011519264859617705 堆排序适用于n值较大的情况。其比较次数为： 2n(log2n)。在最坏的情况下，时间复杂度也是O(nlogn)。且仅需一个记录大小的辅助空间。8.4 8.4 交换排序交换排序 两两比较待排序记录的排序码，交换不满足顺序要求的偶对，直到全部为止。 8.4.1 8.4.1 起泡排序起泡排序 8.4.2 8.4.2 快速排序快速排序 设待排序记录顺序存放在R0,R1,R2,Rn-1中，依次比
22、较（R0,R1），（ R1,R2）, (Rn-2,Rn-1),不满足顺序则交换，结果，最大者在Rn-1中。这叫一次起泡。此后，再对存放在R0,R1,R2,Rn-2中n-1个记录作同样处理,结果，最大者在Rn-2中。 。 n-1次起泡能完成排序。设置标志noswap表示本次起泡是否有交换，若无交换，表示排序完成。8.4.1 8.4.1 起泡排序起泡排序38 49 65 76 13 27 49 97 49 38 65 97 76 13 27 49 38 49 65 13 27 49 76 97 38 49 13 27 49 65 76 97 38 13 27 49 49 65 76 97 13 2
23、7 38 49 49 65 76 97 13 27 38 49 49 65 76 97 初始 1 2 3 4 5 6 算法8.7 起泡排序算法void bubbleSort(SortObject * pvector) int i, j, noswap; RecordNode temp; for(i=0; in-1; i+)/* 做n-1次起泡 */ noswap=TRUE; for(j=0; jn-i-1; j+) /* 置交换标志 */ if(pvector-recordj+1.keyrecordj.key) temp=pvector-recordj; /* 交换记录 */ pvector-
24、recordj=pvector-recordj+1; pvector-recordj+1=temp; noswap=FALSE; if(noswap) break; /本趟起泡未发生记录交换，算法结束 起泡排序的最坏时间复杂度为O(n2)，平均 时间复杂度为O(n2)。 起泡排序算法中增加一个辅助空间temp，辅助空间为S(n)=O(1)。 起泡排序是稳定的。 快速排序是对冒泡排序的改进，其基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 首先任意选取一个记录作为枢轴（或支点）(Pi
25、vot)，然后按下述原则重新排列其一记录：将所有关键字小于它的记录都安置在它之前，将所有关键字大于它的记录安置在它之后。于是以该枢轴记录所在的位置i作分界线，将整个序列分成两个子序列。这个过程称为一趟快速排序。然后分别对于两个子序列作同样的操作，重复这个过程，直到子序列不可再分就完成了记录的排序工作。8.4.2 8.4.2 快速排序快速排序一趟快速排序的具体做法是：附设两个指针low和high,它们的初值分别是一个序列的第一个和最后一个记录的位置，设枢轴记录的关键字为pivotKey，在首先从high所指位置起向前搜索直到第一个关键字小于pivotKey的记录和枢轴记录交换，然后从low所指位
26、置起向后搜索，找到第一个关键字大于pivotKey的记录和枢轴记录互相交换，重复交替这两步直到low=high为止。算法算法8.8 8.8 快速排序算法快速排序算法491386597761327492枢轴一般取第枢轴一般取第一个记录，并把一个记录，并把枢轴关键字放入枢轴关键字放入临时变量中，空临时变量中，空置枢轴所在位置置枢轴所在位置从从高端找一个比高端找一个比枢轴关键字小的枢轴关键字小的记录放入当前空记录放入当前空的低端位置的低端位置从从低端找一个比枢轴关键字大的低端找一个比枢轴关键字大的记录放入当前空的高端位置记录放入当前空的高端位置枢轴枢轴lowhigh临时变量：临时变量： pivotk
27、ey=491Low与与high标识标识记录调整的低端记录调整的低端与高端位置与高端位置highlow65high1397491Low =high枢轴应枢轴应到达的最终位置到达的最终位置27high交替进行上述两步交替进行上述两步记录重新排列的记录重新排列的策略：从表的两策略：从表的两侧向中间夹侧向中间夹lowhigh49 38 65 97 76 13 27 4927 38 13 49 76 97 65 4913 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 各趟排序结果算法算法8.8 快速排序算法快速排序算法void quickSort(SortOb
28、ject * pvector, int l, int r) int i, j; RecordNode temp; if(l=r) return; /* 只有一个记录或无记录，则无须排序只有一个记录或无记录，则无须排序 */ i=l; j=r; temp=pvector-recordi; while(i!=j)/* 寻找寻找Rl的最终位置的最终位置 */ while( (pvector-recordj.key=temp.key) & (ji) ) j - -; /从右向左扫描，查找第从右向左扫描，查找第1个排序码小于个排序码小于temp.key的记录的记录 if(irecordi+= pvect
29、or-record j; while( (pvector-recordi.keyi) ) i+; /从左向右扫描，查找第从左向右扫描，查找第1个排序码大于个排序码大于temp.key的记录的记录 if(irecordj-= pvector-recordi; pvector-recordi=temp;/* 找到找到Rl的最终位置的最终位置 */ quickSort(pvector,l,i-1); /* 递归处理左区间递归处理左区间 */ quickSort(pvector,i+1,r);/* 递归处理右区间递归处理右区间 */算法分析： 快速排序的记录移动次数不大于比较次数，所以，快速排序的最坏
30、时间复杂度应为O(n2)，最好时间复杂度为O(nlog2n)。为了改善最坏情况下的时间性能，可采用“三者取中”的规则，即在每一趟划分前，首先比较Rl.key、Rr.key和R.key的大小，取中间的记录与Rl交换。快速排序的平均时间复杂度是T(n)=O(nlog2n)。 算法需要一个栈空间实现递归。栈的大小取决于递归调用的深度，最多不超过n，若每次都选较大的部分进栈，处理较短的部分，则递归深度最多不超过log2n，所以快速排序的辅助空间为S(n)=O(log2n)。 快速排序是不稳定的。 8.5 8.5 分配排序分配排序 分配排序的思想是把排序码分解成若干部分，然后通过对各个部分排序码的分别排
31、序，最终达到整个排序码的排序。 8.5.1 8.5.1 概述概述 8.5.2 8.5.2 基数排序基数排序 多关键字的排序l假定扑克牌的次序为: 23A23A 23A23Al要将扑克牌排成上面的次序，通常采用的方法是先按花色分成4堆，并按花色的次序将4堆排好，然后分别对每一堆按面值从小到大整理有序。这种方法称为最高位优先法MSD（most significant digit first）8.5.1 8.5.1 概述概述l也可以先按面值分成13堆，并按面值大小将13堆排好，然后再将这13堆按花色分成4堆，4堆牌按花色从小到大合在一起，同样完成排序。这种方法称为最低位优先法LSD（lease si
32、gnificant digit first）。 一般情况下，假设文件F有n个记录F=(R0，R1，Rn-1) 且每个记录Ri的排序码中含有d个部分(ki0, ki1, kid-1)，则文件F对排序码(k0,k1,kd-1)有序是指文件中任意两个记录Ri和Rj(0ijn-1)满足词典次序有序关系(ki0, ki1, kid-1) (kj0, kj1, kjd-1) 其中k0称为最高位排序码，kd-1称为最低位排序码。实现分配排序，有两种方法第一种是先对最高位排序码k0排序，称为高位优先法。第二种是先对最低位排序码kd-1排序，称为低位优先法。 低位优先法比高位优先法简单，高位优先排序必须将文件逐
33、层分割成若干子文件，然后各子文件独立排序；低位优先排序不必分成子堆，对每个排序码都是整个文件参加排序，且可通过若干次“分配”和“收集”实现排序。但对Ki(0 = i = d-2)进行排序时，只能用稳定的排序方法。 下面将介绍的基数排序就是用排序码低位优先法的思想对排序码进行分解后排序的一种方法。 采用基数排序首先把每个排序码看成是一个d元组Ki=(Ki0, Ki1, Kid-1) 其中每个Ki都是集合C0，C1，Cr-1 (C0C1Cr-1)中的值，即C0KijCr-1(0in-1, 0jd-1)，其中r称为基数基数。排序时先按Kid-1从小到大将记录分配到r个堆中，然后依次收集，再按Kid-
34、2分配到r个堆中，如此反复，直到对Ki0分配、收集，得到的便是排好序的序列。 8.5.2 8.5.2 基数排序基数排序109278063930589184505269008083e0 e1 e2 e3 e4 e5 e6 e7 e8 e9f0 f1 f2 f3 f4 f5 f6 f7 f8 f9930063083184505008278109589269063930083184505278008109589269e0 e1 e2 e3 e4 e5 e6 e7 e8 e9505008109930063269278083184589f0 f1 f2 f3 f4 f5 f6 f7 f8 f900850
35、5109930063269278083184259e0 e1 e2 e3 e4 e5 e6 e7 e8 e9008063083109184269278505589930f0 f1 f2 f3 f4 f5 f6 f7 f8 f9063008083109184269278505589930时间复杂度O(d*n)其中d为关键字的位数，n为关键字的个数。稳定的排序方法。l基数排序算法中，时间耗费主要在修改指针上。一趟排序的时间为O(r+n)。总共要进行d趟排序，基数排序的时间复杂度是T(n)=O(d*(r+n)。当n较大、d较小，特别是记录的信息量较大时，基数排序非常有效。l基数排序中，每个记录中增加
36、了一个next字段，还增加了一个queue数组，故辅助空间为S(n)=O(n+r)。l基数排序是稳定的。算法分析：算法算法8.9 8.9 基数排序算法基数排序算法 归并的含义是将两个或两个以上的有序表合并成一个有序表。利用归并的思想就可以实现排序。假设初始的序列含有n个记录，可以看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复直到得到一个长度为n的有序序列为止。这种排序方法称为二路归并排序。8.6 8.6 归并排序归并排序8.6.1 8.6.1 内排序内排序例题初始序列为25, 57, 48, 37, 12, 82, 75,
37、29, 16，请用二路归并排序法排序。初始排序码25 57 48 37 12 82 75 29 16 / / / /第一趟归并后25 57 37 48 12 82 29 75 16 / /第二趟归并后25 37 48 57 12 29 75 82 16 /第三趟归并后12 25 29 37 48 57 75 82 16 /第四趟归并后12 16 25 29 37 48 57 75 82排序后的结果为12, 16, 25, 29, 37, 48, 57, 75, 82算法分析: 时间复杂度: O(nlog2n) 空间复杂度: 和待排记录等量的空间. 二路归并算法是稳定的. 一般情况下很少用于内部
38、排序.算法算法8.10 8.10 两组归并算法两组归并算法算法算法8.11 8.11 一趟归并算法一趟归并算法算法算法8.12 8.12 二路归并算法二路归并算法算法算法7.11 7.11 两组归并算法两组归并算法void merge(RecordNode r,RecordNode r1,int low,int m,int void merge(RecordNode r,RecordNode r1,int low,int m,int high)high) /*rlow /*rlow到到rmrm和和rm+1rm+1到到rhightrhight是两个有序文件是两个有序文件 * */ / int i
39、,j,k; int i,j,k; i=low; j=m+1; k=low; i=low; j=m+1; k=low; while( (i=m) & (j=high) ) while( (i=m) & (j=high) ) if(ri.key=rj.key) if(ri.key=rj.key) / /从两个有序文件中的第一个记录中选出小的记录从两个有序文件中的第一个记录中选出小的记录 r1k+=ri+; r1k+=ri+; else else r1k+=rj+; r1k+=rj+; while (i=m) r1k+=ri+; while (i=m) r1k+=ri+; /* /* 复制第一个文件
40、的剩余记录复制第一个文件的剩余记录 * */ / while (j=high) r1k+=rj+; while (j=high) r1k+=rj+; /* /* 复制第二个文件的剩余记录复制第二个文件的剩余记录 * */ / 算法算法7.12 7.12 一趟归并算法一趟归并算法/* /* 对对r r做一趟归并，结果放在做一趟归并，结果放在r1r1中中 * */ /void mergePass(RecordNode r,RecordNode r1,int n,int length)void mergePass(RecordNode r,RecordNode r1,int n,int length
41、) /* length /* length为本趟归并的有序子文件的长度为本趟归并的有序子文件的长度 * */ / int i, j; int i, j; i=0; i=0; while(i+2*length-1n) while(i+2*length-1n) merge(r,r1,i,i+length-1,i+2*length-1); merge(r,r1,i,i+length-1,i+2*length-1); /* /* 归并长度为归并长度为lengthlength的两个子文件的两个子文件* */ / i+=2*length; i+=2*length; if(i+length-1n-1) if
42、(i+length-1n-1) /* /* 剩下两个子文件，其中一个长度小于剩下两个子文件，其中一个长度小于 length */length */ merge(r,r1,i,i+length-1,n-1); merge(r,r1,i,i+length-1,n-1); else else for(j=i; jn; j+) for(j=i; jn; j+) /* /* 将最后一个子文件复制到数组将最后一个子文件复制到数组r1r1中中 * */ / r1j=rj; r1j=rj; 算法算法7.13 7.13 二路归并算法二路归并算法void mergeSort(SortObject * pvecto
43、r)void mergeSort(SortObject * pvector) RecordNode recordMAXNUM; RecordNode recordMAXNUM; int length; int length; length=1; length=1; while(lengthn) while(lengthn) mergePass(pvector-record,record,pvector-n,length); mergePass(pvector-record,record,pvector-n,length); /* /* 一趟归并，结果存放在数组一趟归并，结果存放在数组r1r1中
44、中* */ / length*=2; length*=2; mergePass(record,pvector-record,pvector-n,length); mergePass(record,pvector-record,pvector-n,length); /* /* 一趟归并，结果存放在数组一趟归并，结果存放在数组r r中中 * */ / length*=2; length*=2; l8.6.2 外排序（略） 排序方法最坏时间复杂度平均时间复杂度 辅助空间 稳定性直接插入排序O(n2) O(n2) O(1) 稳定的二分法插入排序O(n2) O(n2) O(1) 稳定的表插入排序O(n2
45、) O(n2) O(n) 稳定的Shell排序O(n1.3) O(n1.3) O(1) 不定的直接选择排序O(n2) O(n2) O(1)不稳定的堆排序O(nlog2n) O(nlog2n) O(1)不稳定的起泡排序O(n2) O(n2) O(1) 稳定的快速排序O(n2) O(nlog2n) O(log2n)不稳定的基数排序O(d(n+r) O(d(n+r) O(r+n) 稳定的归并排序O(nlog2n) O(nlog2n) O(n) 稳定的结论： （1）平均时间性能：以快速排序法最佳，但最坏情况下不如堆排序和归并排序；在n较大时，归并排序比堆排序快，但所需辅助空间最多。 （2）简单排序以直
46、接插入排序最简单，当下列中记录“基本有序“或n值较小时，是最佳的排序方法。因此常和其他排序方法结合使用。 （3）基数排序最适用于n值很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的”最高位关键字”均不同，则也可以先按“最高位关键字”不同将序列分成若干个子序列，而后用直接插入排序。 （4）从稳定性来看，基数排序是稳定的排序方法，大部分时间复杂度为O(n2)的简单排序法都是稳定的。然而，快速排序、堆排序和希尔排序等时间性能较好的排序都是不稳定的。一般来说，排序过程中的比较是在相邻的两个记录关键字之间进行的排序方法是稳定的。大多数情况下排序是按记录的主关键字进行的，则所有的排序方法是否稳定无关紧要。当排序是按记录的次关键字进行时，则应根据问题所需慎重选择。 本章讨论的大多数算法是在顺序存储结构上进行的，因此在排序过程中要进行大量的记录的移动。当记录很大（即每个记录所占的空间很大）时，记录移动所耗费的时间也很多，此时可采用静态链表作存储结构，如表插入排序，链式基数排序，以修改指针代替移动记录。但有些方法如快速排序法是无法实现表排序的，在这种情况下，可以进行“地址排序”，即另设一个向量指示需要记录，同时在排序过程中不移动记录而移动地址向量中相应分量的内容。作业:lP278 复习题 1，2，3l 算法题2，3，4
