【数据结构与算法】排序

《【数据结构与算法】排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章内部排序10.1概述10.2插入排序10.2.1直接插入排序10.2.3shell排序10.3交换排序（快速排序）10.4选择排序10.4.1简单选择排序10.4.3堆排序10.5归并排序10.6基数排序10.7各种排序方法的比较讨论10.1内部排序概述排序(Sorting):将数据元素(或记录)的一个任意序列,重新排列成一个按关键字有序的序列。排序方法的稳定性：对关键字相同的数据元素，排序前后它们的领先关系保持不变，则称该排序方法是稳定的。反之，称该排序方法是不稳定的。内部排序待排序记录存放在计算机的内存中进行排序。外部排序待排序记录的数量很大，以致内存一次不能容纳全部记录，

2、在排序过程中尚需对外存进行访问的排序。排序的分类按排序过程依据的不同原则进行分类：插入排序、交换排序、选择排序、归并排序和基数排序按工作量分类，可以分为三类：(1)简单的排序方法,其时间复杂度为O(n2);(2)先进的排序方法,其时间复杂度为O(nlog2n);(3)基数排序，其时间复杂度为O(dn);排序的基本操作和记录的存储方式排序过程中需要的两种基本操作：（1）比较关键字的大小；（2）将记录从一个位置移至另一个位置。待排序记录序列可有下列三种存储方式：（1）记录存放在一组连续的存储单元中；类似于线性表的顺序存储结构，记录次序由存储位置决定，实现排序需移动记录。（2）记录存放在

3、静态链表中；记录次序由指针指示，实现排序不需移动记录，仅需修改指针。---链排序（3）记录本身存放在一组连续的存储单元中，同时另设指示各个记录存储位置的地址向量，排序过程中不移动记录本身，而移动地址向量中相应记录的地址。排序结束后再根据地址调整记录的存储位置。---地址排序待排序记录的数据类型#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;InfoTypeotherinfo;}RcdType;typedefstruct{RedTyper[MAXSIZE+1];intlength;}SqList;10.2插入排序1

4、0.2.1直接插入排序例：序列为{49，38，65，97，76，13，27，49}{(49)，38，65，97，76，13，27，49}(38){(38，49)，65，97，76，13，27，49}(65){(38，49，65)，97，76，13，27，49}(97){(38，49，65，97)，76，13，27，49}(76){(38，49，65，76，97)，13，27，49}(13){(13，38，49，65，76，97)，27，49}(27){(13，27，38，49，65，76，97)，49}(49){(13，27，38，49，49，65，76，97)}直接插入排序算法vo

5、idInsertSort(SqList&L){for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){L.r[0]=L.r[i];//复制为哨兵for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];}}//InsertSort时间：最坏情形判断与移动各接近n(n+1)/2;最好情形判断n次，无移动；故时间复杂度：O(n2)空间：一个辅助空间10.2.2Shell排序算法基本思想：先将整个待排序记录序列分割成若干子序列分别进行直接

6、插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序。算法复杂度：O(n3/2)Shell排序举例（非稳定的）二趟结果{13，04，49，38，27，49，55，65，97，76}增量取1：13，04，49，38，27，49，55，65，97，76三趟结果{04，13，27，38，49，49，55，65，76，97}一趟结果{13，27，49，55，04，49，38，65，97，76}增量取3：13553876270465494997例：{49，38，65，97，76，13，27，49，55，04}增量取5：4913382765499755760410.3交换排序1

7、.冒泡排序（其时间复杂度O(n2)）初始关键字第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后第六趟排序后例：49383838381313384949491327276565651327383897761327494976132749491327496527497649972.快速排序-----对冒泡排序的一种改进基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，则可分别对这两部分记录继续分别进行