第10章排序n.ppt

《第10章排序n.ppt》由会员分享，可在线阅读，更多相关《第10章排序n.ppt（103页珍藏版）》请在三一文库上搜索。

1、第十章 排序,10.1 概述,10.2 插入排序,10.3 快速排序(交换类）,10.4 选择排序,10.5 归并排序,10.6 基数排序,10.7 各种排序方法的综合比较,10.1 概 述,一、排序的定义,三、内部排序方法的分类,二、排序方法的稳定性能,一、什么是排序？,排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。,例如：将下列关键字序列,52, 49, 80, 36, 14, 58, 61, 23, 97, 75,调整为,14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,二、排序方法的稳定性能,1. 稳定的排序方法

2、指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。,排序之前 : Ri(K) Rj(K) ,排序之后 : Ri(K) Rj(K) ,例如：,排序前 ( 56, 34, 47, 23, 66, 18, 82, 47* ),若排序后得到结果 ( 18, 23, 34, 47, 47*, 56, 66, 82 ) 则称该排序方法是稳定的;,若排序后得到结果 ( 18, 23, 34, 47*, 47, 56, 66, 82 ) 则称该排序方法是不稳定的。,2. 对于不稳定的排序方法，只要能举出一个实例说明即可。,例如 : 对 4*, 3, 4, 2 进行快

3、速排序， 得到 2, 3, 4, 4* ,三、内部排序的方法,内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。,经过一趟排序,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,基于不同的“扩大” 有序序列长度的方法，内部排序方法大致可分下列几种类型：,插入类,交换类,选择类,归并类,1. 插入类,将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。,2. 交换类,通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,3. 选择类,从记录的无序子序列中“选择”关键字最小

4、或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,4. 归并类,通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。,10. 2 插 入 排 序,有序序列R1i-1,Ri,无序序列 Rin,一趟直接插入排序的基本思想：,有序序列R1i,无序序列 Ri+1n,实现“一趟插入排序”可分三步进行：,3将Ri 插入(复制)到Rj+1的位置上。,2将Rj+1i-1中的所有记录均后移 一个位置；,1在R1i-1中查找Ri的插入位置， R1j.key Ri.key Rj+1i-1.key；,直接插入排序（基于顺序查找）,希尔排序（基于逐趟缩小增量）,不同的具体

5、实现方法导致不同的算法描述,折半插入排序（基于折半查找）,一、直接插入排序,利用 “顺序查找”实现 “在R1i-1中查找Ri的插入位置”,算法的实现要点：,i =2,38,49,38,7 趟 排序,1 趟 排序,2 趟 排序,void InsertSort ( SqList + i ) if (L.ri.key L.ri -1.key) 在 R1 i-1中查找 RI / InsertSort,排序过程：先将序列中第 1 个记录看成是一个有序子序列， 然后从第 2 个记录开始，逐个进行插入，直至整个序列有序。, 的插入位置; 对于在查找过程中找到的那些关键字 不小于 Ri.key 的记录，在查找

6、的同 时实现记录向后移动； 插入 Ri ;,L.r0 = L.ri; / 复制为监视哨 L.ri = L.ri -1; for ( j = i - 2; L.r0.key L.r j .key; - - j ) L.r j + 1 = L.r j ; / 记录后移 L.r j + 1 = L.r0; / 插入到正确位置,对于在查找过程中找到的那些关键字不小于Ri.key的记录，并在查找的同时实现记录向后移动；,for (j=i-1; R0.keyRj.key; -j); Rj+1 = Rj,R0,j,Ri,j= i-1,上述循环结束后可以直接进行“插入”,插入位置,内部排序的时间分析：,实现内

7、部排序的基本操作有两个：,（2）“移动”记录。,（1）“比较”序列中两个关键字的 大小；,对于直接插入排序：,最好的情况（关键字在记录序列中顺序有序）：,“比较”的次数：,最坏的情况（关键字在记录序列中逆序有序）：,“比较”的次数：,0,“移动”的次数：,“移动”的次数：,时间效率： 因为在最坏情况下，所有元素的比较次数总和为（01n-1)O(n2)。其他情况下也要考虑移动元素的次数。 故时间复杂度为O(n2) 空间效率：仅占用1个缓冲单元O（1） 算法的稳定性：稳定,因为 R1i-1 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R1i-1中查找Ri的插入位置”，如此实现的插入排序

