插入排序(直接插入排序、折半插入排序、希尔排序)

前言

插入排序主要分为：直接插入排序、折半插入排序、希尔排序

思想：每步将一个待排序对象与前面已排序序列进行比较并插入到适当的位置上。

应用：打扑克牌、打麻将时你所用到的排序方法

一、直接插入排序

算法思想:

当存在一个待排序表，$L[1…n]$，某状态下：

有序序列$L[1…i-1]$	$L[i]$	无序序列$L[i+1…n]$

查找$L[i]$在$L[1…i-1]$中的插入位置$k$。
将$L[k…i-1]$所有元素往后移动一个位置
将$L[i]复制到L[k]$.

模拟实现：

序	0(哨兵)	1	2	3	4	5	6	7	8
初始化	0	49	38	65	97	79	13	27	49
i=2	38	38	49	65	97	79	13	27	49
i=3	65	38	49	65	97	79	13	27	49
i=4	97	38	49	65	97	79	13	27	49
i=5	79	38	49	65	79	97	13	27	49
i=6	13	13	38	49	65	79	97	27	49
i=7	27	13	27	38	49	65	79	97	49
i=8	49	13	27	38	49	49	65	79	97

算法实现：

void sort(int A[],int n){
    int i,j;
    for(i = 2;i <= n;i++){
        if(A[i] < A[i-1]){
            A[0] = A[i];
            for(j = i - 1;A[0]<A[j];--j){
                A[j+1] = A[j];
            }
            A[j+1] = A[0];
        }
    }
}

算法评估：

空间效率：$O(1)$
时间效率：

最少进行$n-1$次，最多走$n(n-1)/2$次
$O(n)$

稳定性：是
适用性：适合顺序表和链表

二、折半插入排序

算法思想:

直接插入排序每次比较都是倒序寻找，对于有序的前面序列，采用二分查找较少比较元素的次数。

算法实现：

void sort(int A[],int n){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){
        A[0] = A[i];
        low = 1; hight = i-1;
        while(low<=high){
            mid = (low+high)/2;
            if(A[mid] > A[0])high = mid - 1;
            else low = mid + 1;
        }

        for(j=i-1;j>=high+1;--j){
            A[j+1] = A[j];
        }

        A[high+1] = A[0];
    }
}

算法评估：

空间效率：$O(1)$
时间效率：

$O(n^2)$

稳定性：是

三、希尔排序

算法思想:

对于直接插入排序，在最坏情况下，即序列是倒叙的存在，此时每次移动仅为一步，希尔排序应用了移动一大步的思想，即增量。

算法模拟：

序	轮	步长	0	1	2	3	4	5	6	7	8	9
-	1	5	49	38	65	97	76	13	27	49	55	04
-	-	-	I	——	——	——	——	I
-	-	-	-	I	——	——	——	——	I
-	-	-	-	-	I	——	——	——	——	I
-	-	-	-	-	-	I	——	——	——	——	I
-	-	-	-	-	-	-	I	——	——	——	——	I
-	结果	-	13	27	49	55	04	49	38	65	97	76
-	2	3	13	27	49	55	04	49	38	65	97	76
-	-	-	I	——	——	I	——	——	I	——	——	I
-	-	-	-	I	——	——	I	——	——	I
-	-	-	-	-	I	——	——	I	——	——	I
-	结果	-	13	04	49	38	27	49	55	65	97	76
-	3	1	13	04	49	38	27	49	55	65	97	76
-	结果	-	04	13	27	38	49	49	55	65	76	97

算法实现：

void sort(int A[],int n){
    int dk,j,k;
    for(dk = n/2;dk >= 1;dk = dk / 2){
        for(i = dk+1;i<=n;++i){
            if(A[i]<A[i-dk]){
                A[0] = A[i];
                for(j = i-dk;j>0 && A[0]<A[j]j-=dk){
                    A[j+dj] = A[j];
                }
                A[j+dk] = A[0];
            }
        }
    }
}

（看着就头疼快乐系列）

算法评估：

空间效率：$O(1)$
时间效率：1$次，最多走$n(n-1)/2$次

平均$O(n^{1.3})$
最坏$O(n^2)$

稳定性：否
适用性：仅适用于线性表的顺序存储