C语言学习排序详解.

《C语言学习排序详解.》由会员分享，可在线阅读，更多相关《C语言学习排序详解.（25页珍藏版）》请在金锄头文库上搜索。

1、1. 排序 1. 1 什么是排序,1. 什么是排序 将任一文件中的记录，通过某种方法整理成按关键字递增(或递减)次序排列的处理过程。 假如给定 n 个记录的文件为 ( R1，R2，Rn ) 对应的关键字为 ( K1，K2，Kn ) 则排序是确定如下一个排列 p1，p2，pn 使得 Kp1 Kp2 Kpn 从而得到一个有序文件 ( Rp1，Rp2，Rpn ),1 排序 1.1 什么是排序,2. 什么是排序的稳定性 假设在待排序的文件中，存在两个具有相同关键字的记录 R(i)与R(j)， 其中 R(i) 位于 R(j) 之前。在用某种排序法排序之后，R(i) 仍位于 R(j) 之前，则称这种排序方

2、法是稳定的；否则，称这种排序方法是不稳定的。 例如，给定数列 ( 10，25，22，42，25，30，18 ) 排序后，若为 ( 10，18，22，25，25，30，42 ) 则称此过程是稳定的排序； 排序后，若为 ( 10，18，22，25，25，30，42 ) 则称此过程是不稳定的排序。,1.6 排序 1.6.1 什么是排序,3. 排序方法 (1) 内部排序 若被排序的文件较小，则可以将文件记录全部放在内存中，适用于这种情况 的排序方法称为内部排序法。 (2) 外部排序 若被排序的文件很大，以致于不能同时将文件记录全部放在内存中，而需要 将部分或全部记录存放在外存储器(磁盘、磁带等)中，适

3、用于这种情况的排 序方法称为外部排序法。 4. 评价一个排序算法好坏的标准 (1) 对 n 个记录的文件排序所需比较关键字的次数； (2) 对 n 个记录的文件排序所需移动记录的次数； (3) 排序过程中所需的辅助存储空间的大小。 在下述讨论中约定：文件的存储结构采用顺序结构，即使用一维数组 R0n 中的 R1n表示 n 个记录的文件。,1.6.2 简单排序 一、冒泡排序,算法基本思想 设待排序的文件为(R1，R2，Rn),关键字为(R1.key，R2.key，Rn.key) 第 1 遍： 从 R(1) 开始，依次比较两个相邻记录的关键字 R(i).key 和R(i1).key (1，2，n1

4、)。若 R(i).keyR(i1).key，则交换相应记录 R(i) 和 R(i1)的存储位置；否则，不进行交换。 第1遍之后，n 个记录中关键字最大的记录移到了第 n 个位置上。 第 2 遍： 从 R(1) 开始，依次比较两个相邻记录的关键字 R(i).key 和R(i1).key (1，2，n2)。若 R(i).keyR(i1).key，则交换相应记录 R(i) 和 R(i1)的存储位置；否则，不进行交换。 第2遍之后，前 n1 个记录中关键字最大的记录移到了第 n1个位置上 继续进行下去，直到第 n1 遍之后，或者不需要再交换记录为止。,1.6.2 简单排序 一、冒泡排序,例： 第 1

5、遍 第 2 遍 第 3 遍 第 4 遍 k1 43 21 21 21 21 21 21 21 21 21 21 21 15 15 15 15 15 15 k2 21 43 43 43 43 43 43 43 15 15 15 15 21 21 21 21 21 21 k3 89 89 89 15 15 15 15 15 43 28 28 28 28 28 28 28 28 28 k4 15 15 15 89 28 28 28 28 28 43 43 43 43 43 43 43 k5 28 28 28 28 89 43 43 43 43 43 43 43 43 k6 43 43 43 43 4

6、3 89 89 89 89 比较次数为 543214,1.6.2 简单排序 一、冒泡排序,算法分析 (1) 最好情况: 待排序的文件已是有序文件，只需要进行 1 遍排序，共计比较关键字的次数为 minn1 不交换记录。 (2) 最坏情况: 要经过 n1 遍排序，所需总的比较关键字的次数为 max(n-1)+(n-2)+1 n(n-1)/2 交换记录的次数最多为n(n-1)/2 移动记录次数最多为3n(n-1)/2 只需要少量中间变量作为辅助空间，算法是稳定的,1.6.2 简单排序 一、冒泡排序,void BubbleSort(SeqList R) /R（ln)是待排序的文件，采用自下向上扫描，

