《七章节排序.ppt》由会员分享,可在线阅读,更多相关《七章节排序.ppt(110页珍藏版)》请在三一文库上搜索。
1、1,第七章 排 序,7.1 排序的基本概念 7.2 插入排序 7.3 选择排序 7.4 交换排序 7.5 分配排序* 7.6 归并排序*,2,排序:将文件中一组记录(或数据)按其关键字的值以递增(或递减)的次序重新进行排列的操作过程。,原记录: R1,R2, , Rn 关键字: K1, K2, , Kn 新记录: Ri1, Ri2, , Rin 其中: Ki1=Ki2 =Ki3 = =Kin (递减),7.1、排序的基本概念,3,排序的对象: 文件,文件:是一组同类型记录构成的集合,记录:由不同类型的数据项(或域)构成的集合,排序的依据: 文件中记录的关键字项的关键字,关键字项:记录中特殊的数
2、据项(或域),关键字:关键字项(或域)中的值,4,关键字:,Typedef Struct student char number; char name ; int score; Student pm;,选取,Keytype key;,比较,Pi.key pj.key;,注意:,1、主关键字必须唯一,2、次关键字可以不唯一,5,排序的分类:,稳定排序: K i =K j , ij 不稳定排序:,排序后,R i 领先R j,R j 领先R i,排序后具有相同关键字的记录之间的 相对次序保持不变,6,排序的分类,1、内(部)排序: 排序中,整个文件都是在内存中进行处理。,2、外(部)排序: 排序中,
3、文件的数据要进行内、外存的交换。,涉及数据的内、外存的交换。,7,内排序的分类:,1、插入排序(直接插入排序、希尔排序),2、交换排序(冒泡排序、快速排序),3、选择排序(直接选择排序、堆排序),4、归并排序,5、分配排序,8,排序的性能比较:,评价排序算法的好坏的标准主要是两条:,1、排序所需的时间开销(主要是指执行 排序时对关键字的比较次数和记录的 移动次数),2、排序所需的附加空间的开销,9,7.2、插入排序,插入排序总的基本思想: 每次将一个待排序的记录,按其关键字大小插入到一个已经排好序(升序或降序)的文件中适当的位置,直到全部记录插入完毕为止。,7.2.1 直接插入排序 7.2.2
4、 二分法插入排序 7.2.3 表插入排序 7.2.4 Shell排序*,10,7.2.1 直接插入排序,基本思路:,假设待排序的n个记录R0,R1,Rn-1存放在数组中,直接插入法在插入记录Ri(i=1,2n-1)时,记录集合被划分为两个区间R0,Ri-1 和Ri,Rn-1 ,其中,前一个子区间已经排好序,后一个子区间是当前未排序的部分,将排序码Ki与Ki-1,Ki-2,K0依次比较,找出应该插入的位置,将记录Ri插入,原位置的记录向后顺移。直接插入排序采用顺序存储结构。,11,初始: 49 38 65 97 76 13 27 49 i=1: 38 49 65 97 76 13 27 49 i
5、=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 稳定排序,12,7.2.1 直接插入排序,排序步骤:1、查找插入点 2、进行插入,注意:1、此例实现的是( )排序?递增、递减 2、对应以上两步骤如何实现?,13,7.2.1 直接插入排序,typedef int KeyType; typedef int
6、 DataType; typedef struct KeyType key; /* 排序码字段 */ DataType info; /*记录的其它字段 */ RecordNode; typedef struct RecordNode recordMAXNUM; int n; /* n为文件中的记录个数,nMAXNUM */ SortObject;,14,具体算法如下:,void insertSort(SortObject * pvector) int i, j; RecordNode temp; for( i = 1; i n; i+ ) /* 依次插入记录R1, R2Rn-1 */ temp
7、 = pvector-recordi; j = i-1; while (temp.key recordj.key) ,15,算法性能分析,时间的开销,设有n个记录,则外循环要进行n1趟,而内循环则分两种情况:,若文件的记录本来就是按“正序”排列的,则此时总的关键字的比较次数和记录移动次数均最少,即:,Cmin = n1 = O(n) Mmin = n1= O(n),若文件的记录本来就是按“逆序”排列的,则此时总的关键字的比较次数和记录移动次数均最多,即:,Cmax = i =n(n-1)/ 2 = O(n2) Mmax =(i+1)=( n-1)(n+2)/ 2 = O(n2),平均情况:比较
8、O(n2),移动O(n2),16,空间的开销:只需要一个记录的辅助空间 S(n)= O(1),该算法是稳定的排序方法。,17,由于插入排序的基本操作是在有序表中进行查找,而查找的过程是可以用折半查找来实现的。由此实现的排序称为二分法插入排序。,7.2.2 二分法插入排序,二分法插入排序必须采用顺序存储方式。 二分法插入排序的比较次数与待排序记录的初始状态无关,仅依赖于记录的个数,18,(1) 13 27 38 49 65 76 97 49 left=0 mid=3 right=6 (2) 13 27 38 49 65 76 97 49 left=4 mid=5 right=6 (3) 13 2
9、7 38 49 65 76 97 49 left=4 mid=4 right=4 49right 已找到插入位置left=4 (4) 13 27 38 49 49 65 76 97,void binSort(SortObject * pvector) int i, j, left, mid, right; RecordNode temp; for( i = 1; i n; i+ ) temp = pvector-recordi; left = 0; right = i 1; /* 置已排序区间的下、上界初值 */ while (left recordmid.key) right=mid-1;
10、/* 插入元素应在左子区间 */ else left=mid+1; /* 插入元素应在右子区间 */ for(j=i-1; j=left; j-) pvector-recordj+1 = pvector-recordj; /* 将排序码大于ki的记录后移 */ if(left!=i) pvector-recordleft = temp; ,20,算法分析: 空间效率:同直接插入排序 时间效率:仅减少了比较次数,移动记录次数不变。 n log2i nlog2n i=1 最坏的情况为n2/2,最好的情况为2n,平均移动次数为O(n2),21,7.2.3 表插入排序,49,38,65,97,76,1
11、3,27,49 ,pre,now,38,49,65,97,76,13,27,49 ,pre,now,38,49,65,97,76,13,27,49 ,pre,now,38,49,65,97,76,13,27,49 ,pre,now,22,类型声明如下: struct Node; typedef struct Node ListNode; struct Node KeyType key; DataType info; ListNode *next; ; typedef ListNode * LinkList;,void listSort(LinkList * plist) ListNode *n
12、ow, *pre, *p, *q, *head; head=*plist; if(head-next=NULL |head-next-next=NULL) return; /* 为空链表或链表中只有一个结点 */ pre=head-next; now=pre-next; while( now!=NULL) q=head; p=head-next; while(p!=now ,24,算法分析: 空间效率: 每个记录中增加了一个next字段,所以,辅助空间为S(n)=O(n)。 时间效率: 用链表方式减少记录移动的次数,时间复杂度仍为O(n2)。,算法由条件p.key=now.key保证表插入排序
13、是稳定的。,25,shell排序又称缩小增量排序(Diminishing Increment Sort)。 先将整个待排记录序列分割成若干个子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序,就可以完成整个的排序工作。 shell排序的一个特点是:子序列的构成不是简单“逐段分割”,而是将相隔某个增量的记录组成一个子序列。,7.2.4 shell排序*,26,7.2.4 shell排序,基本思想:先取定一个小于n的整数d1作为第一个增量,把文件的全部记录分为d1个组,所有距离为d1倍数的记录放在同一组中,在各组内进行直接插入排序;然后,取第二个增量d2
14、d1重复上述分组和排序,直至所取的增量d t =1(d t d t-1 d2 d1),即所有记录放在同一组中进行直接插入排序为止。,27,举例说明,假设待排序的文件有10个记录,其关键字分别如下: 49,38,65,97,76,13,27,49,55,04,R,49,38,65,97,76,13,27,49,55,04,当 d1 = 5 时,0 1 2 3 4 5 6 7 8 9, 49,13 , 38,27 , 65,49 , 97,55 , 76,04 ,28,举例说明,第一趟排序的结果,R,13,27,49,55,04,49,38,65,97,76,当 d1 = 5 时,0 1 2 3
15、4 5 6 7 8 9,29,举例说明,第二趟排序,R,13,27,49,55,04,49,38,65,97,76,当 d2 = 3 时,0 1 2 3 4 5 6 7 8 9, 13,55,38,76 , 27,04,65 , 49,49,97 ,30,举例说明,第二趟排序的结果,R,13,04,49,38,27,49,55,65,97,76,当 d2 = 3 时,0 1 2 3 4 5 6 7 8 9,31,举例说明,第三趟排序,R,13,04,49,38,27,49,55,65,97,76,当 d1 = 1 时,0 1 2 3 4 5 6 7 8 9,32,举例说明,第三趟排序的结果,R
16、,04,13,27,38,49,49,55,65,76,97,当 d1 = 1 时,0 1 2 3 4 5 6 7 8 9,33,Shell排序的平均比较次数和平均移动次数都为O(n1.3)左右。 Shell排序算法中增加了一个辅助空间temp,因此算法的辅助空间为S(n)=O(1)。 Shell排序是不稳定的。,34,7.3 选择排序,选择排序基本思想: 每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序好的子文件(有序区)的最后,直到全部记录排序完毕。,7.3.1 直接选择排序 7.3.2 堆排序*,35,7.3.1 直接选择排序,基本思想: 假设待排序的文件记录存放在数组R n 中
17、。 第 i 趟排序时,R0到Ri-1是有序区,则: 在当前无序区Ri到Rn-1中选出关键字最小的记录Rk;将它与无序区中第一个记录Ri 交换, 使得R0到Ri变成新的有序区(其中1 i n-1)。 依次类推,直到n-1趟排序完毕后,则文件变为有序。,36,举例说明,假设有如下记录依次存于R中,其对应关键字如下,用选择排序法进行排序,49,38,65,97,76,13,27,49,37,初始化及第一趟排序,49,38,65,97,76,13,27,49,i,k,k,0 1 2 3 4 5 6 7,13,49,0,1,j,5,38,49 38 65 97 49 13 27 76 13 38 65
18、97 49 49 27 76 13 27 65 97 49 49 38 76 13 27 38 97 49 49 65 76 13 27 38 49 97 49 65 76 13 27 38 49 49 97 65 76 13 27 38 49 49 65 97 76 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97,39,直接选择排序算法,void selectSort(SortObject * pvector) int i, j, k; RecordNode temp; for( i = 0; i n-1; i+ ) /* 做n-1趟选择排序
19、*/ 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; ,40,直接选择排序的性能分析,直接选择排序的时间复杂度: 移动:最好时:0 最坏时:3(n-1) 比较:n(n-1)/2 总的时间复杂度:O(n2) 稳定性:不稳定,41,选择排序的主要操作是比较,要提高它
20、的速度必须减少比较的次数。而实际上如果能利用以前的比较结果则可以提高排序速度。 树形选择排序(Tree Selection Sort),又称锦标赛排序(Tournament Sort)。其方法是:首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进行两两比较,如此重复直到选出最小关键字的记录为止。然后对剩下的记录作同样的操作,选出具有次小关键字的记录。这个过程可以用一个完全二叉树来表示。如下图。,7.3.2 堆排序(Heap Sort),42,11,23,11,70,23,18,11,70,73,23,18,68,69,93,11,找最小值比较 7 次,43,18,23,18,70
21、,23,18,68,70,73,23,18,68,69,93,找次小值比较 3 次,44,结论:树型选择排序可减少关键字比较次数,最小值需经过 n-1 次比较,次小值需经过 log2n 次比较,堆排序是对树型选择排序的进一步改进,45,该方法的时间复杂度为O(nlog2n)。缺点是使用了较多的辅助空间,并且和“最大值”进行了多余的比较。1964年Willioms提出了堆排序。 堆的定义:n个元素的序列k1,k2,kn当且仅当满足如下关系时,称之为堆。 ki k2i ki k2i ki k2i+1 ki k2i+1 ( i = 1, 2, , n/2 ),或,46,例如:若关键字序列:10,15
22、,56,25,30,70建立成 如下的存储结构且能用一个完全二叉树来描述, 则该序列就是一个堆。,10,15,56,25,30,70,10 15 56 25 30 70,47,堆的描述:,完全二叉树的顺序存储序列,1、所有结点关键字的值均小于(或大于)其左、右孩子。,2、二叉树中任一子树也是堆。,3、根结点即最小(大)值。,48,小根堆:堆中根结点(称为堆顶)的关键字最小。,大根堆:堆中根结点(称为堆顶)的关键字最大。,堆排序就是利用小(大)根堆来选取当前无序区中关键字最小(最大)的记录来实现排序的。,49,堆排序的基本思想,1、将N个记录的序列建成堆。,(以大根堆为例加以说明),2、将堆顶(
23、最小值)和堆中最后一个记录交换。,3、将前面n-1个记录重新调整为新堆。,4、重复2、3,直到堆中只有一个记录。,50,具体算法如下:,要将无序区的记录数组调整为一个大根堆,必须把这完全二叉树中以每个结点为根的子树都调整为大根堆。 在完全二叉树中,所有序号i n/2 的结点都是叶子,只需依次将以序号 n/2 , n/2 -1 , ,1 的结点作为根的子树都调整为大根堆即可。 若已知结点Ri的左右子树已是堆,要将以Ri为根的完全二叉树也调整为堆则用筛选法。,51,举例说明(用堆排序方法建立升序排序),假设关键字序列为: 42,13,24,91,23,16,05,88 (n=8) 用完全二叉树表示
24、并存储如下:,42,13,91,23,24,16,05,88,42 13 91 23 24 16 05 88,不是堆,52,第一趟排序及堆的建立,42,13,91,23,24,16,05,88,42 13 91 23 24 16 05 88,无序区长度为n=8,则筛选开始序号为 i=4,53,第一趟排序及堆的建立,42,13,91,88,24,16,05,23,42 13 91 88 24 16 05 23,无序区长度为n=8,则筛选开始序号为 i=4,54,第一趟排序及堆的建立,42,13,91,88,24,16,05,23,42 13 91 88 24 16 05 23,接着继续筛选,则序
25、号减1为 i=3,55,第一趟排序及堆的建立,42,13,91,88,24,16,05,23,42 13 91 88 24 16 05 23,然后继续筛选,则序号减1为 i=2,56,第一趟排序及堆的建立,42,88,91,13,24,16,05,23,42 88 91 13 24 16 05 23,在筛选中由于子树不为堆,则子树要调整,57,第一趟排序及堆的建立,42,88,91,23,24,16,05,13,42 88 91 23 24 16 05 13,在筛选中由于子树不为堆,则子树要调整,58,第一趟排序及堆的建立,42,88,91,23,24,16,05,13,42 88 91 23
26、 24 16 05 13,继续筛选,则序号又减1为 i=1,59,第一趟排序及堆的建立,91,88,42,23,24,16,05,13,91 88 42 23 24 16 05 13,继续筛选,则序号又减1为 i=1,60,第一趟排序及堆的建立的结果,91,88,42,23,24,16,05,13,91 88 42 23 24 16 05 13,大根堆,61,第一趟排序及堆的建立的结果,13,88,42,23,24,16,05,91,13 88 42 23 24 16 05 91,这时,将堆顶记录与中无序区的最后一个记录交换 形成有序区,62,第二趟排序及堆的建立,13,88,42,23,24
27、,16,05,91,13 88 42 23 24 16 05 91,无序区长度为n=7,则筛选开始序号为 i=3,63,第二趟排序及堆的建立,13,88,42,23,24,16,05,91,13 88 42 23 24 16 05 91,继续筛选,则序号又减1为 i=2,64,第二趟排序及堆的建立,13,88,42,23,24,16,05,91,13 88 42 23 24 16 05 91,再继续筛选,则序号又减1为 i=1,65,第二趟排序及堆的建立,88,13,42,23,24,16,05,91,88 13 42 23 24 16 05 91,但在筛选中由于子树不为堆,则子树要调整,66
28、,第二趟排序及堆的建立,88,13,42,23,24,16,05,91,88 13 42 23 24 16 05 91,但在筛选中由于子树不为堆,则子树要调整,67,第二趟排序及堆的建立,88,24,42,23,13,16,05,91,88 24 42 23 13 16 05 91,但在筛选中由于子树不为堆,则子树要调整,68,第二趟排序及堆的建立的结果,88,24,42,23,13,16,05,91,88 24 42 23 13 16 05 91,大根堆,69,第二趟排序及堆的建立的结果,05,24,42,23,13,16,88,91,05 24 42 23 13 16 88 91,70,第
29、七趟排序及堆的建立的结果,05,13,16,23,24,42,88,91,05 13 16 23 24 42 88 91,最后,得到如下的堆以及其存储结构,对于调整后的完全二叉树若通过按层次遍历的方法,就可以得到一个升序的序列(如存储结构顺序一样)。,71,堆排序的性能分析,堆排序的时间复杂度为 O(nlog2n),但堆排序在待排序的记录数不大时,优势不明显。,堆排序是不稳定的。,72,7.4 交换排序,交换排序总的基本思想: 两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。,7.4.1 起泡排序 7.4.2 快速排序,73,设待排序记录顺序存放在R0,
30、R1,R2,Rn-1中,依次比较(R0,R1),( R1,R2), (Rn-2,Rn-1),不满足顺序则交换,结果,最大者在Rn-1中。这叫一次起泡。此后,再对存放在R0,R1,R2,Rn-2中n-1个记录作同样处理,结果,最大者在Rn-2中。 。 n-1次起泡能完成排序。 设置标志noswap表示本次起泡是否有交换,若无交换,表示排序完成。,7.4.1 起泡排序,74,举例说明,假设有如下记录依次存于R中,其对应关键字如下:,49,38,65,97,76,13,27,49,75,初 始 化 状 态,49,38,65,97,76,13,27,49,76,第 一 趟 排 序,49,38,65,9
31、7,76,13,27,49,13,76,49,13,97,13,65,13,38,13,49,77,第 二 趟 排 序,27,49,76,97,65,38,13,49,27,76,27,97,27,65,27,38,27,49,78,第 三 趟 排 序,76,49,97,65,38,49,13,27,79,第 三 趟 排 序,49,76,97,65,38,49,13,27,49,76,80,第 三 趟 排 序,49,76,97,65,38,49,13,27,49,97,81,第 三 趟 排 序,97,76,49,65,38,49,13,27,49,65,82,第 三 趟 排 序,97,76,6
32、5,49,38,49,13,27,83,第 三 趟 排 序,97,76,65,49,38,49,13,27,38,49,84,第 四 趟 排 序,97,76,65,49,49,38,13,27,76,97,85,第 五 趟 排 序,76,97,65,49,49,38,13,27,86,第 六 趟 排 序,76,65,49,49,38,13,27,97,87,第 七 趟 排 序,76,65,49,49,38,13,27,97,88,76,65,49,49,38,13,27,97,89,起泡排序的算法,假设待排序的文件为Rn。 对于记录数为 n 的文件,每趟扫描(排序)都使得有序区增加一个记录,因
33、此,经过 n-1 趟排序后,有序区就有n-1 个记录; 而无序区中的任一个记录的关键字都不小于有序区中任一个记录的关键字; 整个排序进行n-1 次; 在每趟排序中,扫描是从底部到顶部依次两两比较的,若当前有序区的记录数为 i (0=i = n-1 ),则当前扫描的次数就是 n i-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 27 38 49 49 65 76 97,13 27 38 4
34、9 49 65 76 97,初始 1 2 3 4 5 6,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-recordj=pvector-recordj+1; p
35、vector-recordj+1=temp; noswap=FALSE; if(noswap) break; /* 本趟起泡未发生记录交换,算法结束 */ ,92,起泡排序的最好时间复杂度为O(n),最坏时间复杂度为O(n2),平均时间复杂度为O(n2)。 起泡排序算法中增加一个辅助空间temp,辅 助空间为S(n)=O(1)。 起泡排序是稳定的。,93,快速排序是对冒泡排序的改进,其基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 首先任意选取一个记录作为枢轴(或支点)(Pivot
36、),然后按下述原则重新排列记录:将所有关键字小于它的记录都安置在它之前,将所有关键字大于它的记录安置在它之后。于是以该枢轴记录所在的位置i作分界线,将整个序列分成两个子序列。这个过程称为一趟快速排序。然后分别对于两个子序列作同样的操作,重复这个过程,直到子序列不可再分就完成了记录的排序工作。,7.4.2 快速排序,94,一趟快速排序的具体做法,设置两个指针i 和j,它们的初值分别为i=0和j=n1。 不妨取基准为无序区的第一个记录Ri(此时为R1),并将之存入temp中。 令j自n1开始向左扫描,直到找到第一个关键字小于temp.key的记录Rj,使Rj移到i 所指的位置; 令i自i+1起向右
37、扫描,直到找到第一个关键字大于temp.key的记录Ri,将Ri移到j所指位置; 接着,令j自j-1起向左扫描,如此交替改变扫描方向,从两端各自往中间靠拢,直到i=j时,i 便是基准X的最终位置,完成了一次划分。,95,举例说明,假设有如下记录依次存于R中,其对应关键字如下,要求用快速排序的一次划分(即一趟排序)进行基准记录的寻找。,49,38,65,97,76,13,27,49,96,初始化,49,38,65,97,76,13,27,49,i,j,基准temp,49,97,j向左扫描,49,38,65,97,76,13,27,49,i,j,基准temp,49,j,27,98,i向右扫描,27
38、,38,65,97,76,13,27,49,i,j,基准temp,49,i,i,65,99,j向左扫描,27,38,65,97,76,13,65,49,i,j,基准temp,49,j,13,100,i向右扫描,27,38,13,97,76,13,65,49,i,j,基准temp,49,i,97,101,j向左扫描,当i=j时,基准位置找到,27,38,13,97,76,97,65,49,i,j,基准temp,49,j,j,49,102,由于基准的左右两个无序子区均为非空,则继续对各子区再进行划分。最后,所有子区均为空,这时,排序完毕。, 49 38 65 97 76 13 27 49 , 27
39、 38 13 49 76 97 65 49 , 13 27 38 49 49 65 76 97,13 27 38 49 49 65 76 97,13 27 38 49 49 65 76 97,void quickSort(SortObject * 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
40、=temp.key) /* 递归处理右区间 */ ,104,快速排序算法的性能分析,最坏的情况是每次划分所选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准的左边(或右边)的无序子区为空,而另一个无序子区的记录个数仅减少一个。因此,排序总体上进行n-1趟,而每趟只需要比较n-1次,故总的比较次数为最大: Cmax=n(n-1)/2=O(n2 ),而最好的情况是每次划分所选取的基准都是当前无序区中关键字的“中间值”记录,划分的结果是基准的左右两边的无序子区长度大致相等。因此,每趟需要比较的次数要少许多。其总的比较次数为: CnLOG2n+nC=O( nLOG2n ),105,
41、快速排序算法的性能分析,快速排序的平均时间复杂度是 O( nLOG2n ), 它是目前基于比较的内部排序算法中速度最快的。,快速排序是不稳定的。,算法需要一个栈空间实现递归。栈的大小取决于递归调用的深度,最多不超过n,若每次都选较大的部分进栈,处理较短的部分,则递归深度最多不超过log2n,所以快速排序的辅助空间为S(n)=O(log2n)。,107,(1)平均时间性能:以快速排序法最佳,但最坏情况下不如堆排序和归并排序;在n较大时,归并排序比堆排序快,但所需辅助空间最多。 (2)简单排序以直接插入排序最简单,当记录 “基本有序“或n值较小时,是最佳的排序方法。因此常和其他排序方法结合使用。 (3)从稳定性来看,基数排序是稳定的排序方法,大部分时间复杂度为O(n2)的简单排序法都是稳定的。然而,快速排序、堆排序和希尔排序等时间性能较好的排序都是不稳定的。一般来说,排序过程中的比较是在相邻的两个记录关键字之间进行的排序方法是稳定的。,结论:,108,归并排序,109,分配排序,110,作业: 1, 3, 12,
链接地址:https://www.31doc.com/p-2582955.html