排序3-插入排序

插入排序把排序对象分成已排序和未排序两个部分, 每次选取未排序部分的首元素, 将它插入已排序部分的合适部分

插入排序(正序)

//插入排序
void insertSort(int arr[], int length){
    int j;
    for(int i=1; i<length; i++){ // i是无序部分首元素的下标
        if(arr[i]<arr[i-1]){ //如果无序部分的首元素小于有序部分的最大值, 进入排序, 否则跳过本次循环
            int tmp = arr[i]; //tmp存储无序部分的首元素
            for(j=i-1; j>=0 && tmp<arr[j]; j--){ // j指向i之前的元素, 如果arr[j]<tmp或j<0, 循环结束
                arr[j+1] = arr[j]; //如果tmp < arr[j], 将arr[j]元素前移至arr[j+1]位置
            } 
            arr[j+1] = tmp; //将tmp赋值给arr[j+1]
        }
    }
}

最优情况: 当排序内容本身都是顺序(相对于要求的排序方式来说)的, 则只需要遍历一次内容,就可完成排序, 此时时间复杂度是 O(n).

最差情况: 如果排序内容本身都是逆序的, 时间复杂度为 O(n^2), 但相对于选择排序与冒泡效率, 插入排序的效率还是更高.

同样排序内容中, n=10000时, 插入排序与选择排序, 冒泡排序的耗时比较(单位: ms)

插入排序示意

以此类推