插入排序和希尔排序（C语言）_c语言:举例说明“插入排序”和“希尔排序”的稳定性与否。

插入排序和希尔排序（C语言）

• 插入排序
• 希尔排序

阅读之前注意：

本文阅读建议用时：20min
本文阅读结构如下表：

插入排序

插入排序的关键在于：

1. 当前元素（比如第1个元素是当前元素）前面的序列（比如第0个元素构成的序列）都是有序的，再把当前元素（第1个元素）插入到这个有序序列（第0个元素构成的序列）中，于是形成多了一个元素的有序序列（即第0个、第1个元素构成的有序序列）
2. 再把这个有序序列后的元素（比如第2个元素）看成当前元素，重复步骤1，直至有序序列后没有元素，即完成了整个序列的排序
   参考以下代码：

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

void insertSort(int *a,int n)//插入排序
{
	int i = 0;
	int j = 0;
	int tmp = 0;
	int time = 0;
	for (i = 1; i < n; i++)
	{
		tmp = a[i];
		for (j = i ; (j > 0 && tmp<a[j-1]); j--)
		{
			a[j] = a[j - 1];//a[j-1]元素后移
			time++;
		}
		a[j] = tmp;
	}
	printf("move times:%d\n", time);
}

void main()
{
	int a[10] = { 1, 5, 9, 7, 2, 3, 6, 8, 4, 0 };
	insertSort(a, 10);
	for (int i = 0; i < 10; i++)
		printf("%d ", a[i]);
	system("pause");
}
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

在代码的insertSort()函数体中，我加入了一个time的变量来计数元素移动的次数。

希尔排序

希尔排序相对于插入排序而言，加入了数据分组的思想。这样就使得相距较远的元素也能很快的交换到对应的位置，而不必像插入排序一样一个一个的往前交换，从而减少了交换的次数。
参考以下代码：

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

void shellSort(int *a,int size)//希尔排序
{
	int gap = size;
	int i = 0;
	int j = 0;
	int tmp = 0;
	int time = 0;
	do
	{
		gap = gap / 3 + 1;
		for (i = gap; i < size; i++)//这里即基础的插入排序
		{
			tmp = a[i];
			for (j = i; (j > 0) && (tmp < a[j - gap]); j -= gap)
			{
				a[j] = a[j - gap];
				time++;
			}
			a[j] = tmp;
		}
	} while (gap > 1);
	printf("move times:%d\n", time);
}

void main()
{
	int a[10] = { 1, 5, 9, 7, 2, 3, 6, 8, 4, 0 };
	shellSort(a, 10);
	for (int i = 0; i < 10; i++)
		printf("%d ", a[i]); 
	system("pause");
}
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

运行以上程序，可以看到希尔排序交换的次数更少，或者说其时间复杂度降下来了。¹

如果本文对你有帮助，不如请我一罐可乐吧