《数据结构6排序》由会员分享，可在线阅读，更多相关《数据结构6排序（55页珍藏版）》请在金锄头文库上搜索。
1、6 6排序排序1主要内容主要内容v排序的基本概念排序的基本概念排序的基本概念排序的基本概念v简单排序方法简单排序方法简单排序方法简单排序方法选择排序选择排序选择排序选择排序插入排序插入排序插入排序插入排序起泡排序起泡排序起泡排序起泡排序v先进排序方法先进排序方法先进排序方法先进排序方法快速排序快速排序快速排序快速排序归并排序归并排序归并排序归并排序基数排序基数排序基数排序基数排序26.1 6.1 排序的基本概念排序的基本概念vv排序是计算机内经常进行的一种操作，其目的是将一组排序是计算机内经常进行的一种操作，其目的是将一组排序是计算机内经常进行的一种操作，其目的是将一组排序是计算机内经常进行的
2、一种操作，其目的是将一组“ “无序无序无序无序” ”的记录序列调整为的记录序列调整为的记录序列调整为的记录序列调整为“ “有序有序有序有序” ”的记录序列。的记录序列。的记录序列。的记录序列。 例如：例如：例如：例如：将下列关键字序列将下列关键字序列将下列关键字序列将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 7552, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为调整为调整为调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 9714, 23, 36, 49, 52, 58, 61 ,75,
3、 80, 97定义定义假设含假设含n个记录的序列为个记录的序列为 R1, R2, ， Rn ,其相应的关键字序列为其相应的关键字序列为 K1, K2, ，Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这样一这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系个关系 ： Kp1Kp2Kpn按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。的操作称作排序。36.1 6.1 排序的基本概念排序的基本概念typedef typedef intint KeyType; / KeyType; /关健字类型为整数关健字
4、类型为整数关健字类型为整数关健字类型为整数typedeftypedef struct struct KeyType key;KeyType key; / /关键字项关键字项关键字项关键字项 infoType OtherInfo; /infoType OtherInfo; /其它信息其它信息其它信息其它信息 RcdType;RcdType; / /记录类型记录类型记录类型记录类型46.1 6.1 排序的基本概念排序的基本概念排序分类排序分类排序分类排序分类按待排序记录所在位置按待排序记录所在位置按待排序记录所在位置按待排序记录所在位置l l内部排序：待排序记录存放在内存内部排序：待排序记录存放在
5、内存内部排序：待排序记录存放在内存内部排序：待排序记录存放在内存l l外部排序：排序过程中需对外存进行访问的排序外部排序：排序过程中需对外存进行访问的排序外部排序：排序过程中需对外存进行访问的排序外部排序：排序过程中需对外存进行访问的排序按排序依据原则按排序依据原则按排序依据原则按排序依据原则l l插入排序：直接插入排序、折半插入排序、希尔排序插入排序：直接插入排序、折半插入排序、希尔排序插入排序：直接插入排序、折半插入排序、希尔排序插入排序：直接插入排序、折半插入排序、希尔排序l l交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速排
6、序l l选择排序：简单选择排序、堆排序选择排序：简单选择排序、堆排序选择排序：简单选择排序、堆排序选择排序：简单选择排序、堆排序l l归并排序：归并排序：归并排序：归并排序：2-2-路归并排序路归并排序路归并排序路归并排序l l基数排序基数排序基数排序基数排序排序稳定性排序稳定性排序稳定性排序稳定性56.1 6.1 排序的基本概念排序的基本概念按排序所需工作量按排序所需工作量按排序所需工作量按排序所需工作量简单的排序方法：简单的排序方法：简单的排序方法：简单的排序方法：T(n)=O(nT(n)=O(n ) )先进的排序方法：先进的排序方法：先进的排序方法：先进的排序方法：T(n)=O(nlog
7、n)T(n)=O(nlogn) 基数排序：基数排序：基数排序：基数排序：T(n)=O(d.n)T(n)=O(d.n)排序基本操作排序基本操作排序基本操作排序基本操作比较两个关键字大小比较两个关键字大小比较两个关键字大小比较两个关键字大小将记录从一个位置移动到另一个位置将记录从一个位置移动到另一个位置将记录从一个位置移动到另一个位置将记录从一个位置移动到另一个位置r2ri-1riri+1r1rn有序序列有序序列有序序列有序序列 R1.i-1R1.i-1无序序列无序序列无序序列无序序列 Ri.nRi.n有序序列有序序列有序序列有序序列 R1 . iR1 . i无序序列无序序列无序序列无序序列 Ri
8、+1 . nRi+1 . n排序算法的思想排序算法的思想排序算法的思想排序算法的思想: :将待排序列看成是看成是有有序序列和无将待排序列看成是看成是有有序序列和无将待排序列看成是看成是有有序序列和无将待排序列看成是看成是有有序序列和无序序列组成，每次排序都会按照某种原则序序列组成，每次排序都会按照某种原则序序列组成，每次排序都会按照某种原则序序列组成，每次排序都会按照某种原则将无序序列中的某个元素取出，放在有序将无序序列中的某个元素取出，放在有序将无序序列中的某个元素取出，放在有序将无序序列中的某个元素取出，放在有序序列中，这样经序列中，这样经序列中，这样经序列中，这样经n-1n-1次操作就会
9、将无序序次操作就会将无序序次操作就会将无序序次操作就会将无序序列列列列R1.nR1.n排成有序序列排成有序序列排成有序序列排成有序序列内部排序的过程是一个逐步扩大逐步扩大记录的有序序列长度有序序列长度的过程。6基于不同的“扩大扩大” 有序序列长度的方法，内部排序方法方法，内部排序方法大致可分下列几种类型：插入类插入类交换类交换类选择类选择类 归并类归并类其它方法其它方法6.1 6.1 排序的基本概念排序的基本概念76.1 6.1 排序的基本概念排序的基本概念vv插入类排序插入类排序插入类排序插入类排序将无序子序列中的一个或几个记录将无序子序列中的一个或几个记录将无序子序列中的一个或几个记录将无
10、序子序列中的一个或几个记录“插入插入插入插入”到有序序列中，从而到有序序列中，从而到有序序列中，从而到有序序列中，从而增加记录的有序子序列的长度。增加记录的有序子序列的长度。增加记录的有序子序列的长度。增加记录的有序子序列的长度。vv交换类排序交换类排序交换类排序交换类排序通过通过通过通过“交换交换交换交换”无序序列中的记录从而得到其中关键字最小或最大无序序列中的记录从而得到其中关键字最小或最大无序序列中的记录从而得到其中关键字最小或最大无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序的记录，并将它加入到有序子序列中，以此方法增加记录的有序的
11、记录，并将它加入到有序子序列中，以此方法增加记录的有序的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。子序列的长度。子序列的长度。子序列的长度。vv选择类排序选择类排序选择类排序选择类排序从记录的无序子序列中从记录的无序子序列中从记录的无序子序列中从记录的无序子序列中“选择选择选择选择”关键字最小或最大的记录，并将关键字最小或最大的记录，并将关键字最小或最大的记录，并将关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。它加入到有序子序列中，以此方法增加记录的有序子序列的长度。它加入到有序子序列中，以此方法增加记录的有序子序列的长度。它加
12、入到有序子序列中，以此方法增加记录的有序子序列的长度。vv归并类排序归并类排序归并类排序归并类排序通过通过通过通过“归并归并归并归并”两个或两个以上的记录有序子序列，逐步增加记录两个或两个以上的记录有序子序列，逐步增加记录两个或两个以上的记录有序子序列，逐步增加记录两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。有序序列的长度。有序序列的长度。有序序列的长度。vv其它类排序其它类排序其它类排序其它类排序86.2 6.2 插入排序插入排序v6.2.1 6.2.1 直接插入排序直接插入排序直接插入排序直接插入排序v6.2.2 6.2.2 二分二分二分二分 ( (折半）插入排序折半）插入
13、排序折半）插入排序折半）插入排序v6.2.3 6.2.3 希尔排序希尔排序希尔排序希尔排序96.2.1 6.2.1 直接插入排序直接插入排序v插入排序过程：插入排序过程：插入排序过程：插入排序过程：整个排序过程为整个排序过程为整个排序过程为整个排序过程为n-1n-1趟插入，即先将序列中第趟插入，即先将序列中第趟插入，即先将序列中第趟插入，即先将序列中第1 1个记录看个记录看个记录看个记录看成是一个有序子序列，然后从第成是一个有序子序列，然后从第成是一个有序子序列，然后从第成是一个有序子序列，然后从第2 2个记录开始，逐个进个记录开始，逐个进个记录开始，逐个进个记录开始，逐个进行插入，直至整个序
14、列有序行插入，直至整个序列有序行插入，直至整个序列有序行插入，直至整个序列有序有序序列R1.i-1Ri无序序列 Ri.n有序序列R1.i无序序列 Ri+1.n1049 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49 65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=1 ( )i=7 (13 38 49 65 76 97) 2727jjjjjj977665493827
15、(13 27 38 49 65 76 97)排序结果：例：例：例：例： ( (49 38 65 97 76 13 27)思考：寻找插入位置时，思考：寻找插入位置时，思考：寻找插入位置时，思考：寻找插入位置时，应该从后向前找还是从前应该从后向前找还是从前应该从后向前找还是从前应该从后向前找还是从前向后找？为什么？向后找？为什么？向后找？为什么？向后找？为什么？11算法名：算法名：算法名：算法名：InsertSortInsertSort1. 1.输入：无序数组输入：无序数组输入：无序数组输入：无序数组R R2. 2.输出：有序数组输出：有序数组输出：有序数组输出：有序数组R R3. 3.算法算法算
16、法算法(1).(1).排序趟数排序趟数排序趟数排序趟数i=2ni=2n(2) (2) 对于每一趟对于每一趟对于每一趟对于每一趟i, i,将无序序将无序序将无序序将无序序列的第一个元素列的第一个元素列的第一个元素列的第一个元素RiRi插入插入插入插入到有序序列到有序序列到有序序列到有序序列R1i-1R1i-1中中中中InsertSort(R)InsertSort(R) for(i=2;i=n;i+) for(i=2;i=1;j-)for(j=i-1;j=1;j-) if(R0Rj) Rj+1=Rj; if(R0Rj) Rj+1=Rj; Rj+1=R0; Rj+1=R0; 12v算法评价算法评价算
17、法评价算法评价时间复杂度时间复杂度时间复杂度时间复杂度l l若待排序记录按关键字从小到大排列若待排序记录按关键字从小到大排列若待排序记录按关键字从小到大排列若待排序记录按关键字从小到大排列( (正序正序正序正序) )YY关键字比较次数：关键字比较次数：关键字比较次数：关键字比较次数：YY记录移动次数：记录移动次数：记录移动次数：记录移动次数：0 0l l若待排序记录按关键字从大到小排列若待排序记录按关键字从大到小排列若待排序记录按关键字从大到小排列若待排序记录按关键字从大到小排列( (逆序逆序逆序逆序) )YY关键字比较次数：关键字比较次数：关键字比较次数：关键字比较次数：YY记录移动次数：记
18、录移动次数：记录移动次数：记录移动次数：l l若待排序记录是随机的，取平均值若待排序记录是随机的，取平均值若待排序记录是随机的，取平均值若待排序记录是随机的，取平均值YY关键字比较次数：关键字比较次数：关键字比较次数：关键字比较次数：YY记录移动次数：记录移动次数：记录移动次数：记录移动次数：T(n)=O(n)空间复杂度：空间复杂度：空间复杂度：空间复杂度：S(n)=O(1)S(n)=O(1)136.2.2 6.2.2 二分二分( (折半折半) )插入排序插入排序v排序过程：排序过程：排序过程：排序过程：用二分查找方法确定插入位置的排序叫用二分查找方法确定插入位置的排序叫用二分查找方法确定插入
19、位置的排序叫用二分查找方法确定插入位置的排序叫 例i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85 ) 20.i=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sji=8 20 (6 13 20 30 39 42 70 85 )插入位置为插入位置为插入位
20、置为插入位置为S S或或或或j+1j+1处处处处14算法描述算法描述算法描述算法描述算法评价算法评价算法评价算法评价l l与直接插入排序相比：与直接插入排序相比：与直接插入排序相比：与直接插入排序相比： 关键字比较次数减少关键字比较次数减少关键字比较次数减少关键字比较次数减少 记录移动次数不变记录移动次数不变记录移动次数不变记录移动次数不变l l时间复杂度：时间复杂度：时间复杂度：时间复杂度：T(n)=O(nT(n)=O(n ) )l l空间复杂度：空间复杂度：空间复杂度：空间复杂度：S(n)=O(1)S(n)=O(1)156.2.3 6.2.3 希尔排序希尔排序v基本思想：基本思想：基本思想
21、：基本思想：在直接插入排序算法中，如果待排序列已经是按升序在直接插入排序算法中，如果待排序列已经是按升序在直接插入排序算法中，如果待排序列已经是按升序在直接插入排序算法中，如果待排序列已经是按升序有序的，则直接插入排序的时间复杂性是有序的，则直接插入排序的时间复杂性是有序的，则直接插入排序的时间复杂性是有序的，则直接插入排序的时间复杂性是T(n)=O(n)T(n)=O(n)ShellShell排序就是利用这个特点，先将记录进行粗略地分排序就是利用这个特点，先将记录进行粗略地分排序就是利用这个特点，先将记录进行粗略地分排序就是利用这个特点，先将记录进行粗略地分组，使整个序列大致按升序有序，这样最
22、后进行直接组，使整个序列大致按升序有序，这样最后进行直接组，使整个序列大致按升序有序，这样最后进行直接组，使整个序列大致按升序有序，这样最后进行直接插入排序时，时间复杂性插入排序时，时间复杂性插入排序时，时间复杂性插入排序时，时间复杂性 T(n)O(nT(n)O(n ) )v排序过程：排序过程：排序过程：排序过程：先取一个正整数先取一个正整数先取一个正整数先取一个正整数d d1 1nn，把所有相隔把所有相隔把所有相隔把所有相隔d d1 1的记录放一组，的记录放一组，的记录放一组，的记录放一组，组内进行直接插入排序；组内进行直接插入排序；组内进行直接插入排序；组内进行直接插入排序；然后取然后取然
23、后取然后取d d2 2dd1 1，重复上述分组和排序操作；直至重复上述分组和排序操作；直至重复上述分组和排序操作；直至重复上述分组和排序操作；直至d di i=1=1，即所有记录放进一个组中排序为止即所有记录放进一个组中排序为止即所有记录放进一个组中排序为止即所有记录放进一个组中排序为止16取d3=1三趟分组：13 27 48 55 4 49 38 65 97 76三趟排序：4 13 27 38 48 49 55 65 76 97例例 初始：初始： 49 38 65 97 76 13 27 48 55 4一趟排序：13 27 48 55 4 49 38 65 97 76二趟排序：13 4 48
24、 38 27 49 55 65 97 76取d1=5一趟分组：49 38 65 97 76 13 27 48 55 4取d2=3二趟分组：13 27 48 55 4 49 38 65 97 7617ShellInsert(int R ,int dk)/ShellInsert(int R ,int dk)/一次增量排序一次增量排序一次增量排序一次增量排序 for(i=dk+1;i=n;i+) for(i=dk+1;i=n;i+) if(RiRi-dk) if(Ri0 & (R0 0 & (R0 Rj ); j-=dk) Rj+dk=Rj; Rj+dk=Rj; Rj+dk=R0; Rj+dk=R0
25、; ShellSort(int R , int d,int t)/ShellSort(int R , int d,int t)/一次增量排序一次增量排序一次增量排序一次增量排序 for(k=0; kt; k+) for(k=0; kr2.keyr1.keyr2.key，则交则交则交则交换；然后比较第二个记录与第三个记录；依次换；然后比较第二个记录与第三个记录；依次换；然后比较第二个记录与第三个记录；依次换；然后比较第二个记录与第三个记录；依次类推，直至第类推，直至第类推，直至第类推，直至第n-1n-1个记录和第个记录和第个记录和第个记录和第n n个记录比较为止个记录比较为止个记录比较为止个记录
26、比较为止第一趟冒泡排序第一趟冒泡排序第一趟冒泡排序第一趟冒泡排序，结果关键字最大的记录，结果关键字最大的记录，结果关键字最大的记录，结果关键字最大的记录被安置在最后一个记录上被安置在最后一个记录上被安置在最后一个记录上被安置在最后一个记录上对前对前对前对前n-1n-1个记录进行第二趟冒泡排序，结果使关个记录进行第二趟冒泡排序，结果使关个记录进行第二趟冒泡排序，结果使关个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第键字次大的记录被安置在第键字次大的记录被安置在第键字次大的记录被安置在第n-1n-1个记录位置个记录位置个记录位置个记录位置重复上述过程，直到重复上述过程，直到重复上述过程
27、，直到重复上述过程，直到“在一趟排序过程中没有在一趟排序过程中没有在一趟排序过程中没有在一趟排序过程中没有进行过交换记录的操作进行过交换记录的操作进行过交换记录的操作进行过交换记录的操作”为止为止为止为止214 49 9 3 38 8 6 65 5 9 97 7 7 76 6 1 13 3 2 27 7 3 30 0初始关键字3 38 8 4 49 9 6 65 5 7 76 6 1 13 3 2 27 7 3 30 0 9 97 7第一趟3 38 8 4 49 9 6 65 5 1 13 3 2 27 7 3 30 0 7 76 6第二趟3 38 8 4 49 9 1 13 3 2 27 7
28、 3 30 0 6 65 5第三趟3 38 8 1 13 3 2 27 7 3 30 0 4 49 9第四趟1 13 3 2 27 7 3 30 0 3 38 8第五趟1 13 3 2 27 7 3 30 0第六趟for(j=1;for(j=1;jijRj+1) if(RjRj+1) / /交换交换交换交换RjRj和和和和Rj+1Rj+1 w=Rj; w=Rj; Rj=Rj+1; Rj=Rj+1; Rj+1=w; Rj+1=w; BulleSort(R)BulleSort(R)for(i=n; i1; i-)for(i=n; i1; i-) for(j=1; for(j=1;jijRj+1)
29、if(RjRj+1) / /交换交换交换交换RjRj和和和和Rj+1Rj+1 w=Rj; w=Rj; Rj=Rj+1; Rj=Rj+1; Rj+1=w; Rj+1=w; 22算法评价算法评价算法评价算法评价l l时间复杂度时间复杂度时间复杂度时间复杂度pp最好情况（正序）最好情况（正序）最好情况（正序）最好情况（正序）YY比较次数：比较次数：比较次数：比较次数：n-1n-1YY移动次数：移动次数：移动次数：移动次数：0 0pp最坏情况（逆序）最坏情况（逆序）最坏情况（逆序）最坏情况（逆序）YY比较次数：比较次数：比较次数：比较次数：YY移动次数：移动次数：移动次数：移动次数：l l空间复杂度：
30、空间复杂度：空间复杂度：空间复杂度：S(n)=O(1)S(n)=O(1)T(n)=O(n)236.3.2 6.3.2 快速排序方法快速排序方法v基本思想：基本思想：基本思想：基本思想：首先对无序的记录序列进行首先对无序的记录序列进行首先对无序的记录序列进行首先对无序的记录序列进行“一次划分一次划分一次划分一次划分”，之后分别，之后分别，之后分别，之后分别对分割所得两个子序列对分割所得两个子序列对分割所得两个子序列对分割所得两个子序列“递归递归递归递归”进行划分。进行划分。进行划分。进行划分。无 序 的 记 录 序 列无序记录子序列(1)无序子序列(2)枢轴枢轴一次划分分别进行划分24v记录划分
31、：记录划分：记录划分：记录划分：找一个记录，找一个记录，找一个记录，找一个记录，以它的关键字作为以它的关键字作为以它的关键字作为以它的关键字作为“ “枢轴枢轴枢轴枢轴” ”，凡其凡其凡其凡其关键关键关键关键字小于枢轴字小于枢轴字小于枢轴字小于枢轴的记录均的记录均的记录均的记录均移动至该记录之前，移动至该记录之前，移动至该记录之前，移动至该记录之前，反之，凡反之，凡反之，凡反之，凡关关关关键字大于枢轴键字大于枢轴键字大于枢轴键字大于枢轴的记录均的记录均的记录均的记录均移动至该记录之后移动至该记录之后移动至该记录之后移动至该记录之后。划分过程：对划分过程：对划分过程：对划分过程：对rsrst t中
32、记录进行一中记录进行一中记录进行一中记录进行一次划分次划分次划分次划分，附设两，附设两，附设两，附设两个指针个指针个指针个指针lowlow和和和和highhigh，设枢轴记录设枢轴记录设枢轴记录设枢轴记录r rp p=rs=rs，pivotkey=rpivotkey=rp p.key.key初始时令初始时令初始时令初始时令low=s, high=tlow=s, high=t首先从首先从首先从首先从highhigh所指位置向前搜索第一个关键字小于所指位置向前搜索第一个关键字小于所指位置向前搜索第一个关键字小于所指位置向前搜索第一个关键字小于pivotkeypivotkey的记录，的记录，的记录，
33、的记录，并和并和并和并和r rp p交换交换交换交换再从再从再从再从lowlow所指位置起向后搜索，找到第一个关键字大于所指位置起向后搜索，找到第一个关键字大于所指位置起向后搜索，找到第一个关键字大于所指位置起向后搜索，找到第一个关键字大于pivotkeypivotkey的记录，和的记录，和的记录，和的记录，和rprp交换交换交换交换重复上述两步，直至重复上述两步，直至重复上述两步，直至重复上述两步，直至low=highlow=high为止为止为止为止25stlowhigh设设 Pivotkey=Rs=52 为枢轴关键字为枢轴关键字high23low80high14low52Rs=52lowh
34、ighhighhighlow原序列：原序列：原序列：原序列：52, 49, 52, 49, 8080, 36, , 36, 1414, 58, 61, 97, , 58, 61, 97, 2323, 75 , 75 一次划分后：一次划分后：一次划分后：一次划分后：2323, 49, , 49, 1414, 36, , 36, (52)(52) 58, 61, 97, 58, 61, 97, 8080, 75, 7526vv递归排序递归排序递归排序递归排序对于上次划分所形成的每个子序列重复进行划分对于上次划分所形成的每个子序列重复进行划分对于上次划分所形成的每个子序列重复进行划分对于上次划分所形
35、成的每个子序列重复进行划分52, 49, 52, 49, 8080, 36, , 36, 1414, 58, 61, 97, , 58, 61, 97, 2323, 75 , 75 (52)(52)2323, 49, , 49, 1414, 36, 3658, 61, 97, 58, 61, 97, 8080, 75, 7514, 14, (23)(23), 49, 36, 49, 36(58)(58), 61, 97, 80, 75, 61, 97, 80, 7536, 36, (49)(49)(61)(61), 97, 80, 75, 97, 80, 75(36)(36)75, 80, 7
36、5, 80, (97)(97)(75),(75), 80 80(80)(80)14, 23, 36, 49, 52, 58, 61, 75, 80, 97 14, 23, 36, 49, 52, 58, 61, 75, 80, 97 (14)(14)27算法评价算法评价算法评价算法评价l l时间复杂度时间复杂度时间复杂度时间复杂度pp最好情况（每次总是选到中间值作枢轴）最好情况（每次总是选到中间值作枢轴）最好情况（每次总是选到中间值作枢轴）最好情况（每次总是选到中间值作枢轴）T(n)=O(nlogT(n)=O(nlog2 2n)n)pp最坏情况（每次总是选到最小或最大元素作枢最坏情况（每次总是
37、选到最小或最大元素作枢最坏情况（每次总是选到最小或最大元素作枢最坏情况（每次总是选到最小或最大元素作枢轴）轴）轴）轴）T(n)=O(nT(n)=O(n ) )l l空间复杂度：需栈空间以实现递归空间复杂度：需栈空间以实现递归空间复杂度：需栈空间以实现递归空间复杂度：需栈空间以实现递归pp最坏情况：最坏情况：最坏情况：最坏情况：S(n)=O(n)S(n)=O(n)pp一般情况：一般情况：一般情况：一般情况：S(n)=O(logS(n)=O(log2 2n)n)286.4 6.4 选择排序选择排序v6.4.1 6.4.1 简单选择排序简单选择排序简单选择排序简单选择排序v6.4.2 6.4.2 堆
38、排序堆排序堆排序堆排序296.4.1 6.4.1 简单选择排序简单选择排序有序序列R1.i-1无序序列 Ri.nRk找最小值找最小值找最小值找最小值RkRkRi有序序列R1.i-1无序序列 Ri.nRiRkRkRk与与与与RiRi交换交换交换交换30vv选择排序的基本思想：整个排序过程为选择排序的基本思想：整个排序过程为选择排序的基本思想：整个排序过程为选择排序的基本思想：整个排序过程为n n趟趟趟趟扫描扫描扫描扫描，即，即，即，即首首首首先先先先在在在在n n个记录中选择关键字最小的放在有序子序列的第个记录中选择关键字最小的放在有序子序列的第个记录中选择关键字最小的放在有序子序列的第个记录中
39、选择关键字最小的放在有序子序列的第一个记录位置，然后从剩下的一个记录位置，然后从剩下的一个记录位置，然后从剩下的一个记录位置，然后从剩下的n-1n-1个记录中选择关键字个记录中选择关键字个记录中选择关键字个记录中选择关键字最小的最小的最小的最小的记录记录记录记录放在有序子序列的第二个记录位置，重复此放在有序子序列的第二个记录位置，重复此放在有序子序列的第二个记录位置，重复此放在有序子序列的第二个记录位置，重复此过程，直到最后一个记录过程，直到最后一个记录过程，直到最后一个记录过程，直到最后一个记录例：（例：（例：（例：（49491 1,38,65,49,38,65,492 2,76,13,27
40、,52,76,13,27,52）49491 13838656549492 2767613132727525213133838656549492 2767649491 12727525213132727656549492 2767649491 13838525213132727383849492 2767649491 16565525213132727383849492 2767649491 16565525213132727383849492 249491 176766565525213132727383849492 249491 152526565767613132727383849492
41、249491 152526565767631初始： 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟： 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76 六趟： 13 27 38 49 65 76 97 排序结束： 13 27 38 49 65 76 9732v算法描述算法描述算法描述算法描述void SelectSort (SqList &L)v
42、oid SelectSort (SqList &L) / / 对顺序表对顺序表对顺序表对顺序表L L作简单选择排序。作简单选择排序。作简单选择排序。作简单选择排序。 RcdType WRcdType W； for (i=1; iL.length; +i) for (i=1; iL.length; +i) k = ik = i； / / 选择第选择第选择第选择第i i小的记录，并交换到位小的记录，并交换到位小的记录，并交换到位小的记录，并交换到位 for (j=i+1; j=L.length; j+ ) / for (j=i+1; j=L.length; j+ ) / 在在在在L.ri.L.le
43、ngthL.ri.L.length中选择中选择中选择中选择keykey最小的记录最小的记录最小的记录最小的记录if ( L.rj.key L.rk.key ) if ( L.rj.key L.rk.key ) k = j k = j ； if ( i!=k )if ( i!=k ) W=L.rkW=L.rk；L.rk =L.riL.rk =L.ri；L.ri = WL.ri = W； / / 与第与第与第与第i i个记录交换个记录交换个记录交换个记录交换 / SelectSort / SelectSort33v算法评价算法评价算法评价算法评价时间复杂度时间复杂度时间复杂度时间复杂度记录移动次数
44、记录移动次数记录移动次数记录移动次数YY最好情况：最好情况：最好情况：最好情况：0 0YY最坏情况：最坏情况：最坏情况：最坏情况：3(3(n-1)n-1)比较次数：比较次数：比较次数：比较次数：空间复杂度：空间复杂度：空间复杂度：空间复杂度：S(n)=O(1)S(n)=O(1)T(n)=O(n)简单选择排序简单选择排序346.4.2 6.4.2 堆排序堆排序356.5 6.5 归并排序归并排序vv基本思想：将两个有序表合并成一个有序表的时间复杂性基本思想：将两个有序表合并成一个有序表的时间复杂性基本思想：将两个有序表合并成一个有序表的时间复杂性基本思想：将两个有序表合并成一个有序表的时间复杂性
45、是是是是 T(n)=O(n)T(n)=O(n)vv关键：将两个有序表合并成一个有序表的算法关键：将两个有序表合并成一个有序表的算法关键：将两个有序表合并成一个有序表的算法关键：将两个有序表合并成一个有序表的算法3 8 12 15 183 8 12 15 18 2 5 142 5 14i ij jRst s=1, t=8, m=5Rst s=1, t=8, m=5 i=s; j=m+1; k=s;i=s; j=m+1; k=s;while( )while( ) if (SRi=SRj) if (SRi=SRj) TRk=SRi; i+; TRk=SRi; i+; else else TRk=SR
46、j; j+ ; TRk=SRj; j+ ; k+; k+; while (i=m) TRk+ = SRi+; while (i=m) TRk+ = SRi+; while (j=n) TRk+ = SRj+;while (j=n) TRk+ = SRj+; i=m & j=ti=m & j=tvoid Merge(SR,TR,s,m,t)void Merge(SR,TR,s,m,t)36v问题：实际被排序的序列不可能是有序的问题：实际被排序的序列不可能是有序的如果无序序列如果无序序列如果无序序列如果无序序列 Rs.t Rs.t 的两部分的两部分的两部分的两部分 Rs Rs (s+t)/2 (s
47、+t)/2 和和和和 RR(s+t)/2+1 (s+t)/2+1 t t 分别按关键字有序，则利用上述归并算法很容易将分别按关键字有序，则利用上述归并算法很容易将分别按关键字有序，则利用上述归并算法很容易将分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。它们归并成整个记录序列是一个有序序列。它们归并成整个记录序列是一个有序序列。它们归并成整个记录序列是一个有序序列。v算法：两类算法算法：两类算法自顶向下自顶向下自顶向下自顶向下递归算法递归算法递归算法递归算法自底向上自底向上自底向上自底向上迭代算法迭代算法迭代算法迭代算法3752, 23, 80, 36, 68
48、, 14 (s=1, t=6) 52, 23, 80 36, 68, 14 52, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 23自自自自顶顶顶顶向向向向下下下下的的的的设设设设计计计计方方方方法法法法递归算法递归算法递归算法递归算法38v迭代算法迭代算法迭代算法迭代算法39利利利利用用用用数数数数组组组组两两两两相相相相邻邻邻邻有有有有序序序序段段段段归归归归并并并并函函函函数数数数，将将将将存存存存于于于于一一一一个个个个数数数数组组组组中中中中的的的的每每每每lenlenlen
49、len个个个个元元元元素素素素有有有有序序序序的的的的段段段段分分分分别别别别作作作作两两两两两两两两归归归归并并并并，使使使使数数数数组组组组中中中中的的的的元元元元素素素素每每每每2*len2*len2*len2*len个个个个元元元元素素素素有序的函数。有序的函数。有序的函数。有序的函数。【算法算法算法算法】一趟归并一趟归并一趟归并一趟归并void mergePass(SR , TR , int n, int len) void mergePass(SR , TR , int n, int len) int i=1, j; int i=1, j; while(i+2*len n) whi
50、le(i+2*len n) merge(SR, TR, i, i+len-1, i+2*len-1); merge(SR, TR, i, i+len-1, i+2*len-1); i+=2*len; i+=2*len; if (i+len =n) / if (i+len =n) / 一个长一个长一个长一个长lenlen，另一个不足，另一个不足，另一个不足，另一个不足lenlen merge(SR, TR , i, i+len-1, n-1); merge(SR, TR , i, i+len-1, n-1); 40【算法算法算法算法】迭代的归并排序迭代的归并排序迭代的归并排序迭代的归并排序假假假
51、假设设设设初初初初始始始始的的的的对对对对象象象象序序序序列列列列有有有有n n个个个个对对对对象象象象，首首首首先先先先把把把把它它它它看看看看成成成成是是是是n n个个个个长长长长度度度度为为为为1 1的的的的有有有有序序序序子子子子序序序序列列列列，先先先先做做做做两两两两两两两两归归归归并并并并，得得得得到到到到n/2n/2个个个个长长长长度度度度为为为为2 2的的的的归归归归并并并并项项项项（如如如如果果果果n n为为为为奇奇奇奇数数数数，则则则则最最最最后后后后一一一一个个个个有有有有序序序序子子子子序序序序列列列列的的的的长长长长度度度度为为为为1 1）；再再再再做做做做两两两两
52、两两两两归归归归并并并并，如如如如此此此此重重重重复，最后得到一个长度为复，最后得到一个长度为复，最后得到一个长度为复，最后得到一个长度为n n的有序序列。的有序序列。的有序序列。的有序序列。void mergeSort(R , TR , n)void mergeSort(R , TR , n) int len; int len; len=1; len=1; while(len n) while(len n) mergePass(R, TR, len); mergePass(R, TR, len); len*=2; len*=2; 41算法评价算法评价算法评价算法评价: :两种方法两种方法两种
53、方法两种方法l l时间复杂度：时间复杂度：时间复杂度：时间复杂度：T(n)=O(nlogT(n)=O(nlog2 2n)n)l l空间复杂度：空间复杂度：空间复杂度：空间复杂度：S(n)=O(n)S(n)=O(n)426.6 6.6 基数排序基数排序v关于排序问题的研究关于排序问题的研究关于排序问题的研究关于排序问题的研究排序算法是计算机科学的最基本的算法排序算法是计算机科学的最基本的算法排序算法是计算机科学的最基本的算法排序算法是计算机科学的最基本的算法现在每年仍有排序方面的研究文章出现现在每年仍有排序方面的研究文章出现现在每年仍有排序方面的研究文章出现现在每年仍有排序方面的研究文章出现主要
54、是基数类的排序算法主要是基数类的排序算法主要是基数类的排序算法主要是基数类的排序算法v理论证明理论证明理论证明理论证明：基于比较的排序算法，其最坏情况下：基于比较的排序算法，其最坏情况下：基于比较的排序算法，其最坏情况下：基于比较的排序算法，其最坏情况下的时间复杂性极限是的时间复杂性极限是的时间复杂性极限是的时间复杂性极限是 T(n)=O(nlogT(n)=O(nlog2 2n)n)436.6.1 6.6.1 桶排序桶排序v例例: (51, 31, 21, 22, 52, 41, 42, 53, 54, 23, 32)2 23 32 22 22 21 15 54 45 53 35 52 25
55、51 13 32 23 31 14 42 24 41 1(2(21 1, 2, 22 2, 2, 23 3, 3, 31 1, 3, 32 2, 4, 41 1, 4, 42 2, 5, 51 1, 5, 52 2, 5, 53 3, 5, 54 4) )44例例例例 对对对对5252张扑克牌按以下次序排序：张扑克牌按以下次序排序：张扑克牌按以下次序排序：张扑克牌按以下次序排序： 22 33 AA 22 33 AA 22 33 AA 22 33 A A两个关键字：花色（两个关键字：花色（两个关键字：花色（两个关键字：花色（ ） 面值（面值（面值（面值（23A23A）并且并且并且并且“ “花色花
56、色花色花色” ”地位高于地位高于地位高于地位高于“ “面值面值面值面值” ”v多关键字排序思路多关键字排序思路多关键字排序思路多关键字排序思路最高位优先法（最高位优先法（最高位优先法（最高位优先法（MSD)MSD)：先对最高位关键字先对最高位关键字先对最高位关键字先对最高位关键字k1k1（如花如花如花如花色）排序，将序列分成若干子序列，每个子序列有色）排序，将序列分成若干子序列，每个子序列有色）排序，将序列分成若干子序列，每个子序列有色）排序，将序列分成若干子序列，每个子序列有相同的相同的相同的相同的k1k1值；然后让每个子序列对次关键字值；然后让每个子序列对次关键字值；然后让每个子序列对次关
57、键字值；然后让每个子序列对次关键字k2k2（如如如如面值）排序，又分成若干更小的子序列；依次重复，面值）排序，又分成若干更小的子序列；依次重复，面值）排序，又分成若干更小的子序列；依次重复，面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字直至就每个子序列对最低位关键字直至就每个子序列对最低位关键字直至就每个子序列对最低位关键字kdkd排序；最后将排序；最后将排序；最后将排序；最后将所有子序列依次连接在一起成为一个有序序列所有子序列依次连接在一起成为一个有序序列所有子序列依次连接在一起成为一个有序序列所有子序列依次连接在一起成为一个有序序列6.6.2 6.6.2 基数
58、排序基数排序多关键字多关键字45最低位优先法最低位优先法最低位优先法最低位优先法(LSD)(LSD)：从最低位关键字：从最低位关键字：从最低位关键字：从最低位关键字kdkd起进行排序，起进行排序，起进行排序，起进行排序，然后再对高一位的关键字排序，然后再对高一位的关键字排序，然后再对高一位的关键字排序，然后再对高一位的关键字排序，依次重复，直依次重复，直依次重复，直依次重复，直至对最高位关键字至对最高位关键字至对最高位关键字至对最高位关键字k1k1排序后，便成为一个有序序列。排序后，便成为一个有序序列。排序后，便成为一个有序序列。排序后，便成为一个有序序列。MSDMSD与与与与LSDLSD不同
59、特点不同特点不同特点不同特点按按按按MSDMSD排序，必须将序列逐层分割成若干子序列，然排序，必须将序列逐层分割成若干子序列，然排序，必须将序列逐层分割成若干子序列，然排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序后对各子序列分别排序后对各子序列分别排序后对各子序列分别排序按按按按LSDLSD排序，不必分成子序列，对每个关键字都是整排序，不必分成子序列，对每个关键字都是整排序，不必分成子序列，对每个关键字都是整排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过个序列参加排序；并且可不通过关键字比较，而通过个序列参加排序；并且可不通过关键字比较，
60、而通过个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序若干次分配与收集实现排序若干次分配与收集实现排序若干次分配与收集实现排序46v链式基数排序链式基数排序链式基数排序链式基数排序基数排序：借助基数排序：借助基数排序：借助基数排序：借助“ “分配分配分配分配” ”和和和和“ “收集收集收集收集” ”对单逻辑关键对单逻辑关键对单逻辑关键对单逻辑关键字进行排序的一种方法。字进行排序的一种方法。字进行排序的一种方法。字进行排序的一种方法。有的逻辑关键字可以看成由若干个关键字复合而成。有的逻辑关键字可以看成由若干个关键字复合而成。有的逻辑关键字可以看成由若干个关键字复合而成。有的
61、逻辑关键字可以看成由若干个关键字复合而成。例：关键字例：关键字例：关键字例：关键字K K的的的的取值取值取值取值范围为范围为范围为范围为00，999999，则可将，则可将，则可将，则可将K K看成由看成由看成由看成由三个关键字（三个关键字（三个关键字（三个关键字（k0,k1,k2) k0,k1,k2) 组成。其中组成。其中组成。其中组成。其中k0k0是百位数，是百位数，是百位数，是百位数， k1k1是十位数，是十位数，是十位数，是十位数， k2k2是个位数。是个位数。是个位数。是个位数。基数：每基数：每基数：每基数：每位位位位关键字的取值关键字的取值关键字的取值关键字的取值范围。上范围。上范围
62、。上范围。上例的基为例的基为例的基为例的基为1010。链式基数排序：用链表作存储结构的基数排序链式基数排序：用链表作存储结构的基数排序链式基数排序：用链表作存储结构的基数排序链式基数排序：用链表作存储结构的基数排序47链式基数排序步骤链式基数排序步骤链式基数排序步骤链式基数排序步骤（设（设（设（设关键字关键字关键字关键字K K的的的的取值取值取值取值范围为范围为范围为范围为00，999 999 ）l l设置设置设置设置1010个队列，个队列，个队列，个队列，fifi和和和和eiei分别为第分别为第分别为第分别为第i i个队列的头指个队列的头指个队列的头指个队列的头指针和尾指针针和尾指针针和尾指
63、针针和尾指针l l第一趟分配对最低位关键字（个位）进行，改变记第一趟分配对最低位关键字（个位）进行，改变记第一趟分配对最低位关键字（个位）进行，改变记第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至录的指针值，将链表中记录分配至录的指针值，将链表中记录分配至录的指针值，将链表中记录分配至1010个链队列中，个链队列中，个链队列中，个链队列中，每个队列记录的关键字的个位相同每个队列记录的关键字的个位相同每个队列记录的关键字的个位相同每个队列记录的关键字的个位相同l l第一趟收集是改变所有非空队列的队尾记录的指针第一趟收集是改变所有非空队列的队尾记录的指针第一趟收集是改变
64、所有非空队列的队尾记录的指针第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将域，令其指向下一个非空队列的队头记录，重新将域，令其指向下一个非空队列的队头记录，重新将域，令其指向下一个非空队列的队头记录，重新将1010个队列链成一个链表个队列链成一个链表个队列链成一个链表个队列链成一个链表l l重复上述两步，进行第二趟、第三趟分配和收集，重复上述两步，进行第二趟、第三趟分配和收集，重复上述两步，进行第二趟、第三趟分配和收集，重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列分别对十位、百位进行，最后得到一个有序序列分别对
65、十位、百位进行，最后得到一个有序序列分别对十位、百位进行，最后得到一个有序序列48例初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：49505008109930063269278083184589二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930
66、063083184505278008109589269一趟收集结果：50008063083109184269278505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集结果：51算法描述算法描述算法描述算法描述算法评价算法评价算法评价算法评价l l时间复杂度：时间复杂度：时间复杂度：时间复杂度：pp分配：分配：分配：分配：T(n)=O(n)T(n)=O(n)pp收集：收集：收集：收集：T(n)=O(rd)T
67、(n)=O(rd)T(n)=O(d(n+rd)T(n)=O(d(n+rd)其中：其中：其中：其中：n n记录数记录数记录数记录数 d d关键字数关键字数关键字数关键字数 rdrd关键字取值范围关键字取值范围关键字取值范围关键字取值范围 l l空间复杂度：空间复杂度：空间复杂度：空间复杂度：S(n)=2rdS(n)=2rd个队列指针个队列指针个队列指针个队列指针+ +n n个指针域空个指针域空个指针域空个指针域空间间间间52初始状态：127810906393058918450526900808302345678910f0=0 e0=0f1=0 e1=0f2=0 e2=0f3=0 e3=0f4=0
68、 e4=0f5=0 e5=0f6=0 e6=0f7=0 e7=0f8=0 e8=0f9=0 e9=01122334456677891049300630831845052780081095892690310671925853f0=0 e0=0f1=0 e1=0f2=0 e2=0f3=0 e3=0f4=0 e4=0f5=0 e5=0f6=0 e6=0f7=0 e7=0f8=0 e8=0f9=0 e9=0134477 910493006308318450527800810958926903106719258一趟收集：31016258750500810993006326927808318458909243811065二趟收集：54750500810993006326927808318458909243811065二趟收集：f0=0 e0=0f1=0 e1=0f2=0 e2=0f3=0 e3=0f4=0 e4=0f5=0 e5=0f6=0 e6=0f7=0 e7=0f8=0 e8=0f9=0 e9=04479287928900806308310918426927850558993003102681754三趟收集：31106555