8、为折半插入排序。,二、折半插入排序,void BiInsertionSort ( SqList &L ) / BInsertSort,在 L.r1i-1中折半查找插入位置；,for ( i=2; i=L.length; +i ) / for,L.r0 = L.ri; / 将 L.ri 暂存到 L.r0,for ( j=i-1; j=high+1; -j ) L.rj+1 = L.rj; / 记录后移,L.rhigh+1 = L.r0; / 插入,low = 1; high = i-1; while (low=high) ,m = (low+high)/2; / 折半,if (L.r0.key

9、L.rm.key) high = m-1; / 插入点在低半区 else low = m+1; / 插入点在高半区,14 36 49 52 80,58 61 23 97 75,i,low,high,m,m,low,low,m,high,14 36 49 52 58 61 80,23 97 75,i,low,high,m,high,m,high,m,low,例如:,再如:,插入 位置,插入 位置,L.r,L.r,时间复杂度： T(n)=O(n),空间复杂度：S(n)=O(1),折半插入排序是稳定排序,仅减少了比较次数， 移动次数不变。,三、希尔排序（又称缩小增量排序）,基本思想：对待排记录序列先

10、作“宏观”调整，再作“微观”调整。,所谓“宏观”调整，指的是，“跳跃式” 的插入排序。 具体做法为：,将记录序列分成若干子序列，分别对每个子序列进行插入排序。,其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。,例如：将 n 个记录分成 d 个子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d ,例如：,16 25 12 30 47 11 23 36 9 18 31,第一趟希尔排序，设增量 d =5,11 23 12 9 18 16 25 36 30 47 31,第二趟希尔排序，

