数据结构：直接插入排序与希尔排序详解_希尔排序与直接插入排序的比较次数

前言

作者本篇文章主要讲的是希尔排序，因为希尔排序在排序里面算是非常难理解的一个排序。那可能有人会问了那我们主要讲希尔排序。为什么还要讲一个直接插入排序呢？要想掌握希尔排序，就必须先理解直接插入排序，因为希尔排序就是在直接插入排序上做的优化。

插入排序

直接插入排序

基本思想

直接插入排序时一种简单的插入排序法，其基本思想是：插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

直接插入排序其实在我们打扑克牌的时候就会用到，比如说我们打扑克牌的时候我们手上已经有了几张牌，此时如果我们再抓一张牌，我们一般是不是会将刚抓上来的这张牌与前面手上有的牌进行比较然后插入到相应的位置。

以下就是我们直接插入排序的单趟排序时会碰到的三种情况了：

第一种：

第二种：

第三种：

看完了直接插入排序单趟排序会碰到的情况之后，我们来实现一下直接插入排序的单趟排序吧

同时我建议大家在写排序的时候先写单趟排序，单趟排序理清楚了再去写整个排序

void InsertSort(int* a, int n)
{
    //直接插入排序的单趟排序
		int end = 0;
		int x = a[end + 1];
		while (end >= 0)
		{
			//如果a[end}大于要插入的x，那么将a[end]的值往后移，并且end--
			if (a[end] > x)
			{
				a[end + 1] = a[end];
				end--;
			}
			//a[end]可能比插入的值要小，我们需要将插入的值插入到a[end]的后面一个位置上，
			//或者说插入的值比数组中的任何数都要小，我们需要将x插入到数组的第一个位置
			//这两种情况我们直接break，放到外面处理就可以了
			else
			{
				break;
			}
		}
		a[end + 1] = x;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

理解了上面的单趟排序之后我们再来实现一下直接插入排序

直接插入排序的实现

//直接插入排序
//时间复杂度：最坏O(N^2)  最好O(N^2)
//空间复杂度：O(1)
//稳定性：稳定
void InsertSort(int* a, int n)
{
	//这里i<n-1,因为x是等于a[end+1]，如果i能取到n-1，那么a[end+1]就会越界，因此i<n-1
	for (int i = 0; i < n - 1; i++)
	{
		//直接插入排序的单趟排序
        //将x插入[0,end]有序区间
		int end = i;
		int x = a[end + 1];
		while (end >= 0)
		{
			//如果a[end}大于要插入的x，那么将a[end]的值往后移，并且end--
			if (a[end] > x)
			{
				a[end + 1] = a[end];
				end--;
			}
			//a[end]可能比插入的值要小，我们需要将插入的值插入到a[end]的后面一个位置上，
			//或者说插入的值比数组中的任何数都要小，我们需要将x插入到数组的第一个位置
			//这两种情况我们直接break，放到外面处理就可以了
			else
			{
				break;
			}
		}
		a[end + 1] = x;
	}
	
}
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

直接插入排序的验证

void TestInsertSort()
{
	int a[] = { 6, 2, 3, 1, 7, 5, 9, 4, 8, 10 };

	PrintArray(a, sizeof(a) / sizeof(int));

	InsertSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));

}

