排序算法一览（1）

第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]为待插入记录空位
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，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++)
{ 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】表插入排序示例

MAXINT 49 38 65 97 76 13 27 49
0 - - - - - - - -

MAXINT 49 38 65 97 76 13 27 49
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
2 3 1 4 0 - - - -

MAXINT 49 38 65 97 76 13 27 49
2 3 1 5 0 4 - - -

MAXINT 49 38 65 97 76 13 27 49
6 3 1 5 0 4 2 - -

MAXINT 49 38 65 97 76 13 27 49
6 3 1 5 0 4 7 2 -

MAXINT 49 38 65 97 76 13 27 49
6 8 1 5 0 4 7 2 3

图10.1
表插入排序得到一个有序的链表，查找则只能进行顺序查找，而不能进行随机查找，如折半查找。为此，还需要对记录进行重排。
重排记录方法：按链表顺序扫描各结点，将第i个结点中的数据元素调整到数组的第i个分量数据域。因为第i个结点可能是数组的第j个分量，数据元素调整仅需将两个数组分量中数据元素交换即可，但为了能对所有数据元素进行正常调整，指针域也需处理。
【算法10.3】
1. j=l->r[0].next；i=1； //指向第一个记录位置，从第一个记录开始调整
2. 若i=l->length时，调整结束；否则，
a. 若i=j，j=l->r[j].next；i++；转(2) //数据元素应在这分量中，不用调整，处理下一个结点
b. 若j>i，l->r[i].elem<-->l->r[j].elem； //交换数据元素
p=l->r[j].next； // 保存下一个结点地址
l->r[j].next=l->[i].next；l->[i].next=j； // 保持后续链表不被中断
j=p；i++；转(2) // 指向下一个处理的结点
c. 若j，while(jr[j].next；//j分量中原记录已移走，沿j的指针域找寻原记录的位置
转到(a)
【例10.3】对表插入排序结果进行重排示例

MAXINT 49 38 65 97 76 13 27 49
6 8 1 5 0 4 7 2 3

MAXINT 13 38 65 97 76 49 27 49
6 (6) 1 5 0 4 8 2 3

MAXINT 13 27 65 97 76 49 38 49
6 (6) (7) 5 0 4 8 1 3

MAXINT 13 27 38 97 76 49 65 49
6 (6) (7) (7) 0 4 8 5 3

MAXINT 13 27 38 49 76 97 65 49
6 (6) (7) (7) (6) 4 0 5 3

MAXINT 13 27 38 49 49 97 65 76
6 (6) (7) (7) (6) (8) 0 5 4

MAXINT 13 27 38 49 49 65 97 76
6 (6) (7) (7) (6) (8) (7) 0 4

MAXINT 13 27 38 49 49 65 76 97
6 (6) (7) (7) (6) (8) (7) (8) 0

图10.2
【时效分析】
表插入排序的基本操作是将一个记录插入到已排好序的有序链表中，设有序表长度为i，则需要比较至多i+1次，修改指针两次。因此，总比较次数与直接插入排序相同，修改指针总次数为2n次。所以，时间复杂度仍为O(n2)

10.2.4希尔排序(Shell’s Sort)
希尔排序又称缩小增量排序，是1959年由D.L.Shell提出来的，较前述几种插入排序方法有较大的改进。
直接插入排序算法简单，在n值较小时，效率比较高，在n值很大时，若序列按关键码基本有序，效率依然较高，其时间效率可提高到O(n)。希尔排序即是从这两点出发，给出插入排序的改进方法。
希尔排序方法：
1. 选择一个步长序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按步长序列个数k，对序列进行k趟排序；
3. 每趟排序，根据对应的步长ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅步长因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

【例10.4】待排序列为 39，80，76，41，13，29，50，78，30，11，100，7，41，86。
步长因子分别取5、3、1，则排序过程如下：
p=5 39 80 76 41 13 29 50 78 30 11 100 7 41 86
└─────────┴─────────┘
└─────────┴──────────┘
└─────────┴──────────┘
└─────────┴──────────┘
└─────────┘
子序列分别为{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}。

第一趟排序结果：
p=3 29 7 41 30 11 39 50 76 41 13 100 80 78 86
└─────┴─────┴─────┴──────┘
└─────┴─────┴─────┴──────┘
└─────┴─────┴──────┘
子序列分别为{29，30，50，13，78}，{7，11，76，100，86}，{41，39，41，80}。
第二趟排序结果：
p=1 13 7 39 29 11 41 30 76 41 50 86 80 78 100
此时，序列基本“有序”，对其进行直接插入排序，得到最终结果：
7 11 13 29 30 39 41 41 50 76 78 80 86 100

图10.3

【算法10.5】
void ShellInsert(S_TBL &p，int dk)
{ /*一趟增量为dk的插入排序，dk为步长因子*/
for(i=dk+1；i<=p->length；i++)
if(p->elem[i].key < p->elem[i-dk].key) /*小于时，需elem[i]将插入有序表*/
{ p->elem[0]=p->elem[i]； /*为统一算法设置监测*/
for(j=i-dk；j>0&&p->elem[0].key < p->elem[j].key；j=j-dk)
p->elem[j+dk]=p->elem[j]； /*记录后移*/
p->elem[j+dk]=p->elem[0]； /*插入到正确位置*/
}
}

void ShellSort(S_TBL *p，int dlta[]，int t)
{ /*按增量序列dlta[0，1…，t-1]对顺序表*p作希尔排序*/
for(k=0；k；t++)
ShellSort(p，dlta[k])； /*一趟增量为dlta[k]的插入排序*/
}

【时效分析】
希尔排序时效分析很难，关键码的 比较次数与记录移动次数依赖于步长因子序列的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的步长因子序列 的方法。步长因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：步长因子中除1外没有公因子，且最后一个步长因子必须为1。希尔排序方法是一个不稳定的排序方法。

10.3 交换排序
交换排序主要是通过两两比较待排记录的关键码，若发生与排序要求相逆，则交换之。
10.3.1冒泡排序(Bubble Sort)
先来看看待排序列一趟冒泡的过程：设1，r[1],r[2],···,r[j]为待排序列，
通过两两比较、交换，重新安排存放顺序，使得r[j]是序列中关键码最大的记录。一趟冒泡方法为：
① i=1； //设置从第一个记录开始进行两两比较
② 若i≥j，一趟冒泡结束。
③ 比较r[i].key与r[i+1].key，若r[i].key≤r[i+1].key，不交换，转⑤
④ 当r[i].key>r[i+1].key时， r[0]=r[i]；r[i]=r[i+1]；r[i+1]=r[0]；
将r[i]与r[i+1]交换
⑤ i=i+1； 调整对下两个记录进行两两比较，转②
冒泡排序方法：对n个记录的表，第一趟冒泡得到一个关键码最大的记录r[n]，第二趟冒泡对n-1个记录的表，再得到一个关键码最大的记录r[n-1]，如此重复，直到n个记录按关键码有序的表。
【算法10.6】
① j=n； //从n记录的表开始
② 若j<2，排序结束
③ i=1； //一趟冒泡，设置从第一个记录开始进行两两比较，
④ 若i≥j，一趟冒泡结束，j=j-1；冒泡表的记录数-1，转②
⑤ 比较r[i].key与r[i+1].key，若r[i].key≤r[i+1].key，不交换，转⑤
⑥ 当r[i].key>r[i+1].key时， r[i]<-->r[i+1]； 将r[i]与r[i+1]交换
⑦ i=i+1； 调整对下两个记录进行两两比较，转④
【效率分析】
空间效率：仅用了一个辅助单元。
时间效率：总共要进行n-1趟冒泡，对j个记录的表进行一趟冒泡需要j-1次关键码比较。
移动次数：
最好情况下：待排序列已有序，不需移动。
10.3.2快速排序
快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序。
一次划分方法：
设1≤p，r[p],r[p+1],...,r[q]为待排序列
① low=p；high=q； //设置两个搜索指针，low是向后搜索指针，high是向前搜索指针
r[0]=r[low]； //取第一个记录为支点记录，low位置暂设为支点空位
② 若low=high，支点空位确定，即为low。
r[low]=r[0]； //填入支点记录，一次划分结束
否则，low，搜索需要交换的记录，并交换之
③ 若low且r[high].key≥r[0].key //从high所指位置向前搜索，至多到low+1位置
high=high-1；转③ //寻找r[high].key r[low]=r[high]； //找到r[high].key，设置high为新支点位置，
//小于支点记录关键码的记录前移。
④ 若low且r[low].key从low所指位置向后搜索，至多到high-1位置
low=low+1；转④ //寻找r[low].key≥r[0].key
r[high]=r[low]； //找到r[low].key≥r[0].key，设置low为新支点位置，
//大于等于支点记录关键码的记录后移。
转② //继续寻找支点空位

【算法10.7】
int Partition(S_TBL *tbl,int low,int high) /*一趟快排序*/
{ /*交换顺序表tbl中子表tbl->[low…high]的记录，使支点记录到位，并反回其所在位置*/
/*此时，在它之前(后)的记录均不大(小)于它*/
tbl->r[0]=tbl->r[low]; /*以子表的第一个记录作为支点记录*/
pivotkey=tbl->r[low].key; /*取支点记录关键码*/
while(low从表的两端交替地向中间扫描*/
{ while(lowr[high].key>=pivotkey) high--;
tbl->r[low]=tbl->r[high]; /*将比支点记录小的交换到低端*/
while(lowr[high].key<=pivotkey) low++;
tbl->r[low]=tbl->r[high]; /*将比支点记录大的交换到低端*/
}
tbl->r[low]=tbl->r[0]; /*支点记录到位*/
return low; /*反回支点记录所在位置*/
}
【例10.5】一趟快排序过程示例
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] r[10] 存储单元
49 14 38 74 96 65 8 49 55 27 记录中关键码
low=1；high=10； 设置两个搜索指针， r[0]=r[low]； 支点记录送辅助单元，
□ 14 38 74 96 65 8 49 55 27
↑ ↑
low high
第一次搜索交换
从high向前搜索小于r[0].key的记录，得到结果
27 14 38 74 96 65 8 49 55 □
↑ ↑
low high
从low向后搜索大于r[0].key的记录，得到结果
27 14 38 □ 96 65 8 49 55 74
↑ ↑
low high
第二次搜索交换
从high向前搜索小于r[0].key的记录，得到结果
27 14 38 8 96 65 □ 49 55 74
↑ ↑
low high
从low向后搜索大于r[0].key的记录，得到结果
27 14 38 8 □ 65 96 49 55 74
↑ ↑
low high
第三次搜索交换
从high向前搜索小于r[0].key的记录，得到结果
27 14 38 8 □ 65 96 49 55 74
↑↑
low high
从low向后搜索大于r[0].key的记录，得到结果
27 14 38 8 □ 65 96 49 55 74
↑↑
low high
low=high，划分结束，填入支点记录
27 14 38 8 49 65 96 49 55 74

【算法10.8】
void QSort(S_TBL *tbl,int low,int high) /*递归形式的快排序*/
{ /*对顺序表tbl中的子序列tbl->[low…high]作快排序*/
if(low { pivotloc=partition(tbl,low,high); /*将表一分为二*/
QSort(tbl,low,pivotloc-1); /*对低子表递归排序*/
QSort(tbl,pivotloc+1,high); /*对高子表递归排序*/
}
}

【效率分析】
空间效率：快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)，即树的高度；在最坏情况下，即二叉树是一个单链，为O(n)。
时间效率：在n个记录的待排序列中，一次划分需要约n次关键码比较，时效为O(n)，若设T(n)为对n个记录的待排序列进行快速排序所需时间。
理想情况下：每次划分，正好将分成两个等长的子序列，则

T(n)≤cn+2T(n/2) c是一个常数
≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)
≤2cn+4(cn/4+T(n/8))=3cn+8T(n/8)
······
≤cnlog2n+nT(1)=O(nlog2n)

最坏情况下：即每次划分，只得到一个子序列，时效为O(n2)。
快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。