第10章 排序
10.1基本概念
排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
是按关键码有序的。如有序表的折半查找，查找效率较高。还有，二叉排序树、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]为待插入记录空位
i=j-1； //从第i个记录向前测试插入位置，用r[0]为辅助单元， 可免去测试i<1。
② 若r[0].key≥r[i].key，转④。 //插入位置确定
③ 若r[0].key < r[i].key时，
r[i+1]=r[i]；i=i-1；转②。 //调整待插入位置
④ r[i+1]=r[0]；结束。 //存放待插入记录
【例10.1】向有序表中插入一个记录的过程如下：
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
i=1，r[0] ≥r[i]，r[i+1]=r[0]； 插入位置确定，向空位填入插入记录
2 9 10 18 25 向有序表中插入一个记录的过程结束
直接插入排序方法：仅有一个记录的表总是有序的，因此，对n个记录的表，可从第二个记录开始直到第n个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。
【算法10.2】
void InsertSort(S_TBL &p)
{ for(i=2；i<=p->length；i++)
if(p->elem[i].key < p->elem[i-1].key) /*小于时，需将elem[i]插入有序表*/
{ p->elem[0].key=p->elem[i].key； /*为统一算法设置监测*/
for(j=i-1；p->elem[0].key < p->elem[j].key；j--)
p->elem[j+1].key=p->elem[j].key； /*记录后移*/
p->elem[j+1].key=p->elem[0].key； /*插入到正确位置*/
}
}
【效率分析】
空间效率：仅用了一个辅助单元。
时间效率：向有序表中逐个插入记录的操作，进行了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=1；high=j-1；r[0]=r[j]； // 有序表长度为j-1，第j个记录为待插入记录
//设置有序表区间，待插入记录送辅助单元
② 若low>high，得到插入位置，转⑤
③ low≤high，m=(low+high)/2； // 取表的中点，并将表一分为二，确定待插入区间*/
④ 若r[0].key
length；i++)
{ s->elem[0]=s->elem[i]； /* 保存待插入元素 */
low=i；high=i-1； /* 设置初始区间 */
while(low<=high) /* 该循环语句完成确定插入位置 */
{ mid=(low+high)/2；
if(s->elem[0].key>s->elem[mid].key)
low=mid+1； /* 插入位置在高半区中 */
else high=mid-1； /* 插入位置在低半区中 */
}/* while */
for(j=i-1；j>=high+1；j--) /* high+1为插入位置 */
s->elem[j+1]=s->elem[j]； /* 后移元素，留出插入空位 */
s->elem[high+1]=s->elem[0]； /* 将元素插入 */
}/* for */
}/* InsertSort */
【时间效率】
确定插入位置所进行的折半查找，关键码的比较次数至多为 ，次，移动记录的次数和直接插入排序相同，故时间复杂度仍为O(n2)。是一个稳定的排序方法。
10.2.3表插入排序
直接插入排序、折半插入排序均要大量移动记录，时间开销大。若要不移动记录完成排序，需要改变存储结构，进行表插入排序。所谓表插入排序，就是通过链接指针，按关键码的大小，实现从小到大的链接过程，为此需增设一个指针项。操作方法与直接插入排序类似，所不同的是直接插入排序要移动记录，而表插入排序是修改链接指针。用静态链表来说明。
#define SIZE 200
typedef struct{
ElemType elem； /*元素类型*/
int next； /*指针项*/
}NodeType； /*表结点类型*/
typedef struct{
NodeType r[SIZE]； /*静态链表*/
int length； /*表长度*/
}L_TBL； /*静态链表类型*/
假设数据元素已存储在链表中，且0号单元作为头结点，不移动记录而只是改变链指针域，将记录按关键码建为一个有序链表。首先，设置空的循环链表，即头结点指针域置0，并在头结点数据域中存放比所有记录关键码都大的整数。接下来，逐个结点向链表中插入即可。
【例10.2】表插入排序示例
0 1 2 3 4 5 6 7 8
key 域
next 域
初始状态
MAXINT
49
38
65
97
76
13
27
49
0
-
-
-
-
-
-
-
-
浙公网安备 33021202002483