排序算法一览

《排序算法一览》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排序算法一览第10章排序10.1基本概念排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据表是按关键码有序的。如有序表的折半查找，查找效率较高。还有，二叉排序树、B-树和B+树的构造过程就是一个排序过程。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可能不唯一，这是因为具有相同关键码的数据元

2、素，这些元素在排序结果中，它们之间的的位置关系与排序前不能保持。若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。排序分为两类：内排序和外排序。内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。10.2插入排序10.2.1直接插入排序设有n个记录，存放在数组r中，重新安排记

3、录在数组中的存放顺序，使得按关键码有序。即r[1].key≤r[2].key≤……≤r[n].key先来看看向有序表中插入一个记录的方法：设１<ｊ≤ｎ，r[1].key≤r[2].key≤……≤r[j-1].key，将r[j]插入，重新安排存放顺序，使得r[1].key≤r[2].key≤……≤r[j].key，得到新的有序表，记录数增１。【算法10.1】①r[0]=r[j]；//r[j]送r[0]中，使r[j]为待插入记录空位i=j-1；//从第i个记录向前测试插入位置，用r[0]为辅助单元，可免去测试i<1。②

4、若r[0].key≥r[i].key，转④。//插入位置确定③若r[0].key

5、整待插入位置21018□25i=3，r[0]

6、voidInsertSort(S_TBL&p){for(i=2；i<=p->length；i++)if(p->elem[i].keyelem[i-1].key)/*小于时，需将elem[i]插入有序表*/{p->elem[0].key=p->elem[i].key；/*为统一算法设置监测*/for(j=i-1；p->elem[0].keyelem[j].key；j--)p->elem[j+1].key=p->elem[j].key；/*记录后移*/p->elem[j+1].key=p->elem[0

7、].key；/*插入到正确位置*/}}【效率分析】空间效率：仅用了一个辅助单元。时间效率：向有序表中逐个插入记录的操作，进行了n-1趟，每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。最好情况下：即待排序列已按关键码有序，每趟操作只需1次比较2次移动。总比较次数=n-1次总移动次数=2(n-1)次最坏情况下：即第j趟操作，插入记录需要同前面的j个记录进行j次关键码比较，移动记录的次数为j+2次。平均情况下：即第j趟操作，插入记录大约同前面的j/2个记录进行关键码比较，

8、移动记录的次数为j/2+2次。由此，直接插入排序的时间复杂度为O(n2)。是一个稳定的排序方法。10.2.2折半插入排序直接插入排序的基本操作是向有序表中插入一个记录，插入位置的确定通过对有序表中记录按关键码逐个比较得到的。平均情况下总比较次数约为n2/4。既然是在有序表中确定插入位置，可以不断二分有序表来确定插入位置，即一次比较，通过待插入记录与有序表居中