11、设增量 d = 3,9 18 12 11 23 16 25 31 30 47 36,第三趟希尔排序，设增量 d = 1,9 11 12 16 18 23 25 30 31 36 47,void ShellInsert ( SqList / 插入 / if / ShellInsert,void ShellSort (SqList /一趟增量为dltak的插入排序 / ShellSort,开始时d 的值较大，子序列中的对象较少， 排序速度较快；随着排序进展，d 值逐渐变 小，子序列中对象个数逐渐变多，由于前面 工作的基础，大多数记录已基本有序，所以 排序速度仍然很快。 时间效率：O(n(log2n

12、)2) 空间效率：O（1）因为仅占用1个缓冲单元 算法的稳定性：不稳定,算法分析：,076，129，256，301，438，694，742，751，863，937,076，301，129，256，438，694，742，751，863，937,256，301，694，076，438，863，742，751，129，937,以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行希尔排序（取d=5,3,1）算法的各趟排序结束时，关键字序列的状态。,256，301，751，129，937，863，742，694，076，438,第1趟 d=5,第

13、2趟 d=3,第3趟 d=1,10.3 快 速 排 序,一、起泡排序,二、一趟快速排序,三、快速排序,四、快速排序的时间分析,一、起泡排序,假设在排序过程中，记录序列R1n的状态为：,第 i 趟起泡排序,无序序列R1n-i+1,有序序列 Rn-i+2n,n-i+1,无序序列R1n-i,有序序列 Rn-i+1n,比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上,例：关键字序列 T=(21，25，49，25*，16，08），请按从小到大的顺序，写出冒泡排序的具体实现过程。,初态： 第1趟 第2趟 第3趟 第4趟 第5趟,21，25，49， 25*，16， 08 21，25，25*，16

14、， 08 ， 49 21，25， 16， 08 ，25*，49 21，16， 08 ，25， 25*，49 16，08 ，21， 25， 25*，49 08，16， 21， 25， 25*，49,void BubbleSort(Elem R , int n) while (i 1) / while / BubbleSort,i = n;,i = lastExchangeIndex; / 本趟进行过交换的 / 最后一个记录的位置,if (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeIndex = j; /记下进行交换的记录位置 /if,for (j

15、= 1; j i; j+),lastExchangeIndex = 1;,注意:,2. 一般情况下，每经过一趟“起泡”，“i 减一”，但并不是每趟都如此。,例如:,2,5,5,3,1,5,7,9,8,9,i=7,i=6,for (j = 1; j i; j+) if (Rj+1.key Rj.key) ,1,3,i=2,1. 起泡排序的结束条件为， 最后一趟没有进行“交换记录”。,算法评价,时间复杂度：,最好情况（正序）,比较次数：n -1 移动次数：0 T(n) = O(n),最坏情况（逆序）,比较次数： 移动次数：,T(n) = O(n2),空间复杂度：S(n) = O(1),稳定性：稳定

16、排序,二、一趟快速排序（一次划分）,目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。,致使一趟排序之后，记录的无序序列Rst将分割成两部分：Rsi-1和Ri+1t，且 Rj.key Ri.key Rk.key (sji-1) 枢轴 (i+1kt)。,s,t,low,high,设 Rs=52 为枢轴,将 Rhigh.key 和 枢轴的关键字进行比较，要求Rhigh.key 枢轴的关键字,将 Rlow.key 和 枢轴的关键字进行比较，要求Rlow.key 枢轴的关键字,high,23,low,80,high,

17、14,low,52,例如,R0,52,low,high,high,high,low,可见，经过“一次划分” ，将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75,在调整过程中，设立了两个指针： low 和high，之后逐渐减小 high，增加 low，并保证 Rhigh.key52，和 Rlow.key52,否则进行记录的“交换”。,int Partition (RedType R, int low, int high) / Partition,R0 = Rlow;

18、 pivotkey = Rlow.key; / 枢轴,while (lowhigh) ,while(low=pivotkey) - high; / 从右向左搜索,Rlow = Rhigh;,while (lowhigh / 从左向右搜索,Rhigh = Rlow;,Rlow = R0; return low;,三、快速排序,首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。,无 序 的 记 录 序 列,无序记录子序列(1),无序子序列(2),枢轴,一次划分,分别进行快速排序,void QSort (RedType & R, int s, int t ) /

19、 对记录序列Rst进行快速排序 if (s t-1) / 长度大于1 / QSort,pivotloc = Partition(R, s, t); / 对 Rst 进行一次划分,QSort(R, s, pivotloc-1); / 对低子序列递归排序，pivotloc是枢轴位置,QSort(R, pivotloc+1, t); / 对高子序列递归排序,void QuickSort( SqList / QuickSort,第一次调用函数 Qsort 时，待排序记录序列的上、下界分别为 1 和 L.length。,四、快速排序的时间分析,时间效率：O(nlog2n) 因为每趟确定的元素呈指数增加，

20、到目前为止快速排序是平均速度最好的一种排序方法。 空间效率：O（log2n）因为递归要用栈(存每层low，high和pivot) 稳 定 性： 不稳定 因为有跳跃式交换。,10.4 选择 排 序,简 单 选 择 排 序,堆 排 序,一、简单选择排序,假设排序过程中，待排记录序列的状态为：,有序序列R1i-1,无序序列 Rin,第 i 趟 简单选择排序,从中选出 关键字最小的记录,有序序列R1i,无序序列 Ri+1n,例：关键字序列T= （21，25，49，25*，16，08），请给出简单选择排序的具体实现过程。,原始序列： 21，25，49，25*，16，08,直接选择排序,第1趟 第2趟 第

21、3趟 第4趟 第5趟,08，25，49，25*，16，21 08，16, 49，25*，25，21 08，16, 21，25*，25，49 08，16, 21，25*，25，49 08，16, 21，25*，25，49,简单选择排序的算法描述如下：,void SelectSort (Elem R, int n ) / 对记录序列R1n作简单选择排序。 for (i=1; in; +i) / 选择第 i 小的记录，并交换到位 / SelectSort,j = SelectMinKey(R, i); / 在 Rin 中选择关键字最小的记录,if (i!=j) RiRj; / 与第 i 个记录交换,

22、时间性能分析,时间效率： O(n2)虽移动次数较少，但比较次数仍多。 空间效率：O（1）没有附加单元（仅用到1个temp) 算法的稳定性：不稳定,10.4.2 树形选择排序,思想：首先对 n 个记录的关键字进行两两比较，然后在其 中 n/2 个较小者之间再进行两两比较，直到选出最小关键字 的记录为止。可以用一棵有 n 个叶子结点的完全二叉树表示。,13,27,38,49,49,65,76,97,时间复杂度：由于含有 n 个叶子结点的完全二叉树的深度 为log2n+1，则在树形选择排序中中，除了最小关键字外，每 选择一个次小关键字仅需进行 log2n 次比较，故时间复杂度 为 O(nlog2n)

23、。,缺点： 1、与“”的比较多余； 2、辅助空间使用多。,二、堆排序,堆是满足下列性质的数列r1, r2, ，rn：,或,堆的定义:,(小顶堆),(大顶堆),解释：如果让满足以上条件的元素序列 （ r1, r2, ，rn ）顺次排成一棵完全二叉树，则此树的特点是：树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。,例：有序列T1=（08, 25, 49, 46, 58, 67）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判断它们是否 “堆”？,（大根堆）,（小根堆）,（小顶堆） （最小堆）,（大顶堆） （最大堆）,终端结点（即叶子）没

24、有任何子女，无需单独调整,步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。,例：关键字序列T= (21，25，49，25*，16，08），请建大根堆。,2. 怎样建堆？,解：为便于理解，先将原始序列画成完全二叉树的形式： 这样可以很清晰地从(n-1)/2开始调整。,完全二叉树的第一个非终端结点编号必为n/2 ！(性质5),21,i=3:,49,而且21还应当向下比较！,49大于08，不必调整； i=2: 25大于25*和16，也不必调整； i=1: 21小于25和49，要调整！,建堆是一个从下往上进行“筛选”的过程。,40,55,49,73,81,64

25、,36,12,27,98,例如: 排序之前的关键字序列为 (40,55,49,73,12,27,98,81,64,36)建为大根堆.,12,36,81,73,49,98,81,73,55,现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。,98,49,40,64,36,12,27,将无序序列建成一个堆，得到关键字最小（大）的记录；输出堆顶的最小（大）值后，将剩余的 n-1 个元素重又建成一个堆，则可得到 n 个元素的次小值；如此 重复执行，直到堆中只有一个记录为止，每个记录出堆 的顺序就是一个有序序列，这个过程叫堆排序。,3. 怎样进行整个序列的堆排序？,堆排序需

26、解决的两个问题： 1、如何由一个无序序列建成一个堆？ 2、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？,21,49,而且21还应当向下比较！,1、建堆,举例：关键字序列T= (21，25，49，25*，16，08），进行堆排序,2、对刚才建好的大根堆进行排序：,交换 1号与 6 号记录 r0 rn,08 25 21 25* 16 49,从 1 号到 5 号 重新 调整为最大堆,08,25,25*,08,从 1号到 4号 重新 调整为最大堆,16,25*,从 1 号到 3号 重新 调整为最大堆,从 1 号到 2 号 重新 调整为最大堆,4、堆排序算法分析：,时间效率： O(nlog2n)。

27、因为整个排序过程中需要调用n-1次堆顶点的调整，而每次堆排序算法本身耗时为log2n； 空间效率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。 稳定性： 不稳定。 优点：对小文件效果不明显，但对大文件有效。堆排序是一种速度快且省空间的排序方法。,10.5 归 并 排 序,归并排序的过程基于下列基本思想进行： 将两个或两个以上的有序子序列 “归并” 为一个有序序列。,在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列,归并为一个记录的有序序列。,有 序 序 列 Rln,有序子序列 Rlm,有序子序列 Rm+1n,这个操作对顺序表而言，是轻而易举的

28、。,void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 将有序的记录序列 SRim 和 SRm+1n / 归并为有序的记录序列 TRin / Merge,for (j=m+1, k=i; i=m , ,if (i=m) TRkn = SRim; / 将剩余的 SRim 复制到 TR,if (j=n) TRkn = SRjn; / 将剩余的 SRjn 复制到 TR,归并排序的算法,如果记录无序序列 Rst 的两部分 Rs(s+t)/2 和 R(s+t)/2+1t 分别按关键字有序， 则利用上述归并算法很容易将它们归并成整个记录序

29、列是一个有序序列。,由此，应该先分别对这两部分进行 2-路归并排序。,例如：,52, 23, 80, 36, 68, 14 (s=1, t=6), 52, 23, 80 36, 68, 14, 52, 2380, 52, 23, 52, 23, 52, 80,36, 6814,3668,36, 68,14, 36, 68, 14, 23, 36, 52, 68, 80 ,23,void Msort ( RcdType SR, RcdType else / Msort, ,m = (s+t)/2; / 将SRst平分为SRsm和SRm+1t,Msort (SR, TR2, s, m); / 递归

30、地将SRsm归并为有序的TR2sm Msort (SR, TR2, m+1, t); /递归地SRm+1t归并为有序的TR2m+1t,Merge (TR2, TR1, s, m, t); / 将TR2sm和TR2m+1t归并到TR1st,void MergeSort (SqList / MergeSort,二路归并排序算法分析：,时间效率： O(nlog2n),因为在递归的归并排序算法中，函数Merge( )做一趟两路归并排序，需要调用merge ( )函数 n/(2len) O(n/len) 次，而每次merge( )要执行比较O(len)次，另外整个归并过程有log2n “层” ，所以算法

31、总的时间复杂度为O(nlog2n)。 空间效率： O(n) 因为需要一个与原始序列同样大小的辅助序列。这正是此算法的缺点。 稳定性：稳定,10.6 基 数 排 序,基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。,多关键字的排序,链式基数排序,多关键字的排序,例：将右表所示的学生 成绩单按数学成绩 的等级由高到低排 序，数学成绩相同 的学生再按英语成 绩的高低等级排序。,105 A A 102 A B 104 B B 101 B C 108 C B 103 C D 106 D B 107 E A,特点：每个记录最终的位置由两个关键字 k1 k2 决定。,第二关键字

32、 K2,第一关键字 K1,我们将它称之为复合关键字，即多关键字 排序是按照复合关键字 的大小排序。,1. 什么是“多关键字”排序？实现方法？,例1：对一副扑克牌该如何排序？ 若规定花色和面值的顺序关系为： 花色： 面值：2 3 4 5 6 7 8 9 10 J Q K A 则可以先按花色排序，花色相同者再按面值排序； 也可以先按面值排序，面值相同者再按花色排序。,例2：职工分房该如何排序？ 我校规定：先以总分排序（职称分工龄分）；总分相同者，再按配偶总分排序，其次按配偶职称、工龄、人口等等排序。,以上两例都是典型的多关键字排序！,实现多关键字排序通常有两种作法:,最低位优先LSD法,最高位优先

33、MSD法,例：对一副扑克牌该如何排序？ 若规定花色为第一关键字（高位），面值为第二关键字（低位），则使用MSD和LSD方法都可以达到排序目的。 MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。 LSD方法的思路：先按面值分成13堆（每堆4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）。,想一想：用哪种方法更快些？,因为有分组，故此算法需递归实现。,讨论：是借用MSD方式来排序呢，还是借用LSD方式？,例：初始关键字序列T=（32, 13, 27, 32*, 19，33），请分

34、别用MSD和LSD进行排序，并讨论其优缺点。,法1（MSD）：原始序列：32,13,27,32*,19,33 先按高位Ki1 排序：（13,19）,27,（32,32*，33） 再按低位Ki2 排序 ： 13, 19, 27, 32, 32*,33,法2（LSD）： 原始序列：32,13,27,32*,19 ，33 先按低位Ki2排序： 32, 32*,13, 33, 27, 19 再按高位Ki1排序： 13, 19 ,27, 32, 32*,33,无需分组，易编程实现！,例：T=（02，77，70，54，64，21，55，11），用LSD排序。 分析： 各关键字可视为2元组；每位的取值范围是

35、：0-9；即基数radix 10 。因此，特设置10个队列，并编号为0-9。,计算机怎样实现LSD算法？,分配过程,收集过程,77,55,54，64,21,70,02,又称散列过程！,，11,小结：排序时经过了反复的“分配”和“收集”过程。当对关键字所有的位进行扫描排序后，整个序列便从无序变为有序了。,70,64,54,21,11,02,再次分配,再次收集,这种LSD排序方法称为：,基数排序,，77,，55,所用队列是顺序结构，浪费空间，能否改用链式结构？,用链队列来实现基数排序,链式基数排序,实现思路：,针对 d 元组中的每一位分量，把原始链表中的所有记录, 按Kij的取值，让 j = d,

36、 d-1, , 1， 先“分配”到radix个链队列中去； 然后再按各链队列的顺序，依次把记录从链队列中“收集”起来； 分别用这种“分配”、“收集”的运算逐趟进行排序； 在最后一趟“分配”、“收集” 完成后，所有记录就按其关键码的值从小到大排好序了。,二、链式基数排序,假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。,对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。,请实现以下关键字序列的链式基数排序： T=（61

37、4，738，921，485，637， 101，215，530，790，306）,例:,第一趟分配,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,614,738,921,485,637,101,215,530,790,306,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,原始序列静态链表：,r0,（从最低位 i = 3开始排序，f 是队首指针，e 为队尾指针）,第一趟收集（让队尾指针ei 链接到下一非空队首指针fi+1 即可）,r0,第一趟收集的结果：,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,614,738,921,485,637,101,215,

38、530,790,306,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,第二趟分配（按次低位 i = 2 ）,第二趟收集（让队尾指针ei 链接到下一非空队首指针fi+1 ）,r0,r0,第二趟收集的结果：,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,614,738,921,485,637,101,215,530,790,306,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,第三趟分配（按最高位 i = 1 ）,第三趟收集（让队尾指针ei 链接到下一非空队首指针fi+1 ）,r0,r0,提醒注意：,“分配”和“收集”的实际操作仅为修改链表中的指针和设置队

39、列的头、尾指针；,基数排序的时间复杂度为O(d(n+rd),其中：分配为O(n) 收集为O(rd)(rd为“基”) d为“分配-收集”的趟数,10.7 各种排序方法的综合比较,一、时间性能,1. 平均的时间性能,基数排序,时间复杂度为 O(nlog2n)：,快速排序、堆排序和归并排序,时间复杂度为 O(n2)：,直接插入排序、起泡排序和 简单选择排序,时间复杂度为 O(n):,二、空间性能,指的是排序过程中所需的辅助空间大小,1. 所有的简单排序方法(包括：直接插入、起泡和简单选择) 和堆排序的空间复杂度为O(1)；,2. 快速排序为O(log2n)，为递归程序执行过程中，栈所需的辅助空间；,

40、3. 归并排序所需辅助空间最多，其空间复杂度为 O(n);,4. 链式基数排序需附设队列首尾指针，则空间复杂度为 O(rd)。,三、使用场合,1、问题规模n50时，采用直接插入排序或简单选择排序。 2、若待排序的序列基本有序（正序）应采用直接插入、冒泡或快速排序。 3、当问题规模n比较大时，应使用时间复杂度为O(nlog2n)：快速排序、堆排序、归并排序。,4、本章算法，输入数据时存在一个向量中的，当记录规模比较大时，为避免大量的时间移动数据，可用链表作存储结构。插入排序、基数排序、归并排序都易在链表中实现；快速排序、堆排序不易在链表中实现。,1. 了解排序的定义和各种排序方法的特点。熟悉各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。,本章总结：,2. 掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。,按平均时间复杂度划分，内部排序可分为三类：O(n2)的简单排序方法，O(nlogn)的高效排序方法 和 O(dn)的基数排序方法。,3理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。,