简单插入排序堆排序
一、简单插入排序
二、折半插入排序
三、希尔插入排序
一、简单插入排序
基本思想
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 13 | 27 | 38 | 49 | 65 | 76 | 97 | 99 |
处理第i个数据时：
STEP1:将处理数据与前面紧邻数据进行比较，若符合有序，则无需任何操作，否则转STEP2。
STEP2:类似顺序查找，绿色的0号空间设置为监视哨。
STEP：自位置I-1向前搜索比较过程中，同时后移较大记录。
算法代码：
void InsertSort（SqList *L）
{
for(i=2;i<=L.length;i++)
if(L.elem[i].key<L.elem[i-1].key)
{
L.elem[0] = L.elem[i];
for(j=i-1;L.elem[0].key<L.elem[j].key;j--)
L.elem[j+1] = L.elem[j];
L.elem[j+1] = L.elem[j];
}
}
性能分析
（1）最好情况O(n)
本身有序：每个记录只需和其前面相邻的记录比较1次，共n-1次，且没有任何数据移动。
（2）最坏情况O(n²)
比较次数：i= 2+3+4...+n=½n² +½n-1
移动次数：（i+1）=3+4+...+(n+1)
= ½n² +(3/2)n-2
（3）平均性能O（n²）
假设最好最坏等都是等概率出现，则
| 最好情况 | 最差情况 | 平均情况 | |
| 比较次数 | n | ½n² +½n-1 | O(n²) |
| 移动次数 | 0 | ½n² +(3/2)n-2 | O(n²) |
性能改进
经验1：在进行某一趟记录排序时，其前面记录已经有序-------折半插入排序
经验2：若记录趋向有序时，记录的比较与移动次数相对较少。------希尔插入排序
二、折半插入排序
基本思想
首先：通过折半查找法获取其在前面应该插入的位置j。
其次：将待排序位置i的记录放入哨兵站。
然后：将位置i-1到位置j之间的数据依次后移。
最后：将待排序记录插入到位置j
void BinInsertSort(SqList *L)
{
for(i=2;i<=L.length;i++){
L.elem[0] = L.elem[i]; low=1; high=i-1;
while(low <= high){
mid = (low + high)/2;
if(L.elem[0].key< L.r[mid].key) high = mid -1;
else low = mid +1;}
for(j=i-1; j>=high+1; --j) L.elem[j+1] = L.elem[j];
L.elem[high+1]=L.elem[0];
}
}
性能分析
理论上折半插入排序因为比较次数减少而提升性能。
不能达到减少比较次数的效果。
三、希尔插入排序
基本思想
性能优秀条件：源数据有序、记录量较少
基本有序：小的基本在前面，大的基本在后面，不大不小的基本在中间
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 27 | 38 | 13 | 49 | 52 | 65 | 97 | 76 | 85 |
首先：采用跳跃分割法进行数据分组，间隔因子d为等差
其次：组内采用插入法排序
然后：采用多次分组，渐进基本有序
最后：保障最后1次分组间隔为1，也就是全局排序
举例：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 21 | 23 | 25 | 27 | 29 | 22 | 24 | 26 | 28 | 30 |
根据等差5拆分排列：
依次进行比较：1和6
依次进行比较：2和7
依次进行比较：3和8
依次进行比较：4和9
依次进行比较：5和10
最后进行普通插入排序。
算法实现代码：
void ShellInsert(SqList *L,int dk){
for(i = dk +1;i<=L.length;i++)
if(L.elem[i].key < L.[i-dk].key)
{
L.elem[0] = L.elem[i];
for(j =i-dk; j>0&& L.elem[0].key<L.elem[j].key;j-=dk)
L.elem[j+dk]=L.elem[j];
L.elem[j+dk] = L.elem[0];
}
}
性能分析
delta[k] = 2(t-k+1)次方-1 O(n(3/2)次方）
其中：0<= k <= t <=[log2(n+1)]
注意：间隔序列之间互素，最后1个因子为1。
假设数据量是100万，两种排序的总次数大约是多少？
基本插入排序 n/4 * n
25万 * 100万 = 2500亿次
希尔插入排序√n * n
0.1万 * 100万 = 10亿次
数据推导可知：
16是分界点，如果元素个数超过16个，性能体现会更显著！