算法思想

每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

直接插入排序

1
2
3
4
5
6
7
8
9
10
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1;i<n;i++)
        if(A[i]<A[i-1]){
        temp=A[i];
        for(j=i-1;j>=0 && A[j]>temp;j--)
            A[j+1]=A[j];
        A[j+1]=temp;
    }
}

折半插入排序

用A[0]暂存目标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void InsertSort(int A[], int n){ 
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){
        A[0] = A[i];                    //将A[i]暂存A[0]
        low = 1; high = 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]
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def InsertSort(nums,n):
    for i in range(len(nums)):
        temp=nums[i]
        low=0
        high=i-1
        while low<=high:
            mid=int((low+high)/2)
            if temp>nums[mid]:
                low=mid+1
            else:
                high=mid-1
        for j in range(i-1,high,-1):
            nums[j+1]=nums[j]
        nums[high+1]=temp
return nums

希尔排序

1
2
3
4
5
6
7
8
9
10
11
void ShellSort(int A[];int n){
    int d;
    for(d=n/2;d>=1;d=d/2)
        for(i=1+d;i<=n;i++)
            if(A[i]<A[i-d]){
                A[0]=A[i];
                for(j=i-d;j>0&&A[0]<A[j];j-=d)
                    A[j+d]=A[j];
                A[j+d]=A[0];
            }
}

算法效率分析

  • 空间效率：空间复杂度=O(1)

  • 时间效率: 最坏情况下时间复杂度=O(n²)

  • 稳定性：希尔排序是一种不稳定的排序方法