[数据结构与算法]十大排序——插入排序

插入排序：遍历数组，在遍历的过程中将第i个元素与第i+1个元素进行比较，若array[i]>array[i+i]则第i个元素与第i-2个元素比较，直到找到小于第i个元素的元素，将第i个元素插入到其后方。以此类推。

	最小时间复杂度	最大时间复杂度	平均时间复杂度	空间复杂度	稳定性
选择排序	O(n)	O()	O()	O(1)	不稳定

动图解析：

?C语言实现：

#include<cstdio>
#include<cstdlib>
#define Status int

int a[10] = { 8,0,4,5,3,2,6,7,9,1 };
int length = sizeof(a) / sizeof(a[0] - 1);
int i,e, j, b,temp;

Status Insertion_Sort(){
	for(i = 1; i < length; i++){
		j = i - 1;
		temp = a[i];
		while (j >= 0 && a[j] > temp) {
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = temp;
		}
	for (int i = 0; i < length; i++) {
		printf("%d", a[i]);
	}
	return 0;
}
int main() {
	printf("该数组为：");
	for (int i = 0; i < length; i++) {
		printf("%d", a[i]);
	}
	printf("\n");
	printf("排序后的数组为：");
	Insertion_Sort();
}

p.s.在使用Visual Studio编译器的时候输入scanf()方法要用scanf_s()

更多内容请移步公众号 手撕算法。谢谢

算法爱好者协会群：940100543，加入学习讨论。

所使用编译器为：Visual Studio2019 链接：https://pan.baidu.com/s/1eg8CNrqrP1jn7GRzHfYXxA
??????????????????????????????????????????????????????????????????? 提取码：1234

推荐新手使用dev cpp??????????????????????? 链接：https://pan.baidu.com/s?????? /1XZp_8lVE7X6tMLmvXRbYhw
???????????????????????????????????????????????????????????????????? 提取码：1234

?