目录
嗨嗨^_^，米娜桑，今天我们继续学习排序算法中的插入排序，激不激动，兴不兴奋呢！好了废话不多说，下面请看正文！
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增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以上就是今天的全部内容了，我们下一期再见！
分享一张壁纸： 