int main()
{
	TestInsertSort();
	printf("\n");

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

小结

直接插入排序对于接近有序的数组它会排得比较快，但是对于逆序的数组它就会排得很慢。

希尔排序

基本思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序数组中所有元素分成gap组，所有距离为gap的元素分在同一组内，并对每一组内的元素进行排序。然后，重复上面分组和排序的工作。当gap=1时，所有元素在统一组内排好序

希尔排序的预排序

在讲预排序之前我们先来看一张图片

我们可以从上面图中观察到一个现象：

gap越大，预排序越快，但是预排序后越不接近有序

gap越小，预排序越慢，但是预排序后越接近有序

下面我们就来讲一讲预排序吧

敲重点：我们学预排序的时候一定要与直接插入排序对比着来学，这样学起来便于我们理解。

我们先来看看一组中的一次预排序

            int gap = 3;
            //单组中的一次预排序
            int end = 0;
			int x = a[end + gap];
			while (end >= 0)
			{
	            //如果a[end]>x,那么将end的值往后挪gap个位，并且将end-=gap
				if (a[end] > x)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
	//a[end]可能比插入的值要小，我们需要将插入的值插入到a[end]的后面一个位置上，
	//或者说插入的值比数组中的任何数都要小，我们需要将x插入到数组的第一个位置
	//这两种情况我们直接break，放到外面处理就可以了
				else
				{
					break;
				}
			}
			a[end + gap] = x;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

上面我们了解了一组中的一次预排序之后，我们解下来再来看看一组的预排序

我们了解了一组预排序的过程后，我们再来实现一下一组预排序的代码

        int gap = 3;
		//单组排序
	//这里i<n-gap,因为x是等于a[end+gap]，如果i能取到n-gap，那么a[end+gap]就会越界，因此i<n-gap
		for (int i = j; i < n - gap; i += gap)
		{
			//单组中的一次排序
			int end = i;
			int x = a[end + gap];
			while (end >= 0)
			{
	            //如果a[end]>x,那么将end的值往后挪gap个位，并且将end-=gap
				if (a[end] > x)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
	//a[end]可能比插入的值要小，我们需要将插入的值插入到a[end]的后面一个位置上，
	//或者说插入的值比数组中的任何数都要小，我们需要将x插入到数组的第一个位置
	//这两种情况我们直接break，放到外面处理就可以了
				else
				{
					break;
				}
			}
			a[end + gap] = x;
		}
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

解下来我们再来看看gap组预排序后是什么样子(这里作者只写了最终gap组后预排序后的结果，没有写过程)

gap组预排序之后与我们刚开始的数据对比一下，相比而言预排序之后还是更接近于有序了。

下面我们有两种实现gap预排序的方法

第一种相比于第二种更好理解，但是看个人的喜好了。

第一种：

    //gap组的预排序
	for (int j = 0; j < 3; j++)
	{
		int gap = 3;
		//单组排序
	//这里i<n-gap,因为x是等于a[end+gap]，如果i能取到n-gap，那么a[end+gap]就会越界，因此i<n-gap
		for (int i = j; i < n - gap; i += gap)
		{
			//单组中的一次排序
			int end = i;
			int x = a[end + gap];
			while (end >= 0)
			{
	            //如果a[end]>x,那么将end的值往后挪gap个位，并且将end-=gap
				if (a[end] > x)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
	//a[end]可能比插入的值要小，我们需要将插入的值插入到a[end]的后面一个位置上，
	//或者说插入的值比数组中的任何数都要小，我们需要将x插入到数组的第一个位置
	//这两种情况我们直接break，放到外面处理就可以了
				else
				{
					break;
				}
			}
			a[end + gap] = x;
		}
	}
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

第二种：

        //一锅炖，多组并排
		//这里i<n-gap,因为x是等于a[end+gap]，如果i能取到n-gap，那么a[end+gap]就会越界，因此i<n-gap
		for (int i = 0; i < n - gap; i++)
		{
			//单组中的一次排序
			int end = i;
			int x = a[end + gap];
			while (end >= 0)
			{
				//如果a[end]>x,那么将end的值往后挪gap个位，并且将end-=gap
				if (a[end] > x)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				//a[end]可能比插入的值要小，我们需要将插入的值插入到a[end]的后面一个位置上，
				//或者说插入的值比数组中的任何数都要小，我们需要将x插入到数组的第一个位置
				//这两种情况我们直接break，放到外面处理就可以了
				else
				{
					break;
				}
			}
			a[end + gap] = x;
		}
	}
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

上面学会了gap组的预排序之后，距离我们学会希尔排序就已经成功一大半了。

希尔排序的实现

当通过上面多次的预排序后，我们的数组只是接近与有序，并不是有序，那么我们应该怎么做才能使得它变成有序呢？

希尔排序的本质其实就是：多次预排序(gap>1)+直接插入排序(gap==1)

因此我们只要保证把最后把gap==1之后再进行一次排序，就达到了我们最后想要的效果了。

我们可以先令gap=n(也就是我们数组的长度)，每预排序一次就将gap/=2,最后gap会变成1，

同样的我们也可以将gap/=3,但是必须在后面加上一个1，不然的话gap/=3最后有可能不是1。

//时间复杂度：最坏O(N^2) 最好0(N*logN)
//空间复杂度：O(1)
//稳定性：不稳定
void ShellSort(int* a,int n)
{
	int gap = n;
	//多组预排序(gap>1)+直接插入排序(gap==1)
	while (gap > 1)
	{
		//这里gap可以除以2，到最后会gap会变成1，就是我们的直接插入排序
		//这里gap也可以除以3，但必须在后面加上一个1，不然的话gap到最后可能不是1
		gap /= 2;
		gap = gap / 3 + 1;
		//一锅炖
		//这里i<n-gap,因为x是等于a[end+gap]，如果i能取到n-gap，那么a[end+gap]就会越界，因此i<n-gap
		for (int i = 0; i < n - gap; i++)
		{
			//单组中的一次排序
			int end = i;
			int x = a[end + gap];
			while (end >= 0)
			{
				//如果a[end]>x,那么将end的值往后挪gap个位，并且将end-=gap
				if (a[end] > x)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				//a[end]可能比插入的值要小，我们需要将插入的值插入到a[end]的后面一个位置上，
				//或者说插入的值比数组中的任何数都要小，我们需要将x插入到数组的第一个位置
				//这两种情况我们直接break，放到外面处理就可以了
				else
				{
					break;
				}
			}
			a[end + gap] = x;
		}
	}
}
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

希尔排序的验证

void TestShellSort()
{
	int a[] = { 6, 2, 3, 1, 7, 10, 5, 4, 8, 9 };

	PrintArray(a, sizeof(a) / sizeof(int));

	ShellSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));

}

int main()
{
	TestShellSort();
	printf("\n");

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

小结

希尔排序使对直接插入排序的优化

当gap>1时都是预排序，目的是让数组更接近与有序。

gap越大，预排序越快，但是预排序后越不接近有序

gap越小，预排序越慢，但是预排序后越接近有序。

gap==1时，就是我们的直接插入排序

希尔排序的时间复杂度不好算，因为gap取值的方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定。