7、对R做冒泡排序 int i，j； Boolean exchange； /交换标志 for(i=1;i=i；j-) /对当前无序区Rin自下向上扫描 if(Rj+1.keyRj.key) /交换记录 R0=Rj+1； /R0不是哨兵，仅做暂存单元 Rj+1=Rj； Rj=R0； exchange=TRUE； /发生了交换，故将交换标志置为真 if(!exchange) /本趟排序未发生交换，提前终止算法 return； /endfor(外循环) /BubbleSort,二、选择排序,算法基本思想 设待排序的文件为(R1，R2，Rn),关键字为(R1.key，R2.key，Rn.key) 第 1

8、遍： 在 n 个记录中, 选出具有最小关键字的记录，需要进行 n1 次比较。 第 2 遍： 在余下的 n1 个记录中，选出最小关键字的记录，需要进行 n2 次比较。 . . . 第 n1 遍： 在最后的 2 个记录中，比较 1 次选出最小关键字的记录。,二、选择排序,例. k1 k2 k3 k4 k5 k6 初始关键字： （43 89 21 43 28 15 ） 第 1 遍排序后： 15 （89 21 43 28 43 ） 第 2 遍排序后： 15 21 （89 43 28 43 ） 第 3 遍排序后： 15 21 28 （43 89 43 ） 第 4 遍排序后： 15 21 28 43 （8

9、9 43 ） 第 5 遍排序后： 15 21 28 43 43 89,二、选择排序,void sortArry(int a,int n) int i, j, t, k; for(i=0; in-1; i+) k=i; for(j=i+1; jn; j+) if(aj ak) k = j； t = ak; ak = ai; ai = t; ,二、选择排序,算法分析 在任何情况下，算法所需要的比较次数均为 n-1 ( n ) i=1 n(n-1)/2 交换记录次数最多为n-1，移动记录数最多为3(n-1)，在最好情况下，不移动记录。 选择排序只需少量的中间变量作为辅助空间。算法是不稳定的,三、插入

10、排序,算法基本思想 将待排序的记录插入到已排序的子文件中去，使得插入之后得到的子文件仍然是有序子文件。插入一个记录，首先要对有序子文件进行查找，以确定这个记录的插入位置。按查找方式的不同，插入排序又可以分为线性插入排序和折半插入排序，前者使用顺序查找，后者使用折半查找。 (一) 线性插入排序 设待排序的文件为(R1，R2，Rn),关键字为(R1.key，R2.key，Rn.key) 首先将初始文件中的记录R1看作有序子文件。 第1遍： 将R2插入这个有序子文件中：若R2的关键字小于R1的关键字，则R2插在 R1之前；否则，R2插在R1的后面。 第 2 遍： 将记录R3插入前面已有2个记录的有序

11、子文件中，得到3个记录的有序子文件。 以此类推，依次插入 R4，Rn。最后得到 n 个记录的升序文件。,三、插入排序,例1. 线性插入排序（K0为临时工作单元，又称“监视哨”） K0 K1 K2 K3 K4 K5 K6 初始关键字： 43 21 89 15 43 28 (43后移) 第 1 遍排序后： 21 ( 21 43 ) 89 15 43 28 (不后移) 第 2 遍排序后： 89 ( 21 43 89 ) 15 43 28 (89,43,21后移) 第 3 遍排序后： 15 ( 15 21 43 89 ) 43 28 (89后移) 第 4 遍排序后： 43 ( 15 21 43 43 89 ) 28 (89,43,43后移) 第 5 遍排序后： 28 ( 15 21 28 43 43 89 ),三、插入排序,算法分析： 在最坏的情况下，对n个记录线性插入排序大约需要n(n-1)/2次比较。只需少量的中间变量作为辅助空间。算法是稳定的,三、插入排序,(二) 折半插入排序 在插入排序过程中，因为由前面插入的记录已构成一个有序子文件，所以在插入Ri时，可以对这个有序子文件采用折半查找来确定Ri(2，3，n)的插入位置，以减少比较次数。这种插入排序称为折半插入排序。 算法分析 折半插入排序的比较次数比线性插入排序的比较次数少；移动记