1、计算机软件技术基础,教 师：曾晓东电 话：13679007201E_mail: ,5.2 排序,一、基本概念二、选择排序三、插入排序四、交换排序五、归并排序六、各种排序算法的比较,计算机软件技术基础,查找与排序,一、基本概念,1. 排序设有含n个记录的序列为 R1,R2,Rn ，其相应的关键字序列为 K1,K2,.,Kn 。现要求确定一种排序p1,p2,.pn, 使其关键字满足递增（或递减）的关系：Kp1Kp2Kpn（或Kp1Kp2 Kpn）使原序列成为一个按关键字有序的序列： Rp1,Rp2,Rpn ,计算机软件技术基础,查找与排序,一、基本概念,2.排序方法的稳定性若Ki=Kj(1in ,
2、1jn ,ij)，在排序前Ri领先于Rj ，排序后Ri仍领先于Rj ，则称此排序方法是稳定的；反之称为不稳定的。3. 排序的分类若排序时待排序记录存放在内存中进行排序，则称为内部排序；若待排序记录数量很大，在内存中一次不能容纳全部记录，需要在排序过程中对外存进行访问，则称为外部排序。4.基本操作1）对记录中关键字大小进行比较；2）将记录从一个位置移到另一个位置。,计算机软件技术基础,查找与排序,一、基本概念,5. 排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价的大略估算一般都按平均情况进行估算。对于
3、那些受对象排序码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。5. 算法执行时所需的附加存储 评价算法好坏的另一标准。,计算机软件技术基础,查找与排序,一、基本概念,7. 待排序的数据表使用顺序存储结构存储其数据类型定义如下：记录结点的类型定义：typedef structkeywordtype key;datatype data;RECORDNODE;待排序的数据表是RECORDNODE类型的数组struct RECORDNODE aMaxSize;,计算机软件技术基础,查找与排序,二、选择排序,选择排序是不断在待排序序列（无序区）中按记录关键字递增（或递减）次序选择记
4、录，放入有序区中，逐渐扩大有序区，直到整个记录区为有序区为止。其基本思想是: 每一趟 (例如第 i 趟, i = 1, 2, , n-1) 在后面 n-i 个待排序对象中选出排序码最小的对象, 作为有序对象序列的第 i 个对象。待到第 n-1 趟作完, 待排序对象只剩下1个, 就不用再选了。,计算机软件技术基础,查找与排序,二、选择排序,直接选择排序过程：在当前无序序列中选择一个关键字最小的记录，并将它和最前端的记录交换。重复上述过程，使记录区的前端逐渐形成一个由小到大的有序区。2) 基本步骤(1)在一组对象 aian 中选择具有最小关键字的对象；(2)若它不是这组对象中的第一个对象, 则将它
5、与这组对象中的第一个对象对调;(3)在这组对象中剔除这个具有最小关键字的对象。在剩下的对象ai+1an中重复执行第(1)、(2)步, 直到剩余对象只有一个为止。,计算机软件技术基础,查找与排序,最小者 08交换21,08,最小者 16交换25,16,最小者 21交换49,21,计算机软件技术基础,查找与排序,最小者 25*无交换,最小者 25无交换,各趟排序后的结果,计算机软件技术基础,查找与排序,1. 直接选择排序,3）算法void SelectSort(RECORDNODE a,int n)/*对记录数组a1:n进行直接选择排序*/int i,j,small;RECORDNODE swap
6、;for (i=1;iaj.key) small=j;if (small!=i)/*交换*/swap=asmall; asmall=ai; ai=swap;,计算机软件技术基础,查找与排序,1. 直接选择排序,4）算法分析算法由两层循环构成，外层循环表示共需进行n-1趟排序，内层循环需进行n-I次比较，也许会做一次交换，即记录移动次数最多为3。总的时间性能为 比较次数：n(n-1)/2 移动次数：最坏情况下为3(n-1)所以总的时间复杂度为：O(n2)空间复杂度为：O(1) 交换记录时用直接选择排序是一种不稳定的排序算法,计算机软件技术基础,查找与排序,二、选择排序,2. 堆排序1) 堆设有序
7、列 k1,k2,kn ，若满足：,则称该序列构成的完全二叉树是一个堆。 例如，有序列： 96，83，27，38，11，9 构成的完全二叉树如上图所示,它是一个堆。 易知堆顶元素为所有元素中的最小值或最大值,计算机软件技术基础,查找与排序,2. 堆排序,2）堆排序的过程由两部分组成： 将现有的序列构成一个堆 输出堆顶元素，重新调整元素，构成新的堆，直到堆空为止。3）堆的构造： 由所给序列生成对应的完全二叉树； 设完全二叉树a1.n中结点ak的左右子树均为堆，为构成以ak为根结点的堆，需进行调整。方法是将ak的值与其左右子树的根结点进行比较，若不满足堆的条件，则将ak与其左右子树中根结点大的交换，
8、继续进行比较，直到所有子树均满足堆的定义为止。,计算机软件技术基础,查找与排序,建立初始的最大堆,计算机软件技术基础,查找与排序,计算机软件技术基础,查找与排序,2. 堆排序,最大堆的向下调整算法void createHeap(RECORDNODE a,int p,int n)/*将ap:n建立为以ap为根的最大堆*/int i,j,k;i=p; j=2*i;a0=ai;/*ai暂存到a0中*/while(j=n)if(j=1;i-)createHeap(a,i,n);,计算机软件技术基础,查找与排序,2. 堆排序,4）堆排序由以下两个步骤进行： 由给定的无序序列构造最大堆； 最大堆堆顶a1具
9、有最大的关键字,将a1与an对调,把具有最大关键字的对象交换到最后,再对前面的n-1个对象,使用堆的调整算法Sieve(a,1,n-1),重新建立最大堆,具有次最大关键字的对象又上浮到a1位置。再对调a1和an-1,调用Sieve(a,1,n-2),对前n-2个对象重新调整，。如此反复执行，最后得到全部排序好的对象序列。这个算法即堆排序算法。,计算机软件技术基础,查找与排序,计算机软件技术基础,查找与排序,计算机软件技术基础,查找与排序,计算机软件技术基础,查找与排序,计算机软件技术基础,查找与排序,计算机软件技术基础,查找与排序,2. 堆排序,堆排序的算法Void HeapSort(RECO
10、RDNODE a,int n)/*使用堆排序算法对记录数组a1:n按关键字递增排序*/int i;for(i=n/2;i=1;i-) createHeap(a,i,n);/*建立初始最大堆*/for(i=n;i=2;i-)a0=a1; a1=ai;ai=a0;/*交换a1和aI*/createHeap (a,1,i-1);/*重建最大堆*/,计算机软件技术基础,查找与排序,计算机软件技术基础,查找与排序,2. 堆排序,5) 算法分析若设堆中有 n 个结点, 且 2k-1 n 2k, 则对应的完全二叉树有 k 层。在第 i 层上的结点数 2i-1 (i = 1, 2, , k)。在第一个形成初始
11、堆的 for 循环中对每一个非叶结点调用了一次堆调整算法createHeap(),因此该循环所用的计算时间为：,其中, i 是层序号, 2i-1 是第 i 层的最大结点数, (k-i)是第 i 层结点能够移动的最大距离。,计算机软件技术基础,查找与排序,2. 堆排序,第二个for循环中调用了n-1次createHeap( )算法, 该循环的计算时间为O(nlog2n)。因此, 堆排序的时间复杂性为O(nlog2n)。该算法的附加存储主要是在第二个for循环中用来执行对象交换时所用的一个临时对象。因此，该算法的空间复杂性为O(1)。堆排序是一个不稳定的排序方法。,计算机软件技术基础,查找与排序,
12、三、插入排序,插入排序是将当前无序区中最前端的记录插入到有序区中，逐渐扩大有序区，直到所有记录都插入到有序区中为止。1. 直接插入排序1)基本思想是 : 当插入第i (i 1) 个对象时, 前面的a0, a1 , , ai-1已经排好序。这时, 用ai的排序码与ai-1, ai-2, 的关键码顺序进行比较, 找到插入位置即将ai插入, 原来位置上的对象向后顺移。 为了减少查找关键码时的比较次数，可在有序区的前端a0处设一个监视哨，存放当前要插入的关键字。,计算机软件技术基础,查找与排序,各趟排序结果,21,25,49,25*,16,08,1 2 3 4 5 6,0 1 2 3 4 5 6,21
13、,25,49,25*,16,08,25,i = 2,0 1 2 3 4 5 6,21,25,49,25*,16,08,49,i = 3,计算机软件技术基础,查找与排序,21,25,49,25*,16,08,21,25,49,25*,16,08,i = 5,21,25,49,25*,16,08,i = 6,i = 4,25*,16,08,0 1 2 3 4 5 6,0 1 2 3 4 5 6,0 1 2 3 4 5 6,计算机软件技术基础,查找与排序,16,49,16,16,21,25,49,25*,16,08,1 2 3 4 5 6,21,25,49,25*,08,i = 4 时的排序过程,2
14、1,25,49,25*,完成,16,08,16,i = 5j = 4,i = 5j = 3,0 1 2 3 4 5 6,0 1 2 3 4 5 6,计算机软件技术基础,查找与排序,25,25*,16,16,21,25,49,25*,08,21,49,25*,08,21,25,49,25*,16,08,16,16,25,21,i = 5j = 2,i = 5j = 1,i = 5j = 0,16,0 1 2 3 4 5 6,0 1 2 3 4 5 6,0 1 2 3 4 5 6,计算机软件技术基础,查找与排序,三、插入排序,2）函数实现void straightInsert(RECORDNODE
15、 r,int n)/*使用直接插入排序法对数组a(1:n)排序*/for (i=2;i=n;i+)a0=ai; /*设置监视哨*/ j=i-1;while (a0.keyaj.key)aj+1=aj;j-;aj+1=a0;,计算机软件技术基础,查找与排序,三、插入排序,3) 算法分析设待排序对象个数为n, 则该算法的while循环执行n-1趟。关键码比较次数和对象移动次数与对象关键码的初始排列有关。最好情况下, 排序前对象已按关键码从小到大有序, 每趟只需与前面有序对象序列的最后一个对象比较1次, 移动2次对象, 总的关键码比较次数为 n-1, 对象移动次数为 2(n-1)。最坏情况下, 第
16、i 趟时第 i 个对象必须与前面 i 个对象都做关键码比较, 并且每做1次比较就要做1次数据移动。则总关键码比较次数KCN和对象移动次数RMN分别为,计算机软件技术基础,查找与排序,三、插入排序,在平均情况下的排序码比较次数和对象移动次数约为 n2/4。因此，直接插入排序的时间复杂度为 o(n2)。直接插入排序是一种稳定的排序方法。,计算机软件技术基础,查找与排序,三、插入排序,2. 折半插入排序1）与直接插入排序相比，除了采用的是折半查找寻找插入的位置外，其它类似。2）算法void BinarySort(RECORDNODE a,int n)for (i=2;i=low;j-) rj+1=r
17、j;rlow=r0;,计算机软件技术基础,查找与排序,三、插入排序,3) 算法分析折半查找比顺序查找查找快, 所以折半插入排序就平均性能来说比直接插入排序要快。它所需的关键码比较次数与待排序对象序列的初始排列无关, 仅依赖于对象个数。在插入第 i 个对象时, 需要经过 log2i +1 次关键码比较, 才能确定它应插入的位置。因此, 将 n 个对象(为推导方便, 设为 n=2k )用折半插入排序所进行的排序码比较次数为：,其记录移动的数目与直接插入排序相同因此，此算法的时间复杂度为O(n2)折半插入排序是一个稳定的排序算法,计算机软件技术基础,查找与排序,三、插入排序,3. 希尔排序1) 希尔
18、排序方法又称为缩小增量排序。2) 该方法的基本思想是 : 设待排序对象序列有 n 个对象, 首先取一个整数 gap s0.key) sj=sj-delse break;sj=s0;d=d/2;,计算机软件技术基础,查找与排序,3.希尔排序,4) 算法分析Gap的取法有多种。最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。knuth 提出取 gap = gap/3 +1。对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数。想要弄清排序码比较次数和对象移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。 Knuth利
19、用大量实验统计资料得出 : 当 n 很大时，排序码平均比较次数和对象平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。希尔排序是一种不稳定的排序方法,计算机软件技术基础,查找与排序,四、交换排序,交换排序是根据序列中两个结点关键字的比较结果，来对换在序列中的位置。算法的特点是将关键字较大的结点向序列的尾部移动，关键字较小的结点向序列的前部移动。基本思想是两两比较待排序对象的排序码,如发生逆序(即排列顺序与排序后的次序正好相反)，则交换之。直到所有对象都排好序为止。,计算机软件技术基础,查找与排序,四、交换排序,1. 冒泡排序
20、基本方法：设待排序对象序列中的对象个数为 n。最多作 n-1 趟, i = 1, 2, , n-1。在第 i 趟中从后向前，j = n, n-1, , i，顺次两两比较aj-1和aj。如果发生逆序，则交换aj-1和aj。1）过程：对无序表进行扫描，当发现相邻两个记录关键字逆序时就进行交换，第一次扫描后就将最大关键字记录沉到底部，而关键字较小的记录则像气泡一样逐渐上浮。然后对剩下的记录再进行扫描，直到某次扫描时不发生交换，则排序完成。,计算机软件技术基础,查找与排序,计算机软件技术基础,查找与排序,1. 冒泡排序,2)算法void BubbleSort(RECORDNODE a,int n)/*
21、使用冒泡排序算法，对记录数组a1:n排序*/int i,j;int exchange = 1;/*标志，记录是否有交换*/for(i=1;ii;j-)if(aj-1.keyaj.key)/*逆序*/a0=aj;aj=aj-1;aj-1=a0;/*交换*/ exchange = 1;/*标志置为1,有交换*/,计算机软件技术基础,查找与排序,1. 冒泡排序,算法也可写成：void BubbSort(RECORDNODE a,int n)int i;for (i=0;iaj.key) t=ai; ai=aj; aj=t; ,计算机软件技术基础,查找与排序,1. 冒泡排序,3) 算法分析第i趟对待排
22、序对象序列ai,aI+1,an进行排序, 结果将该序列中排序码最小的对象交换到序列的第一个位置(i), 其它对象也都向排序的最终位置移动。在个别情形, 对象可能在排序中途向相反的方向移动。最多做n-1趟冒泡就能把所有对象排好序。在对象的初始排列已经按关键字从小到大排好序时,此算法只执行一趟起泡,做n-1次关键字比较,不移动对象。这是最好的情形。最坏的情形是算法执行n-1趟起泡,第i趟 (1 i n) 做 n- i 次关键字比较, 执行 n-i 次对象交换。这样在最坏情形下总的关键字比较次数KCN和对象移动次数RMN为：,计算机软件技术基础,查找与排序,1. 冒泡排序,冒泡排序的平均时间复杂度为
23、O(n2)起泡排序需要一个附加对象以实现对象值的对换。起泡排序是一个稳定的排序方法。,计算机软件技术基础,查找与排序,四、交换排序,2. 快速排序1）基本思想快速排序是对冒泡排序的一种改进。基本思想是任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准,按照该对象的关键字大小,将整个对象序列划分为左右两个子序列： 左侧子序列中所有对象的关键字都小于或等于基准对象的关键字 右侧子序列中所有对象的关键字都大于基准对象的关键字基准对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。,计算机软件技术基础,查找
24、与排序,2. 快速排序,2）分割过程 选取表中一个元素ak（一般选取第一元素），令x=ak，称为控制关键字，用控制关键字和无序区中其余元素关键字进行比较。 设置两个指示器i,j，分别表示线性表第一个和最后一个元素位置。 将j逐渐减小，逐次比较aj与x，直到出现一个ajx，然后将ai移到aj位置。如此反复进行，直到i=j为止，最后将x移到aj位置，完成一趟排序。此时以x为界将原数组分割成两个子区。,计算机软件技术基础,查找与排序,计算机软件技术基础,查找与排序,计算机软件技术基础,查找与排序,2. 快速排序,3）算法：void QuickSort(RECORDNODE a,int low,int
25、 high)/*对记录数组alow:high进行快速排序*/if(low=high) return;t=alow; i=low; j=high;while(i=t.key) j-;/*从末端向中间搜索*/if(ij) ai=aj;while(ij,计算机软件技术基础,查找与排序,4）举例：设序列为46,55,13,42,94,5,17,70,计算机软件技术基础,查找与排序,2. 快速排序,5) 算法分析算法quicksort是一个递归的算法, 其递归树如图所示。,计算机软件技术基础,查找与排序,2. 快速排序,快速排序的趟数取决于递归树的高度。如果每次划分对一个对象定位后, 该对象的左侧子序列
26、与右侧子序列的长度相同, 则下一步将是对两个长度减半的子序列进行排序, 这是最理想的情况。在 n个元素的序列中,对一个对象定位所需时间为 O(n)。若设t(n) 是对 n 个元素的序列进行排序所需的时间, 而且每次对一个对象正确定位后, 正好把序列划分为长度相等的两个子序列, 此时, 总的计算时间为：T(n) cn + 2T(n/2) /* c 是一个常数*/ cn + 2( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4) 2cn + 4( cn/4 +2T(n/8) ) = 3cn + 8T(n/8) cn log2n + nT(1) = O(n log2n ),计算机软件
27、技术基础,查找与排序,2. 快速排序,可以证明, 函数quicksort的平均计算时间也是O(nlog2n)。实验结果表明: 就平均计算时间而言, 快速排序是所有内排序方法中最好的一个。快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。最大递归调用层次数与递归树的高度一致,理想情况为 log2(n+1) 。因此，要求存储开销为 O(log2n)。在最坏的情况, 即待排序对象序列已经按其关键字从小到大排好序的情况下, 其递归树成为单支树, 每次划分只得到一个比上一次少一个对象的子序列。总的关键字比较次数将达,因此，快速排序在最坏情况下的时间复杂度为O(n2) 快速排序是一种不稳定的排
28、序方法。,计算机软件技术基础,查找与排序,用第一个对象作为基准对象,快速排序退化的例子,计算机软件技术基础,查找与排序,2. 快速排序,其排序速度退化到简单排序的水平, 比直接插入排序还慢。占用附加存储(栈)将达到O(n)。改进办法: 取每个待排序对象序列的第一个对象、最后一个对象和位置接近正中的 3 个对象，取其关键字居中者作为基准对象。,用居中排序码对象作为基准对象,计算机软件技术基础,查找与排序,五、归并排序,1. 归并，是将两个或两个以上的有序表合并成一个新的有序表。对象序列a中两个有序表al am和am+1 an。它们可归并成一个有序表, 存于另一对象序列b的bl bn 中。这种归并
29、方法称为两路归并 (2-way merging)。设变量 i 和 j 分别是表al am和am+1 an的当前检测指针。变量 k 是存放指针。,计算机软件技术基础,查找与排序,五、归并排序,当 i 和 j 都在两个表的表长内变化时, 根据对应项的排序码的大小,依次把排序码小的对象排放到新表 k 所指位置中；当 i 与 j 中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表中。,计算机软件技术基础,查找与排序,五、归并排序,2. 归并排序归并排序算法就是利用两路归并过程进行排序的。其基本思想是：假设初始对象序列有 n 个对象，首先把它看成是 n 个长度为 1 的有序子序列 (归并项)，先做
30、两两归并，得到 n / 2 个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为1)；再做两两归并，如此重复，最后得到一个长度为 n 的有序序列。,计算机软件技术基础,查找与排序,五、归并排序,两路归并算法的函数实现void merge(int start,int end,int m,RECORDNODE a)/*将有序表a(start:m)和a(m+1:end)归并为一个新的有序表a(start:end)*/RECORDNODE tempMAXSIZE;int i,j,k;i=start;j=m+1;k=start;while(i=m/*临时表的内容存回到a中*/,计算机
31、软件技术基础,查找与排序,五、归并排序,归并排序的算法void MergeSort(RECORDNODE a,int n)/*对长度为n的数组a排序*/Int length,left,right;left=0;length=1;while(lengthN)right=min(n-1,left+2*length-1)/限制right的值，使其不越界Merge(left,right,length,a);if(right+lengthN) left=right+1;/右边还有待合并段elselength*=2;left=1;/从新开始下一趟排序,计算机软件技术基础,查找与排序,五、归并排序,计算机软
32、件技术基础,查找与排序,五、归并排序,3. 算法分析1) 时间复杂度在函数MergeSort中while循环将被执行log2n次在while循环中，将调用Merge函数n/(2length)次而在Merge函数中，将比较length次,故在while循环中，将比较O(n)次因此，此算法的时间复杂度为O(nlogn)2) 空间复杂度归并排序占用附加存储较多, 需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。3) 归并排序是一个稳定的排序算法,计算机软件技术基础,查找与排序,六、各种排序方法的比较,计算机软件技术基础,查找与排序,六、各种排序方法的比较, 原则1）待排序记录的
33、个数2）记录本身的大小3）关键字的分布情况4）对排序稳定性的要求5）现有语言工具条件等,计算机软件技术基础,查找与排序,六、各种排序方法的比较, 结论1）若待排序的记录数n较小（n50），则可采用插入排序或直接选择排序。且由于插入排序的移动次数较选择排序多，因此若记录本身较大时宜采用选择排序。2）若n较大，则应采用时间复杂度O(nlog2n)的排序方法，如快速排序或堆排序。当排序的关键字是随机分布时，快速排序的平均运行时间最短；堆排序只需1个辅助空间，且不会出现快速排序可能出现的最坏情况，但堆排序的建堆时间较长。3）若待排序记录按关键字基本有序，则宜采用插入排序或冒泡排序。,计算机软件技术基础,查找与排序,六、各种排序方法的比较,4）从方法的稳定性看，所有时间复杂度为O(n2)的排序方法是稳定的，而快速排序、堆排序等性能较好的排序方法是不稳定的。5）在一般情况下，待排序记录采用顺序存储结构，而当记录本身较大时，为避免耗费大量时间移动记录，可用链表作存储结构。6）当待排序记录经常进行插入、删除时，为避免大量移动记录，宜采用动态存储结构。,计算机软件技术基础,查找与排序,小结,1、理解两种基本操作：比较、移位 2、掌握：各种排序方法及其时间复杂度和空间复杂度,计算机软件技术基础,查找与排序,
