排序算法-----插入排序

前言：

    嗨嗨^_^，米娜桑，今天我们继续学习排序算法中的插入排序，激不激动，兴不兴奋呢！好了废话不多说，下面请看正文！

插入排序

     插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

原理图

初始数组如下所示：

第一次，拿到第一个数字，因为第一个数字不存在顺序，无法进行比较，所以不需要进行相关的操作** 第二次**，拿到第二个数字 1 ，与前面的数字进行比较，发现6比1大，那么就进行数字交换，如下图所示：

第三次，拿到数字9，发现9，比前面的两个数字都要大，那么就保持位置不变，继续往后看。

第四次，拿到数字2，此时发现，2比9小，比6小，比1大，那么就把2插入到1和6之间，6和9依次向后移动一位。

第五次，拿到数字4，此时把数字4插入到2和6之间，同样的6和9依次往后移动一位。

第六次，拿到数字8，此时8比9小，那么就插入到9的前面即可，9向后移动一位

第七次，拿到12，发现12比前面已排序好了的数字都要大，那么位置不变。

** 第八次**，拿到10，此时10比12小，比9大，那么就插入到9和12之间，12向后移动一位。

看，这样就完成了排序了！

动态图展示

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

//直接插入
void insert_sort(int* n, int length) {
    for (int i = 0; i < length; i++) {
        int temp = n[i];
        for (int j = i - 1; j >= 0; j--) {
            if (n[j] > temp) {
                n[j + 1] = n[j];
                n[j] = temp;
            }
        }
    }
 }
int main() {
    int array[10];
    srand((unsigned)time(0));
    for (int i = 0; i < 10; i++) {
        array[i] = rand() % 20;
    }
    for (int i = 0; i < sizeof(array) / sizeof(int); i++) {
        printf("%d ", array[i]);
    }
    printf("\n排序后：");
    insert_sort(array, sizeof(array) / sizeof(int));
    for (int i = 0; i < sizeof(array) / sizeof(int); i++) {
        printf("%d ", array[i]);
    }
}
//输出结果：
//9 16 13 4 8 12 2 0 7 2
//排序后：0 2 2 4 7 8 9 12 13 16

分析总结

时间复杂度

最好情况就是全部有序，此时只需遍历一次，最好的时间复杂度为O ( n )；如果完全逆序的话，那么时间复杂度就会变为O(n^2),直接翻倍。所以时间复杂度为O(n^2) 。

空间复杂度

这里没有去开辟空间，空间是一个常量，所以空间复杂度是O（n）.

稳定性

遇到相同大小元素过程中，依然是插入到相同元素的前边，相对位置没有发生改变，所以稳定性好。

二分法插入排序

二分法插入排序是对插入排序的代码优化，整体的实质上还是插入排序，时间复杂度依然是不会改变的O（n^2）,当n较大时,总排序码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差。同样的，二分法插入排序是稳定的。

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
//二分法插入排序
void insert_bin_sort(int *n,int length) {
    int left, right, mid;
    for (int i = 1; i < length; i++) {
        left = 0;
        right = i - 1;
        while (left <= right) {
            mid = (left + right) / 2;
            if (n[mid] > n[i]) {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
            
        }
        int temp = n[i];
        for (int j = i; j > left; j--) {
            n[j] = n[j - 1];
        }
        n[left] = temp;
    }
}
int main() {
    int array[10];
    srand((unsigned)time(0));
    for (int i = 0; i < 10; i++) {
        array[i] = rand() % 20;
    }
    for (int i = 0; i < sizeof(array) / sizeof(int); i++) {
        printf("%d ", array[i]);
    }
    printf("\n排序后：");
    insert_bin_sort(array, sizeof(array) / sizeof(int));
    for (int i = 0; i < sizeof(array) / sizeof(int); i++) {
        printf("%d ", array[i]);
    }
}
//输出结果：
//15 0 15 3 5 7 9 6 12 14
//排序后：0 3 5 6 7 9 12 14 15 15

以上就是今天的全部内容了，我们下一期再见！

分享一张壁纸：