菜鸡大学生的数据结构——排序篇

注意：以下未标注的图片都是纯手工绘制，开放一切权限，希望能够帮到你。 同样是注意：将我的图片说成是你自己画的的行为是不可以的。 祝你愉快~

啥是排序呢？

给你一串数据，我们可以按照一些条件将数据按照递增或者递减的方式进行排列，比如计算机里面的文件：

排序在生活中还是很有用的，比如我们可以通过首字母很快找到通讯录的联系人，找到最大值和最小值，精确找到某一天的消息… 总之，有用，好好学。

排序可以分为内部排序和外部排序。

内部排序： 数据元素全部放在内存中的排序。 外部排序： 数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

我们今天讲的所有排序都属于内部排序。

常见的排序算法及算法实现

1. 直接插入排序

我们假设书架上有一摞整齐的书：

如何把绿色书放入书架，使这书依旧整齐？ 菜鸡大学生说：这简单，从右往左，找到刚好比这本书高的书，放在它右边就行了。

恭喜你，你已经完全掌握插入排序了，它的基本思想就是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止。

由于我们不知道数组前几个元素是有序的，所有我们从数组第二个元素开始执行插入排序，直到数组最后一个元素。

动图演示：

代码：

//插入排序
void InsertSort(int* a, int n)
{
          
   
	for (int i = 0; i < n - 1; i++)
	{
          
   
		int end = i;
		int tmp = a[i + 1];
		while (end >= 0)
		{
          
   
			if (a[end] > tmp)
			{
          
   
				a[end + 1] = a[end];
				end--;
			}
			else
			{
          
   
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

复杂度及稳定性分析

当数据有序的时候，时间复杂度为O（n），但显然不可能次次都这么巧。 平均下来还是O(N^2)。

稳定性： 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

从后往前插入数据又没啥波动，稳定的。

直接插入排序的特性总结： 元素集合越接近有序，直接插入排序算法的时间效率越高。 时间复杂度：O(N^2)。 空间复杂度：O(1)，它是一种稳定的排序算法。 稳定性：稳定。

2.希尔排序

又称缩小增量法。

显然，直接插入效率不是特别高。 根据插入排序的总结：元素集合越接近有序，直接插入排序算法的时间效率越高。 我们是不是可以想想办法让数据变得有序一点点呢？

1959年，有一个大佬Donald Shell提出了希尔排序。

先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。 然后将gap逐渐减小重复上述分组和排序的工作。 当gap=1时，就排好了。

通过图片我们发现，不断的预排序使得数据逐渐变成了小的在前，大的在后的状态。 这样在进行插入排序效率会直线上升。

那我们如何写代码呢？ 我们当然可以排完一组，再去排第二组，第三组。 以gap=2为例：

for (int j = 0; j < gap; ++j)
{
          
   
	for (int i = j; i < n - gap; i += gap)
	{
          
   
		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;
	}
}

然后再套一层循环去控制gap。

但我们完完全全可以将它们合并起来，就可以少一次循环了。

gap如何变化可以随意去设置，但是注意最后一次一定要是1。

//希尔排序
void ShellSort(int* a, int n)
{
          
   
	int gap = n;
	while (gap > 1)
	{
          
   
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
          
   
			int end = i;
			int tmp = a[i + gap];
			while (end >= 0)
			{
          
   
				if (a[end] > tmp)
				{
          
   
					a[end + gap] = a[end];
					end-=gap;
				}
				else
				{
          
   
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

复杂度及稳定性分析

希尔排序的特性总结： 希尔排序是对直接插入排序的优化。 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，排序起来就比较快（可以看动图）。 希尔排序的时间复杂度不好计算，因为gap的取值方法有很多。 在Knuth《计算机程序设计技巧》一书中，Knuth进行了大量的试验统计，计算出时间复杂度大概在O(N^1.25)到O(1.6N^1.5)之间。 空间复杂度O(1)。 稳定性：不稳定。

3.选择排序

每次学到排序的时候菜鸡大学生总会乳冒泡，但其实选择排序也拉。 冒泡：为什么只有我被乳？ 可能是因为冒泡一般是第一个学的排序吧（小声）。

继续说回选择排序。 基本思想：

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置， 然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置， 重复这样的步骤直到全部待排序的数据元素排完 。

优化方案：同时选最大值和最小值，然后将最大值与末尾交换，最小值与开头交换。

注意特殊情况： 此时由于max在begin位置，当min和begin互换时，max的位置其实是min，但是程序只会交换begin和end。 解决方案： 交换一次后判断max是不是begin，是的话max的值就是min。

同理，反过来也成立。 我们代码写的是相反版本：

//选择排序
void SelectSort(int* a, int n)
{
          
   
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
          
   
		int maxi = begin;
		int mini = begin;

		//寻找最大下标和最小下标
		for (int i = begin; i <= end; i++)
		{
          
   
			if (a[maxi] < a[i])
			{
          
   
				maxi = i;
			}

			if (a[mini] > a[i])
			{
          
   
				mini = i;
			}
		}

		//交换
		Swap(&a[maxi], &a[end]);

		//如果最小值在end位置
		if (mini == end)
		{
          
   
			mini = maxi;
		}
		Swap(&a[mini], &a[begin]);

		begin++;
		end--;
	}
}

复杂度及稳定性分析

直接选择排序的特性总结： 直接选择排序由于效率不高（可能还不如冒泡），所以日常使用的范围有限。 时间复杂度：O(N^2) 空间复杂度：O(1) 稳定性：不稳定 有一种特殊情况，我们假设一串数据2，2，1，3. 一轮下来第一个2会和1交换，然后两个2的顺序就乱了。

4.堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。 它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

如果是建小堆的话第一个就已经是最小的了，后面的数据还需要重新建堆，那么堆排序的意义就不存在了。

思路：

假设要排的数据有n个。 建大堆找到最大的数据和最后一个数据交换。 堆顶数据向下调整，此时新的堆顶数据是n-1个数据里面最大的数。 堆顶和第n-1个数据交换。 直到只剩一个数据。

我们先不急着建堆，先把后面的代码写出来。

for (size_t i = n - 1; i > 0; i--)
	{
          
   
		Swap(&a[0], &a[i]);
		AdjustDown(a, i, 0);
	}

注：建堆所需要的向下调整函数在二叉树的顺序结构里面有分析，可以去我之前的博客。 又注：这一段基本上都是拷贝的那一篇博客的内容。 又又注：这篇发出来的时候那一篇博客应该还没来的及发，应该下周就能出了。

顺便画个不太好理解的图。

然后在尝试建堆康康。 我们可以采取向上建堆和向下建堆两种建堆方式。 向上建堆就类似于一个个向数组里面插入数据。 向下建堆从倒数第一个非叶子节点开始向下调整。

//建大堆
	// 向上建堆
	for (int i = 0; i < n; i++)
	{
          
   
		AdjustUp(a, i);
	}

	//向下建堆
	for (int i = (n-1-1)/2; i >= 0; i--)
	{
          
   
		AdjustDown(a, n, i);
	}

既然有两种建堆方式我们就要比较一下效率了。 我们假设是满二叉树： 显然向下建堆效率更高。

将代码整合一下：

void AdjustDown(HPDataType* a, size_t size, size_t root)
{
          
   
	size_t parent = root;
	size_t child = root*2+1;

	while (child < size)
	{
          
   
		// 1、选出左右孩子中大的那个
		if (child + 1 < size && a[child] < a[child + 1])
			++child;

		// 2、如果孩子大于父亲，则交换，并继续往下调整
		if (a[child] > a[parent])
		{
          
   
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
          
   
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
          
   
	//向下建堆
	for (int i = (n-1-1)/2; i >= 0; i--)
	{
          
   
		AdjustDown(a, n, i);
	}

	for (size_t i = n - 1; i > 0; i--)
	{
          
   
		Swap(&a[0], &a[i]);
		AdjustDown(a, i, 0);
	}
}

复杂度及稳定性分析

堆排序的特性总结： 时间复杂度：O(N*logN) 空间复杂度：O(1) 稳定性：不稳定

5. 冒泡排序

冒泡一到店，所有排序的算法便都看着他笑，有的叫道，“冒泡，你又被人嫌弃了”他不回答，对菜鸡大学生说，“温两个循环，要一碟变量。”便排出九行代码。 他们又故意的高声嚷道， “你一定又占了人家的时间了！”冒泡睁大眼睛说，“你怎么这样凭空污人清白……” “什么清白？我前天亲眼见你拖慢了菜鸡大学生的程序，吊着打。”冒泡便涨红了脸，额上的青筋条条绽出，争辩道，“低效不能算拖……低效！……十几秒的事，能算拖么？” 接连便是难懂的话，什么“有序效率爆高“，什么“稳定”之类，引得众人都哄笑起来：店内外充满了快活的空气。

思想： 两两比较，大的就向后移动，直到最大的数据到达末尾。 执行n-1次即可。（n-1次的原因是最后一次两个数据只要交换一次就行，当然n也没啥问题。）

//冒泡排序
void BubbleSort(int* a, int n)
{
          
   
	for (int i = 0; i < n - 1 ; i++)
	{
          
   
		int exchange = 0;
		for (int j = 0; j < n - i - 1; j++)
		{
          
   
			if (a[j] > a[j + 1])
			{
          
   
				Swap(&a[j], &a[j + 1]);
				exchange = 1;
			}
		}

		if (exchange == 0)
			break;
	}
}

复杂度及稳定性分析

冒泡排序的特性总结： 时间复杂度：O(N^2) 空间复杂度：O(1) 稳定性：稳定

6. 快速排序

我们的好朋友，它来啦。 存在于库里的唯一大爹，它来啦。

那啥事快排呢？ 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 基本思想很简单，随便取一个基准值key，保证所有的元素，比key大的在一边，比key小的在另一边。然后左右序列重复这个过程直到有序。

菜鸡大学生嗅到了递归的味道！菜鸡大学生把持不住了！ 菜鸡大学生准备先写主干部分！

我们可以通过递归把数据分成左右两部分。 直到左边的数据等于右边的数据或者大于右边的数据。 （见图，按颜色分组）

注意，这里讲的主要是思想，图和PartSort代码没有关系，画的时候只追求了比key大的在一边，比key小的在另一边这个条件。 这张图主要是展示边界控制的问题。

//快速排序
void QuickSort(int* a, int left, int right)
{
          
   
	if (left >= right)
		return;

	int keyi = PartSort(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi+1, right);
}

下面就是考虑PartSort函数的问题。 茴字有四种写法，而快排如果算上非递归也有四种写法。 可以推断出：茴香豆就是快排。

Hoare版本

既然是hoare提出的，我们就得放在第一个，给创始人最大的排面。

思路： 选key，一般是第一个或者最后一个。 选定左指针和右指针从两头遍历数组。 如果是从第一个开始就右指针先走，最后一个开始就左指针先走。 * （画图解释）* 左指针遇到大于key的值就停下来，右指针遇到小于key的值就停下来。 交换左右指针的值。 直到相遇，交换key和左右指针位置的值。

注：这张静态图是指针移动和交换同时进行的。

为什么不能第一个开始左指针先走呢？ 第一个开始左指针走之前不会有什么问题，但是到了最后一步左指针会找到比key值大的数，然后停下和key交换。 而如果是右指针的话，它找到的是比key小的数，交换不会出现任何问题。 最后一个开始右指针先走同理。

铺垫了这么多我们来写代码吧。

//快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
          
   
	int keyi = left;
	while (left < right)
	{
          
   
		//右指针先走
		while (left < right && a[right] >= a[keyi])
		{
          
   
			right--;
		}
		//左指针再走
		while (left < right && a[left] <= a[keyi])
		{
          
   
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);

	return left;
}

挖坑法

挖坑法和上面的方法很像，但是相对便于理解。

思路： 选key，然后取出，留下一个坑。这里以左边第一个为key举例。 右边的指针遇到小于基准值的数时，直接将该值放入坑中，而右指针指向的位置形成新的坑位。 然后左指针遇到大于基准值的数时，将该值放入坑中，左指针指向的位置形成坑位。 重复过程直到两指针相遇，将key值放入坑中。

我们先看一下单次排序的动图：

顺着来就好，不像hoare版本需要考虑一些小小的细节。

好累啊不想画全趟了怎么办

代码：

//快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
          
   
	int key = a[left];
	int pit = left;

	while (left < right)
	{
          
   
		while (left < right && a[right] >= key)
		{
          
   
			right--;
		}
		a[pit] = a[right];
		pit = right;

		while (left < right && a[left] <= key)
		{
          
   
			left++;
		}
		a[pit] = a[left];
		pit = left;
	}

	a[pit] = key;
	return pit;
}

前后指针

很方便的写法，就是不太好理解。

思路:（以key为第一个数为例） 选定key，定义prev和cur指针. (cur = prev + 1) cur先走，遇到小于基准值的数停下，prev向后移动一个位置。 交换prev和cur的值。 重复上面的步骤，直到cur走出数组范围 最后将key值与prev对应位置交换。

我们先来看一下单趟动图： 这个方法的核心就是保证prev指向及prev之前的所有数据的值都小于key。

当cur还没遇见比key大的值的时候，prev是跟着cur一起移动的。 当cur第一次遇见比key大的值的时候，prev停下，此时prev包括prev前的数据都是小于key的。 当cur再一次遇见比key小的数据时，prev的下一个一定是比key大的数据，所以prev++和cur交换。 直到遍历结束。prev之前包括prev都比key小，key和prev交换。 key之前都比key小，key之后都比key大。

然后我们来考虑一下key取最右边： 为了保证prev包括prev前的数据都是小于key的。 prev就不能从0位置开始了，万一第一个数就大于key呢？

接下来的路与取左边完全一样，直到cur在key位置的时候： prev包括prev前的数据都是小于key的。（哇，这话我说了多少次）

在左边的时候prev前面有key，所以可以直接交换。 在右边的时候直接交换会把小的数换到右边，所以交换的时候是换prev++的位置。

好了，终于到代码了：

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
          
   
	//keyi=left
	int keyi = left;
	int cur = left + 1;
	int prev = left;
	while (cur <= right)
	{
          
   
		if (a[cur] < a[keyi] && a[++prev] != a[cur])
			Swap(&a[prev], &a[cur]);

		cur++;
	}
	Swap(&a[prev], &a[keyi]);

	return prev;
}

int PartSort3(int* a, int left, int right)
{
          
   
	//keyi=right
	int keyi = right;
	int cur = left;
	int prev = left-1;
	while (cur < right)
	{
          
   
		if (a[cur] < a[keyi] && a[++prev] != a[cur])
			Swap(&a[prev], &a[cur]);

		cur++;
	}
	Swap(&a[++prev], &a[keyi]);

	return prev;
}

快速排序优化

我们先讨论一下快速排序的两种情况：

最好： 所有的key刚好是中位数。时间复杂度O(NlogN). 最坏： 每一个key都是最小或最大值。时间复杂度O(N^2).

如果我们不幸用快排排了大量有序数据，程序很可能因为递归调用过多导致栈溢出。

所以我们可以进行如下优化：

1. 三数取中法选key。
2. 递归到小的子区间时，可以考虑使用插入排序。

完全优化过的代码：

int PartSort3(int* a, int left, int right)
{
          
   
	int midi = GetMidIndex(a, left, right);
	Swap(&a[midi], &a[left]);

	//keyi=left
	int keyi = left;
	int cur = left + 1;
	int prev = left;
	while (cur <= right)
	{
          
   
		if (a[cur] < a[keyi] && a[++prev] != a[cur])
			Swap(&a[prev], &a[cur]);

		cur++;
	}
	Swap(&a[prev], &a[keyi]);

	return prev;
}

int GetMidIndex(int* a, int left, int right)
{
          
   
	int mid = left + (right - left) / 2;
	
	if (a[left] < a[mid])
	{
          
   
		if (a[mid] < a[right])
		{
          
   
			return mid;
		}
		else if (a[left] > a[right])
		{
          
   
			return left;
		}
		else
		{
          
   
			return right;
		}
	}
	else 
	{
          
   
		if (a[mid] > a[right])
		{
          
   
			return mid;
		}
		else if (a[left] < a[right])
		{
          
   
			return left;
		}
		else
		{
          
   
			return right;
		}
	}
}

void QuickSort(int* a, int left, int right)
{
          
   
	if (left >= right)
		return;

	// 小区间直接插入排序控制有序
	if (right - left + 1  <= 30)
	{
          
   
		InsertSort(a + left, right - left + 1);
	}
	else
	{
          
   
		int keyi = PartSort3(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}

非递归写法

既然递归写法会导致栈溢出，那么我们只要把递归干掉就不会栈溢出了！

我们可以使用栈模拟递归的实现。 （用栈解决栈溢出的问题，这未尝不是一种…虽然不是一个东西就是啦）

思想： 将左右下标入栈。 如果栈不为空，两次取出栈顶元素，分别是左右下标。 三种单趟排序方法任选一种得到key的位置。 在以key为界限，若key左右区间中有元素，则将区间入栈。 重复上述步骤直到栈为空。

代码：

void QuickSortNonR(int* a, int left, int right)
{
          
   
	//创建栈
	ST st;
	StackInit(&st);

	//入栈
	StackPush(&st, left);
	StackPush(&st, right);

	while (!StackEmpty(&st))
	{
          
   
		//右后进，右先出
		right = StackTop(&st);
		StackPop(&st);

		left = StackTop(&st);
		StackPop(&st);

		//得到key
		int mid = PartSort3(a, left, right);

		if (right > mid + 1)
		{
          
   
			StackPush(&st, mid+1);
			StackPush(&st, right);
		}
		if (left < mid - 1)
		{
          
   
			StackPush(&st, left);
			StackPush(&st, mid - 1);
		}
	}
	StackDestory(&st);
}

复杂度及稳定性分析

快速排序的特性总结： 快速排序，好用，超好用。 时间复杂度：O(N*logN)。 空间复杂度：O(logN)。 稳定性：不稳定。

7.归并排序

经典分治。

思想： 将已有序的子序列合并，得到完全有序的序列。

这世上本来没有有序的序列，分多了，就有了。

递归写法

由于递归写法的思想在快排我们就讲过，所以就直接放代码。 我尽量使得注释详细一点。 注意：为了防止数据覆盖我们需要开一个新的数组。

//归并排序
void _MergeSort(int* a, int begin, int end, int* tmp)
{
          
   
   if (begin >= end)
   	return;

   int mid = (begin + end) / 2;
   _MergeSort(a, begin, mid, tmp);
   _MergeSort(a, mid + 1, end, tmp);

   //归并
   int begin1 = begin;
   int end1 = mid;
   int begin2 = mid + 1;
   int end2 = end;
   int i = begin;

   while (begin1 <= end1 && begin2 <= end2)//有一个序列为空就停止
   {
          
   
   	if (a[begin1] < a[begin2])
   	{
          
   
   		tmp[i++] = a[begin1++];
   	}
   	else
   	{
          
   
   		tmp[i++] = a[begin2++];
   	}
   }

   //将剩余数据放入tmp数组
   while (begin1 <= end1)
   {
          
   
   	tmp[i++] = a[begin1++];
   }
   while (begin2 <= end2)
   {
          
   
   	tmp[i++] = a[begin2++];
   }

   //将合并后的序列拷贝到原数组中
   memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n)
{
          
   
   int* tmp = (int*)malloc(sizeof(int) * n);
   assert(tmp);

   _MergeSort(a, 0, n - 1, tmp);

   free(tmp);
}

非递归写法

非递归实现的思想与递归实现的思想是类似的。

不同的是，我们是先1个元素一组，再2个元素一组，4个元素一组…直到将所有的元素归并完。

这样会产生一些边界问题，但是我们先不急着搞。 我们假设有八个数据。

void MergeSortNonR(int* a, int n)
{
          
   
	int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);
	int gap = 1;

	while (gap < n)
	{
          
   
		for (int k = 0; k < n; k += 2 * gap)
		{
          
   
			//归并
			int begin1 = k;
			int end1 = k + gap - 1;
			int begin2 = k + gap;
			int end2 = k + gap * 2 - 1;
			int i = begin1;

			while (begin1 <= end1 && begin2 <= end2)//有一个序列为空就停止
			{
          
   
				if (a[begin1] < a[begin2])
				{
          
   
					tmp[i++] = a[begin1++];
				}
				else
				{
          
   
					tmp[i++] = a[begin2++];
				}
			}

			//将剩余数据放入tmp数组
			while (begin1 <= end1)
			{
          
   
				tmp[i++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
          
   
				tmp[i++] = a[begin2++];
			}
		}
		//将合并后的序列拷贝到原数组中
		memcpy(a, tmp, n * sizeof(int));
		gap *= 2;
	}
	free(tmp);
}

这个代码只有在数据个数是2^n时候才可以运行，不然会导致越界。 我们现在把数据改成六个。

我们可以发现到了最后，四个边界寄了三个。 实在是令人啊！

所以我们要去手动控制边界。 一共有三种情况：

end1越界。 end1不越界，begin2越界。 end1，begin2不越界，end2越界。

解决方案：

修正end1为n-1. begin2越界表明第二段区间不存在，把begin2和end2变成一个不存在的区间就行，可以改成begin2>end2. 修正end2为n-1.

最终代码：

void MergeSortNonR(int* a, int n)
{
          
   
	int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);
	int gap = 1;

	while (gap < n)
	{
          
   
		for (int k = 0; k < n; k += 2 * gap)
		{
          
   
			//归并
			int begin1 = k;
			int end1 = k + gap - 1;
			int begin2 = k + gap;
			int end2 = k + gap * 2 - 1;
			int i = begin1;

			// end1 越界，修正
			if (end1 >= n)
				end1 = n - 1;

			// begin2 越界，第二个区间不存在
			if (begin2 >= n)
			{
          
   
				begin2 = n;
				end2 = n - 1;
			}

			// begin2 ok， end2越界，修正end2即可
			if (begin2 < n && end2 >= n)
				end2 = n - 1;

			while (begin1 <= end1 && begin2 <= end2)//有一个序列为空就停止
			{
          
   
				if (a[begin1] < a[begin2])
				{
          
   
					tmp[i++] = a[begin1++];
				}
				else
				{
          
   
					tmp[i++] = a[begin2++];
				}
			}

			//将剩余数据放入tmp数组
			while (begin1 <= end1)
			{
          
   
				tmp[i++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
          
   
				tmp[i++] = a[begin2++];
			}
		}
		//将合并后的序列拷贝到原数组中
		memcpy(a, tmp, n * sizeof(int));
		gap *= 2;
	}
	free(tmp);
}

复杂度及稳定性分析

归并排序的特性总结： 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。 时间复杂度：O(N*logN) 空间复杂度：O(N) 稳定性：稳定

8. 计数排序

为啥叫后面三个“桶”排序呢，因为它们都或多或少用到了桶的思想。

菜鸡大学生吐槽：在查找资料的时候经常有人把这三排序混起来。，。（悲）

那从简单的下手，先说计数排序。 比如我们有个单词Hippopotomonstrosesquippedaliophobia（长单词恐惧症） 我们想把它的字母排个序，怎么排好呢？ 根据观察，这个单词里面含有大量重复的字母，我们是不是可以数一下这些字母出现的次数， 然后按顺序写下来就好了？

计数排序的原理就是这个，它对于大量且集中的数据有奇效。

思路： 统计相同元素出现次数 。 根据统计的结果将序列回收到原来的序列中。

偷懒用个网上图片~~

如果数据里面有数的话可以考虑数据之间的相对位置。 或者可以考虑加上最小负数的绝对值。 总之办法总比困难多。

代码：

//计数排序
void CountSort(int* a, int n)
{
          
   
	int min = a[0], max = a[0];
	for (int i = 1; i < n; ++i)
	{
          
   
		if (a[i] < min)
			min = a[i];

		if (a[i] > max)
			max = a[i];
	}

	int range = max - min + 1;
	int* countA = (int*)malloc(sizeof(int) * range);
	assert(countA);
	memset(countA, 0, sizeof(int) * range);

	// 计数
	for (int i = 0; i < n; ++i)
	{
          
   
		countA[a[i] - min]++;
	}

	// 排序
	int j = 0;
	for (int i = 0; i < range; ++i)
	{
          
   
		while (countA[i]--)
		{
          
   
			a[j++] = i + min;
		}
	}
}

复杂度及稳定性分析

计数排序的特性总结： 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限,浮点数就不适用。 时间复杂度：O(range + N) 空间复杂度：O(range) 稳定性：稳定。

9. 基数排序

看完上一个排序我们发现，我们之前的排序都是两个数进行比较，然后观察是否要交换。

计数排序不需要，基数排序也不需要。 它是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

啥是多关键字？ 回到我们梦开始的地方。 对于电脑的数据，我们可以按照名称排序，按照修改日期排序，按照类型，按照大小…

以这个为例，我们可以按照名称和类型两个关键字进行排序。 先把不同类型的数据分成几堆，然后再分别按名称进行排序。

可能会用到的概念： MSD（Most significant digital）：先从高位开始进行排序。 LSD（Least significant digital）：先从低位开始进行排序。

那么基数排序怎么排呢，我们假设有一串三位数： 步骤：

按照个位数进行排序。 按照十位数进行排序。 按照百位数进行排序。

基数排序思想： 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。 从最低位进行一次排序。 3.从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

(图源：网络)

注意，数据放回去的时候一定要按照放进来的顺序放回去。 （看图）

基数排序在菜鸡大学生查找资料的过程中发现了两种写法。 一一给大家分享：

很常见的版本

由于每一位数的范围在0~9之间，所以我们可以准备十个桶。

代码：

//基数排序
//求最大位数
int Maxbit(int* arr, int n)
{
          
   
	int max = arr[0];
	for (int i = 1; i < n; i++)
	{
          
   
		if (arr[i] > max)
			max = arr[i];
	}

	int k = 1;
	while (max >= 10)
	{
          
   
		max /= 10;
		k++;
	}

	return k;
}

void RadixSort(int* arr, int n)
{
          
   
	int k = Maxbit(arr, n);
	int radix = 1;
	int* tmp = (int*)malloc(sizeof(int) * n);

	while (k)
	{
          
   
		int bucket[10] = {
          
    0 };

		//统计每个桶的数据个数
		for (int i = 0; i < n; i++)
		{
          
   
			bucket[arr[i] / radix % 10]++;
		}

		//累加
		for (int i = 1; i < 10; i++)
		{
          
   
			bucket[i] += bucket[i - 1];
		}

		//向tmp数组存入数据
		for (int i = n-1; i >=0; i--)
		{
          
   
			tmp[bucket[arr[i] / radix % 10] - 1] = arr[i];
			bucket[arr[i] / radix % 10]--;
		}

		//将tmp序列拷贝到原数组中
		memcpy(arr, tmp, n * sizeof(int));

		radix *= 10;
		k--;
	}
	free(tmp);
}

不常见的队列版本

先进先出想到了啥，是队列吧。 那我们直接上队列就好啦。 队列代码请到之前博客自取，如果你会c++当我没说。 (/ω＼*)……… (/ω•＼*)

void RadixSortQ(int* arr, int n)
{
          
   
	int k = Maxbit(arr, n);
	int radix = 1;

	while (k)
	{
          
   
		//初始化桶
		Queue q[10];
		for (int i = 0; i < 10; i++)
		{
          
   
			QueueInit(q + i);
		}

		//入队
		for (int i = 0; i < n; i++)
		{
          
   
			QueuePush(&q[arr[i] / radix % 10], arr[i]);
		}
		
		//出队
		int index = 0;
		for (int i = 0; i < 10; i++)
		{
          
   
			while (!QueueEmpty(q + i))
			{
          
   
				arr[index++] = QueueFront(q + i);
				QueuePop(q + i);
			}
		}
		k--;
		radix *= 10;
	}	
}

负数或者有正有负优化方式见计数排序。

复杂度及稳定性分析

基数排序的特性总结： 时间复杂度：O(range * N) 空间复杂度：O(range+k) 稳定性：稳定。

10. 桶排序

最后一个了！

真正意义上的桶排序它来啦。 菜鸡大学生之前也一直认为它是计数排序呢，结果发现这玩意比计数排序复杂。

（来自网上） 菜鸡大学生画图欲望日益下降。

思想： 将待排序的n个元素按照一定规律划分为m个区间，每个区间就是一个桶。 每个桶存放该区间的数据，由于每个桶内的数据元素个数不确定，可以使用链表表示，同时使用插入排序，让每个桶的链表有序。 这样按照次序将所有桶的元素连起来就得到完整的有序列表。

由于这排序不咋常见就直接放代码（摆烂）吧。

//桶排序
typedef int SLTDataType;
typedef struct SListNode
{
          
   
	SLTDataType data;
	struct SListNode* next;
}SListNode;

void InsertNode(SListNode** bucket, int data)
{
          
   
	SListNode* p = (SListNode*)malloc(sizeof(SListNode));
	p->data = data;
	p->next = NULL;

	// 桶为空 
	if (*bucket == NULL)
	{
          
   
		*bucket = p;
	}
	else
	{
          
   
		SListNode* prev = NULL;
		SListNode* cur = *bucket;

		while (cur != NULL && cur->data <= data)
		{
          
   
			prev = cur;
			cur = cur->next;
		}
		// 对插入到第一个结点前的情况处理
		if (prev == NULL)
		{
          
   
			*bucket = p;
			p->next = cur;
		}
		else
		{
          
   
			prev->next = p;
			p->next = cur;
		}
	}
}

void BucketSort(int* arr, int n)
{
          
   
	//寻找最大值最小值
	int max = arr[0], min = arr[0];
	for (int x = 0; x < n; x++) {
          
   
		max = arr[x] > max ? arr[x] : max;
		min = arr[x] < min ? arr[x] : min;
	}

	//获取容量
	int bucketsize = (max - min) / n + 1;

	//获取桶数量
	int bucketcount = (max - min) / bucketsize + 1;

	//申请桶空间
	SListNode** b=(SListNode**)calloc(bucketcount, sizeof(SListNode*));

	//分配数据
	for (int i = 0; i < n; i++)
	{
          
   
		//算出arr[i]对应的桶位置
		int pos = (arr[i] - min) / bucketsize;
		InsertNode(&b[pos], arr[i]);
	}

	//将数据返回到数组
	SListNode* tmp;
	for (int i = 0, j = 0; i < bucketcount && j < n; i++)
	{
          
   
		if (b[i] != NULL)
		{
          
   
			tmp = b[i];
			while (tmp != NULL)
			{
          
   
				arr[j++] = tmp->data;
				tmp = tmp->next;
			}
		}
	}

	//free
	for (int i = 0; i < bucketcount; i++)
	{
          
   
		while (b[i] != NULL)
		{
          
   
			tmp = b[i];
			b[i] = tmp->next;
			free(tmp);
		}
	}
	free(b);
}

复杂度及稳定性分析

桶排序的特性总结： 时间复杂度：O(range + N) 空间复杂度：O(range) 稳定性：稳定。

最后

我天，真不容易。