C语言8种基本排序算法之插入排序

103 阅读 0 评论 68 点赞

我是靠谱客的博主舒心期待，这篇文章主要介绍C语言8种基本排序算法之插入排序，现在分享给大家，希望可以做个参考。

小白一天学一个算法系列，从逻辑、关键、算法动画、完整示例代码四个方面进行学习。

（注：冒泡排序示例代码有更详细的注解，共用代码后续算法示例代码中不再注释。）

逻辑：待插入数和有序数列的数依次比较，符合条件时有序数后移，插入值填写到空出的位置。外层控制插入值进入，内层控制有序数后移。

关键：内外层结合的关键点是j=i-1，j--，从待插入值的相邻位开始向前依次比较大小。

动画：

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10

//插入排序
void sort_insert(int *arr)
{
	int i,j,InsertVal;
	//开始时，最前面的两个数比较
	for (i = 1; i < N; i++)	//外层控制要插入的值进入
	{
		InsertVal=arr[i];	//保存待插入值，循环比较
		for(j=i-1;j>=0&&arr[j]>InsertVal;j--)	//内层控制已插入的值后移
		{
			arr[j+1]=arr[j];	//先判断后执行，注意j=j-1是在执行之后的
		}
		arr[j+1]=InsertVal;		//循环结束后即确定了要插入的位置，填入插入值
	}
}

//打印数组
void sort_inser_print(int *arr)
{
	int i;
	for (i = 0; i < N; i++)
	{
		//putchar(arr[i]);
		printf("%3d",arr[i]);
	}
	printf("n");
}

int main()
{
	
	//int res_rand;
	int i;
	int a[N];
	srand((unsigned int)time(NULL));	//srand播种
	//res_rand=rand()%100;	//rand生成

	printf("随机数生成：");
	for (i = 0; i < N; i++)
	{
		a[i]=rand()%100;
	}
	sort_inser_print(a);

	//调用插入排序
	sort_insert(a);
	printf("插入排序结果：");
	sort_inser_print(a);
	system("pause");
	return 0;
}