排序之直接插入排序和折半插入排序

84 阅读 0 评论 56 点赞

我是靠谱客的博主自由高山，最近开发中收集的这篇文章主要介绍排序之直接插入排序和折半插入排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

直接插入排序

直接插入排序时将一个记录插入到一个已经有序的的表或者数组中，从而得到一个新的有序的表或者数组。
就像打牌一样，拿到一张牌后，要往手中的牌里插，使手中的牌还是有序的。假如手中有4,6,7三张牌，现在拿到的下一张牌是5，那么肯定要插在4之后，直接插入排序也是这个道理。
假如现在有数组：{11,2,5,78,34,56,23}，直接插入排序的过程如下：

代码实现如下：

void InsertSort(int a[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {
        temp = a[i];    // 待插关键字为a[i]
        for (j = i - 1; a[j] > temp && j >= 0; j--) {   // 查找a[i]的位置
            a[j + 1] = a[j];
        }
        a[j + 1] = temp;
    }
}

分析发现上图中当待插关键字为78时，78比前面的一个大，就没有必要进行这一趟排序，所以可以在进行每一趟排序之前，判断是否需要进行。
代码实现如下：

void InsertSort(int a[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) { // 如果需要进行排序，也就是说a[i]比它的前一个小，a[i]和前面的不能构成一个有序序列
            temp = a[i];
            for (j = i - 1; a[j] > temp && j >= 0; j--) { 
                a[j + 1] = a[j];
            }
            a[j + 1] = temp;
        }
    }
}

直接插入排序的时间复杂度

直接插入排序的最好的情况是原本需要排序的数组就是有序的，那么它只需要比较即可，但是如果是最坏情况，即数组是反序的，那么他的时间复杂度就会比较大，所以最后他的平均时间复杂度为 $O(n^2)$ 。直接插入排序是简单排序中时间复杂度比较稳定的排序算法。

直接插入排序时一种稳定的排序。

折半插入排序

我们知道对于数组折半查找要比顺序查找快，通过这个点可以对直接插入排序进行优化。之前在找待插关键字位置的时候使用的是顺序查找比较，现在将之前的顺序查找改为折半查找。

void BiInsertSort(int a[], int n) {
    int i, j, temp;
    int low, high, mid;
    for (i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            temp = a[i];    // a[i]是待插关键字
            low = 0;
            high = i - 1;   // 从0到i是一段有序序列，在这段序列中找一个合适的位置插入a[i]
            while (low < high) {
                mid = (low + high) / 2;
                if (a[mid] > temp)  // a[i]在mid之前
                    high = mid - 1;
                else
                    low = mid + 1;  // a[i]在mid之后
            }
            for (j = i - 1; j >= low; j--) 
                a[j + 1] = a[j];        // 记录后移
            a[low] = temp;
        }  
    }
}