排序（一）——冒泡排序、直接插入排序、希尔排序（BubbleSOrt,InsertSort,ShellSort)

欢迎来到繁星的CSDN，本期的内容主要包括冒泡排序(BubbleSort），直接插入排序(InsertSort)，以及插入排序进阶版希尔排序（ShellSort）。

废话不多说，直接上正题！

一、冒泡排序

冒泡排序是我们的老朋友了，我们最初模拟实现qsort的时候就是用它来模拟的（尽管qsort的底层原理实际是quicksort，即快排）。

上代码！

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		// 单趟
		int flag = 0;
		for (int i = 1; i < n - j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				flag = 1;
			}
		}

		if (flag == 0)
		{
			break;
		}
	}
}

代码相当简单，其思想就是通过两两之间的比较，每一趟都将最大的数据放在数组的最后。

缺点是，冒泡排序的速度相当慢，原因不仅仅在于比较的次数恒定（n*(n+1)/2次)，更在于如果数据量庞大，各个数据移动的速度也相当慢。

实际意义聊胜于无，但却很好地帮我们入门各大排序算法，这是它仍然活跃的意义。

二、直接插入排序

我们一般会叫它插入排序，在此加入“直接”二字，是为了区分它和希尔排序。

插入排序的思路也是较为简单的。

面对一个有n个元素的数组，如果前n-1个元素都有序，那么第n个元素通过和前面所有元素比较，就能得到该元素在数组中的位置。有一点数学归纳法的思想在里面。

上代码！

void InsertSort(int* a, int n)
{
	//  [0, n-1]
	for (int i = 0; i < n - 1; i++)
	{
		// [0, n-2]是最后一组
		// [0,end]有序 end+1位置的值插入[0,end]，保持有序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

由于一个元素一定有序，所以第一个元素不用排序。而从第二个元素开始，通过比较，不断插入到前面的数组中，使前n项都有序，如此往复，便可使得整个数组有序。

相比于冒泡排序，插入排序少了大量重复的交换数值的工作，而是一步到位，得到数据的最终位置（尽管时常需要将所有数据后移，但代码中只是赋值，而非交换，效率比冒泡高的多）。

两者运行时间差别：

（此处数据为10000个）

尽管如此，我们在实际工作中也很少使用直接插入排序，即使时间比冒泡排序少的多，其时间复杂度仍为O(n^2)。但不得不指出，它仍有应用，后续在快排的时候将会提到。

三、希尔排序

希尔排序是插入排序的优化版本，优化到可以和快速排序一较高下。

希尔排序主要做两件事：1、预排序。2、插入排序。

由插入排序的代码可知，当数组越趋近于有序，比较和赋值的次数也越来越少。所以预排序的目的就是使得整个数组接近有序。

上代码！

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		// +1保证最后一个gap一定是1
		// gap > 1时是预排序
		// gap == 1时是插入排序
		gap = gap / 3 + 1;

		for (size_t i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

要点解释：

1、gap代表的含义是，下标相减为gap的元素为一组，进行插入排序。此举的意义是使得O（n^2)的复杂度造成的影响尽可能小，因为a*(n/a)^2小于n^2，a为任意整数。

2、而当gap等于1时再进行排序，就是插入排序了。

3、gap的大小实际上由写代码的人自己决定，没有一定gap越大，或者gap越小的效果最好，但可以确定的是，经过预排序的插排会比直接插排要更快。

4、上述代码中的gap是一个效果较好的gap，可以参照并直接使用。