文档介绍：《数据结构排序》
数据结构课程的内容
概述
插入排序
交换排序
选择排序
归并排序
基数排序
第9章 内部排序
概述
1. 什么是排序？
将一组杂乱无章的冲或暂存单元（Temp）。则程序执行过程为：
21
25
49
25*
21
初态：
16
49
25*
25
21
16
08
完成!
时间效率： O(n2)——因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n2)。其他情况下还要加上移动元素的次数。
空间效率：O（1）——因为仅占用1个缓冲单元
算法的稳定性：稳定——因为25*排序后仍然在25的后面。
对应程序参见教材P265。
若设待排序的对象个数为n，则算法需要进行n-1次插入。
最好情况下，排序前对象已经按关键码大小从小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键码比较 1 次，移动 2 次对象。因此，总的关键码比较次数为n-1，对象移动次数为 2(n-1)。
直接插入排序的算法分析
最坏情况下，第i趟插入时，第i个对象必须与前面i-1个对象都做关键码比较，并且每做 1 次比较就要做 1 次数据移动。则总的关键码比较次数KCN和对象移动次数RMN分别为
若待排序对象序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键码比较次数和对象移动次数约为 n2/4。因此，直接插入排序的时间复杂度为 o(n2)。
直接插入排序是一种稳定的排序方法。
2） 折半插入排序
优点：比较的次数大大减少，全部元素比较次数仅为O(nlog2n)。
时间效率：虽然比较次数大大减少，可惜移动次数并未减少，所以排序效率仍为O(n2) 。
空间效率： O（1）
稳定性：稳定
对应程序见教材P267（仅用于顺序表）
新元素插入到哪里？
讨论：若记录是链表结构，用直接插入排序行否？折半插入排序呢？
答：直接插入不仅可行，而且还无需移动元素，时间效率更高！
折半插入排序的改进——2-路插入排序见教材P267。
在已形成的有序表中折半查找，并在适当位置插入，把原来位置上的元素向后顺移。
但链表无法“折半”！
折半插入排序的算法分析
折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。
在插入第 i 个对象时，需要经过 log2i +1 次关键码比较，才能确定它应插入的位置。因此，将 n 个对象用折半插入排序所进行的关键码比较次数为：n*log2n
折半插入排序是一个稳定的排序方法。
3）表插入排序
基本思想：在顺序存储结构中，给每个记录增开一个指针分量，在排序过程中将指针内容逐个修改为已经整理（排序）过的后继记录地址。
优点：在排序过程中不移动元素，只修改指针。
回忆：
链表排序——排序时只移动指针；
地址排序——排序时先移动地址，最后再移动记录。
此方法具有链表排序和地址排序的特点。
1
例：关键字序列 T=(21，25，49，25*，16，08）， 请写出表插入排序的具体实现过程。
解：假设该序列（结构类型)已存入一维数组V[7]中，将V[0]作为表头结点。则算法执行过程为：
i
关键字 V[i].key
指针 V[i].link
0
MaxNum
1
21
2
25
3
49
4
25*
5
16
6
08
指向第1个元素
指向头结点
初态
i=1
i=2
i=3
i=4
i=5
i=6
0
3
4
5
6
5
0
3
1
0
2
*表示后一个25
int LinkInsertSort ( staticlinklis<Type> & list ) {
[0].Key = MaxNum;
[0]. Link = 1;
[1].Link = 0; //形成循环链表
表插入排序的算法
for ( int i = 2; i <= ; i++ ) {
int current = [0]. Link; //current=当前记录指针
int pre = 0; //pre=当前记录current的前驱指针
while ( [current]. Key <= [i]. Key)