复杂度及稳定性分析

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

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

从后往前@R_406_1997@又没啥波动，稳定的。

直接插入排序的特性总结：

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

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;
		}
	}
}

复杂度及稳定性分析

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，排序起来就比较快（可以看动图）。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法有很多。

在Knuth《计算机程序设计技巧》一书中，Knuth进行了大量的试验统计，计算出时间复杂度大概在O(N^1.25)到O(1.6N^1.5)之间。

4. 空间复杂度O(1)。
5. 稳定性：不稳定。

3.选择排序

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

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

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

  

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

注意特殊情况：

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

//选择排序
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(&amp;a[maxi], &a[end]);

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

		begin++;
		end--;
	}
}

复杂度及稳定性分析

直接选择排序的特性总结：

1. 直接选择排序由于效率不高（可能还不如冒泡），所以日常使用的范围有限。
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

有一种特殊情况，我们假设一串数据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);
	}
}

复杂度及稳定性分析

堆排序的特性总结：

1. 时间复杂度：O(N*LOGN)
2. 空间复杂度：O(1)
3. 稳定性：不稳定

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;
	}
}

复杂度及稳定性分析

冒泡排序的特性总结：

1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：稳定

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提出的，我们就得放在第一个，给创始人最大的排面。

思路：

1. 选key，一般是第一个或者最后一个。
2. 选定左指针和右指针从两头遍历数组。
3. 如果是从第一个开始就右指针先走，最后一个开始就左指针先走。 * （画图解释）*
4. 左指针遇到大于key的值就停下来，右指针遇到小于key的值就停下来。
5. 交换左右指针的值。
6. 直到相遇，交换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;
}

挖坑法

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

思路：

1. 选key，然后取出，留下一个坑。这里以左边第一个为key举例。
2. 右边的指针遇到小于基准值的数时，直接将该值放入坑中，而右指针指向的位置形成新的坑位。
3. 然后左指针遇到大于基准值的数时，将该值放入坑中，左指针指向的位置形成坑位。
4. 重复过程直到两指针相遇，将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为第一个数为例）

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

我们先来看一下单趟动图：

• 当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);
	}
}

非递归写法

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

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

思想：

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

代码：

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);
}

复杂度及稳定性分析

快速排序的特性总结：

1. 快速排序，好用，超好用。
2. 时间复杂度：O(N*logN)。
3. 空间复杂度：O(logN)。
4. 稳定性：不稳定。

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);
}

复杂度及稳定性分析

归并排序的特性总结：

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

8. 计数排序

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

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

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

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

思路：

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

偷懒用个网上图片~~

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

代码：

//计数排序
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;
		}
	}
}

复杂度及稳定性分析

计数排序的特性总结：

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

9. 基数排序

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

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

啥是多关键字？ 回到我们梦开始的地方。

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

可能会用到的概念：

• MSD（Most significant digital）：先从高位开始进行排序。
• LSD（Least significant digital）：先从低位开始进行排序。

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

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

基数排序思想：

1. 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。
2. 从最低位进行一次排序。 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;
	}	
}

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

复杂度及稳定性分析

基数排序的特性总结：

1. 时间复杂度：O(range * N)
2. 空间复杂度：O(range+k)
3. 稳定性：稳定。

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);
}

复杂度及稳定性分析

桶排序的特性总结：

1. 时间复杂度：O(range + N)
2. 空间复杂度：O(range)
3. 稳定性：稳定。

最后

我天，真不容易。