直接插入排序

插入排序的基本思想是，每次将一个待排序元素插入到前面已经排好序元素中的适当位置，直到全部元素插入完成为止。其中，直接插入排序是最简单的插入排序。

排序思路

将待排序的数组R[0..n-1]分为两个部分[0..i-1]和[i..n-1]。其中[0..i-1]为有序区间，[i..n-1]为无序区间。

对于第i趟排序（这里规定第一趟排序从R[1]开始,毕竟一个单独字符R[0]不需要排序嘛！），[0..i-1]已经为有序区间。将元素R[i]分别于之前的每一个元素进行比较，在有序区找到合适的位置后，将R[i]插入该位置。

注：比较顺序可以从0到i-1，也可以从i-1到0。本例将以i-1到0为例。

以c为例,从小到大排序

排序算法

#include<stdio.h>

void insert_sort(int R[],int n){
    int tmp,i,j;
    for(i=1;i<n;i++){
        if(R[i]<R[i-1]){
            tmp=R[i];//记录下R[i]的值，方便插入
            j=i-1;//将i前的元素逐个后移，直到前面的元素不大于tmp
            while(j>=0&&R[j]>tmp){
                R[j+1]=R[j];
                j--;
            }
            R[j+1]=tmp;
        }
        //打印第i趟排序后的结果
        printf("%d: ",i);
        int k;
        for (k = 0; k < n;k++){
            printf("%d ", R[k]);
        }
        printf("\n");
    }
}
int main(void){
    int a[] = {9,8,7,6,5,4,3,2,1,0};
    insert_sort(a, 10);
}

动图演示：

图片来自：https://visualgo.net

输出结果：

1: 8 9 7 6 5 4 3 2 1 0
2: 7 8 9 6 5 4 3 2 1 0
3: 6 7 8 9 5 4 3 2 1 0
4: 5 6 7 8 9 4 3 2 1 0
5: 4 5 6 7 8 9 3 2 1 0
6: 3 4 5 6 7 8 9 2 1 0
7: 2 3 4 5 6 7 8 9 1 0
8: 1 2 3 4 5 6 7 8 9 0
9: 0 1 2 3 4 5 6 7 8 9

算法分析

时间复杂度：

平均情况：

平均比较次数i/2,平均移动次数i/2+2

$$ \sum_{i=1}^{n-1} (\frac{i}{2} + \frac{i}{2}+2)=\frac{(n-1)(n+4)}{2}=O(n^2) $$

最坏情况：一开始元素就是有序从大到小的，时间复杂度为O(n^2^)
最好情况：一开始元素就是有序从小到大的，时间复杂度为O(n)

空间复杂度：

只使用了i，j，tmp三个辅助变量，与问题规模n无关。空间复杂度为O(1)

稳定性：

插入时判断条件为R[i]<R[i-1]以及移动时条件为R[j]>tmp，故相同元素的相对位置不变。这是一种稳定的排序方法。

复杂性：

简单

归位：

否，不是全局有序。

本文由 ukuq 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jan 25, 2019 at 10:44 pm