经典的排序算法一览表

排序算法一览

第 10 章 排序

10.1 基本概念

排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素

某个项值有序的序列。作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算

机中的数据表是按关键码有序的。如有序表的折半查找，查找效率较高。还有，二叉排序树、 B-树和 B+树的构造过

程就是一个排序过程。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次

外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。

10.2 插入排序

10.2.1 直接插入排序

设有 n 个记录，存放在数组 r 中，重新安排记录在数组中的存放顺序，使得按关键码有序。即

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]为待插入记录空位

r[1] r[2] r[3] r[4] r[5] 存储单元

2 10 18 25 9 将 r[5]插入四个记录的有序表中，j=5

r[0]=r[j]；i=j-1； 初始化，设置待插入位置

2 10 18 25 □ r[i+1]为待插入位置

i=4，r[0] < r[i]，r[i+1]=r[i]；i--； 调整待插入位置

2 10 18 □ 25

i=3，r[0] < r[i]，r[i+1]=r[i]；i--； 调整待插入位置

2 10 □ 18 25

i=2，r[0] < r[i]，r[i+1]=r[i]；i--； 调整待插入位置

2 □ 10 18 25

逐个向有序表中进行插入操作，从而得到 n 个记录按关键码有序的表。

【算法 10.2】

{ for(i=2；i<=p->length；i++)

if(p->elem[i].key < p->elem[i-1].key) /*小于时，需将 elem[i]插入有序表*/

空间效率：仅用了一个辅助单元。

时间效率：向有序表中逐个插入记录的操作，进行了 n-1 趟，每趟操作分为比较关键码和移动记录，而比较的次数和

移动记录的次数取决于待排序列按关键码的初始排列。

最好情况下：即待排序列已按关键码有序，每趟操作只需 1 次比较 2 次移动。

总比较次数=n-1 次

总移动次数=2(n-1)次

最坏情况下：即第 j 趟操作，插入记录需要同前面的 j 个记录进行 j 次关键码比较，移动记录的次数为 j+2 次。

平均情况下：即第 j 趟操作，插入记录大约同前面的 j/2 个记录进行关键码比较，移动记录的次数为 j/2+2 次。

由此，直接插入排序的时间复杂度为 O(n2)。是一个稳定的排序方法。

10.2.2 折半插入排序

直接插入排序的基本操作是向有序表中插入一个记录，插入位置的确定通过对有序表中记录按关键码逐个比较得到的。

平均情况下总比较次数约为 n2/4。既然是在有序表中确定插入位置，可以不断二分有序表来确定插入位置，即一次比

③ low≤high，m=(low+high)/2； // 取表的中点，并将表一分为二，确定待插入区间*/

④ 若 r[0].key<r[m].key，high=m-1； //插入位置在低半区

否则，low=m+1； // 插入位置在高半区

转②

⑤ high+1 即为待插入位置，从 j-1 到 high+1 的记录，逐个后移，r[high+1]=r[0]；放置待插入记录。

【算法 10.3】

void InsertSort(S_TBL *s)

{ /* 对顺序表 s 作折半插入排序 */

for(i=2；i<=s->length；i++)

while(low<=high) /* 该循环语句完成确定插入位置 */

if(s->elem[0].key>s->elem[mid].key)

low=mid+1； /* 插入位置在高半区中 */

else high=mid-1； /* 插入位置在低半区中 */

for(j=i-1；j>=high+1；j--) /* high+1 为插入位置 */

s->elem[j+1]=s->elem[j]； /* 后移元素，留出插入空位 */

}/* for */

}/* InsertSort */

确定插入位置所进行的折半查找，关键码的比较次数至多为 ，次，移动记录的次数和直接插入排序相同，故时间复杂

直接插入排序、折半插入排序均要大量移动记录，时间开销大。若要不移动记录完成排序，需要改变存储结构，进行

表插入排序。所谓表插入排序，就是通过链接指针，按关键码的大小，实现从小到大的链接过程，为此需增设一个指

针项。操作方法与直接插入排序类似，所不同的是直接插入排序要移动记录，而表插入排序是修改链接指针。用静态

链表来说明。

ElemType elem； /*元素类型*/

int next； /*指针项*/

}NodeType； /*表结点类型*/

NodeType r[SIZE]； /*静态链表*/

int length； /*表长度*/

}L_TBL； /*静态链表类型*/

1 0 - - - - - - -

MAXINT 49 38 65 97 76 13 27 49

2 0 1 - - - - - -

MAXINT 49 38 65 97 76 13 27 49

2 3 1 0 - - - - -

MAXINT 49 38 65 97 76 13 27 49