第9章排序

第9章排序lirui@nwnu.edu.cn*第9章排序9.1插入排序9.2交换排序9.3选择排序9.4归并排序9.5基数排序9.6各种内部排序方法的比较讨论*9.1插入排序一、直接插入排序二、折半插入排序三、希尔排序*一、直接插入排序直接插入排序的基本操作是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增加1的有序表。例如：已知待排序的一组记录的初始排列如下所示：R（49），R（38），R（65），R（97），R（76），R（13），R（27），R（19）。*假设在排序过程中，前四个记录已按关键字递增的次序，重...

lirui@nwnu.edu.cn*第9章排序9.1插入排序9.2交换排序9.3选择排序9.4归并排序9.5基数排序9.6各种内部排序方法的比较讨论*9.1插入排序一、直接插入排序二、折半插入排序三、希尔排序*一、直接插入排序直接插入排序的基本操作是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增加1的有序表。例如：已知待排序的一组记录的初始排列如下所示：R（49），R（38），R（65），R（97），R（76），R（13），R（27），R（19）。*假设在排序过程中，前四个记录已按关键字递增的次序，重新排列，构成一个含4个记录的有序序列:现要将第5个（关键字为76）的记录插入上述序列，可以得到一个新的含5个记录的有序序列，则首先要找到插入的位置，然后进行插入。假设从R（97）起向左进行顺序查找，由于657697，则R（76）应插入在R（65）和R（97）之间，从而得到下列新的有序序列:{R（38），R（49），R（65），R（76），R（97）}（2）称从式（1）到式（2）的过程为一趟直接插入排序。{38，49，65，97}（1）*一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r[1…i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列r[1…i]；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r[0]处设置监视哨。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序序列的子序，然后从第2个记录起逐个进行插入直至整个序列变成按关键字非递减有序序列为止。在自i-1起往前搜索的过程中，可以同时后移记录。*例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827排序结果：(13273849657697)*记录按关键字非递增有序排列时比较的次数达最大值记录移动次数达到最大值关键字间的比较次数和移动记录的次数,约为n2/4。由此，直接插入排序的时间复杂度为O（n2）。记录按关键字非递减有序排列时比较的次数达最小值:记录不需要移动。*二、折半插入排序插入排序的基本操作是在一个有序表中进行查找和插入，则从上章的讨论可知，这个“查找”操作可利用“折半查找”来实现，由此进行的插入排序称之为折半插入排序。*i=1(30)1370853942620i=213(1330)70853942620…...i=820(613203039427085)折半插入排序i=820(6133039427085)20lowhighmidi=820(6133039427085)20lowhighmidi=820(6133039427085)20lowhighmidi=820(6133039427085)20lowhigh*三、希尔排序基本思想：先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。排序过程：先取一个正整数d1 分析起泡排序的效率，若初始序列为“正序”，则只需进行一趟排序，在排序过程中进行n-1次关键字间的比较；反之，若初序列“逆序”，则需进行n-1趟排序，需进行次比较。并作等数量级的记录移动，因此，总的时间复杂度为O（n2）。*二、快速排序其基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。*由此，可以该“枢轴”记录最后所落的位置最作分界线，将序列{L.r[s]，L.r[s+1]，…，L.r[t]}分割成两个子序列{L.r[s]，L.r[s+1]，…，L.r[i-1]}和{L.r[i+1]，L.r[i+2]，…，L.r[t]}，这个过程称作一趟快速排序。一趟快速排序的具体做法是：对r[s……t]中记录进行一趟快速排序，附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为Pivotkey，然后从low所指位置起向后搜索找到第一个关键字大于Pivotkey的记录和枢轴记录相互交换做，重复这两步直至low=high。首先从high所指位置起向前搜索找到第一个关键字小于Pivotkey的记录和枢轴记录相互交换，*X初始关键字：4938659776132750lowhigh4927lowhighlowhighlowhigh6549lowhigh4913lowhigh9749lowhighlowhigh完成一趟排序：(273813)49(76976550)*分别进行快速排序(13)27(38)49(5065)76(97)快速排序结束：13273849506576*通常，快速排序平均时间复杂度为O(nlogn)，但待排序记录的键值几乎已排序时，情况反而恶化，每一趟快速排序的基准记录位置就是第一个记录位置或最后一个记录位置。最坏情况下的时间复杂度为T(n)=O(n²)。快速排序的平均时间为Tavg(n)=knlnn，其中n为待排序序列记录的个数，k为某个常数，经验证明，在所有同数量级的此类（先进的）排序方法中，快速排序的常数因子k最小。因此，就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法。快速排序递归算法需要栈空间来实现递归，一般情况下需要的空间为S(n)=O(log2n)，最坏情况下，需要的栈空间为S(n)=O(n)。快速排序方法是不稳定的。*9.3选择排序一、简单选择排序二、树形选择排序三、堆排序*一、简单选择排序一趟简单选择排序的操作为：通过n-1次关键字的比较，从n个记录中选择出关键字最小的记录，并和第1个记录交换。再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第2个记录交换重复上述操作，共进行n-1趟排序后，排序结束.*初始：[49386597761327]jkkkkkkjji=11349一趟:13[386597764927]i=2jjkkkkk2738二趟:1327[6597764938]三趟:132738[97764965]*五趟:1327384965[9776]六趟:132738496576[97]排序结束:13273849657697四趟:13273849[769765]*简单选择排序过程中，所需进行记录移动的操作次数较少，其最小值为0，最大值为3(n-1)。然而，无论记录的初始排列如何，所需进行的关键字间的比较次数相同，均为(n(n-1))/2。因此，总的时间复杂度也是O（n2）。算法描述与算法评价 *二、树形选择排序树形选择排序，又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法首先对n个记录的关键字进行两两比较，然后在其中n/2个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。*386549977613274938651327381313树形选择排序示例*树形选择排序示例3865499776274938657627382727输出13之后*树形选择排序示例38654997764938657649384938输出13、27之后*或(i=1,2,…...n/2)kik2ikik2i+1kik2ikik2i+1三、堆排序2、堆和完全二叉树堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）1、堆的定义n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆*例（13,38,27,50,76,65,49,97）1327384965765097*3、堆排序：若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则可得到n个元素的次小值；如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。实现堆排序需解决的两个问题如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？二个问题解决方法——筛选*4、筛选13273849657650979727384965765013输出：13*2749389765765013输出：139749382765765013输出：1327*3849502765769713输出：13276549502738769713输出：132738*4965502738769713输出：1327387665502738499713输出：13273849*5065762738499713输出：132738499765762738495013输出：1327384950*6597762738495013输出：13273849509765762738495013输出：132738495065*7665972738495013输出：132738495065769765762738495013输出：1327384950657697*5、建堆建堆：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选*49653827137697504965382713765097例如含8个元素的无序序列（49，38，65，97，76，13，27，50）*4913382765765097491338276576509713494927*时间复杂度：最坏情况下T(n)=O(nlogn)空间复杂度：S(n)=O(1)总共进行的比较的次数为：<2(log2(n-1)+log2(n-2)+……+log22))<2n(log2n)由此，堆排序在最坏的情况下，其时间复杂度为O(nlogn)。*初始关键字:[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]9.4归并排序*时间复杂度：T(n)=O(nlog2n)空间复杂度：S(n)=O(n)与快速排序和堆排序相比，归并排序的最大特点，它是一种稳定的排序方法。但在一般情况下，很少利用2路归并排序方法进行内部排序。*9.5基数排序一、多关键字排序二、链式基数排序*2<3<……<A<2<3<……<A<2<3<……<A<2<3<……<A一、多关键字排序已知扑克牌中52张牌面的次序为：两个关键字：花色（<<<）面值（2<3<……

                    本文档为【第9章  排序】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

第9章 排序

你可能还喜欢

第9章排序