插入排序:直接插入排序(Straight Insertion Sort)

基本思想:

将一个记录插入到已排序好的有序表中,从而得到一个新的记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。

待排序记录 R1,R2,… ,Rn–1, Rn
第一步:R1
第二步:(R1 ), R2
第三步:(R1 , R2), R3
……
第 j 步:(R1,R2,… ,Rj–1), Rj
……
第 n 步: (R1,R2,… ,Rn–1), Rn.

要点:设立哨兵,作为临时存储和判断数组边界之用。

算法的实现:

// 输出数组内容
void print(int array[], int length, int i) {
    printf("i=%d:",i);
    for (int j = 0; j < length; j++) {
        printf(" %d ", array[j]);
    }
    printf("\n");
}

// 直接插入排序(Straight Insertion Sort)
void InsertSort(int array[], int length) {
    for (int i = 1; i < length; i++) {
        if (array[i] < array[i-1]) { // 若第i个元素大于i-1元素,直接插入;小于的话,移动有序表后插入
            int j = i - 1;
            int sentry = array[i]; // 复制为哨兵,即存储待排序元素
            array[i] = array[i-1]; // 首先后移一个元素
            while (j >= 0 && sentry < array[j]) { // 查找在有序表的插入位置
                array[j+1] = array[j];
                j--; // 元素后移
            }
            array[j+1] = sentry; // 插入到正确位置
        }
        print(array, length, i); // 打印每趟排序的结果
    }
}

int main(int argc, const char * argv[]) {
    int arrayInsertSort[8] = { 49, 38, 65, 97, 76, 13, 27, 49 };
    InsertSort(arrayInsertSort, 8);
    printf("\n");
    
    return 0;
}

精简代码:

将 array[j] 插入到前面a[0…j-1]的有序区间所用的方法进行改写,用数据交换代替数据后移。如果 array[j] 前一个数据 array[j-1] > array[j],就交换 array[j] 和 array[j-1],再 j-- 直到 array[j-1] <= array[j]。这样也可以实现将一个新数据并入到有序区间。

// 直接插入排序(Straight Insertion Sort)
void InsertSort(int array[], int length) {
    for (int i = 1; i < length; i++) {
        for (int j = i - 1; j >= 0 && array[j] > array[j+1] ; j --) {
            int temp = array[j+1];
            array[j+1] = array[j];
            array[j] = temp;
        }
        print(array, length, i); // 打印每趟排序的结果
    }
}

总结

时间复杂度:O(n^2)。其他的插入排序有二分插入排序,2-路插入排序。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容