目录

一、冒泡排序（BubbleSort）

二、选择排序（ SelectSort）

三、插入排序（InsertSort）

四、希尔排序（ShellSort）

五、堆排序

六、快排（QuickSort）

Hoare版本

前后指针法

优化之三数取中

七、归并排序（MergeSort）

八、计数排序（CountSoort）

九、小结

---

注：本文排序都是升序

一、冒泡排序（BubbleSort）

通过连续地比较与交换相邻元素实现排序，这个过程就像气泡从底部升到顶部一样， 因此得名冒泡排序。

冒泡过程可以利用元素交换操作来模拟：从数组最左端开始向右遍历，依次比较相邻元素大 小，如果“左元素>右元素”就交换二者。遍历完成后，最大的元素会被移动到数组的最右端。

代码实现：

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

动图演示：

二、选择排序（ SelectSort）

开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾：

1. 初始状态下，所有元素未排序，即未排序（索引）区间为[0,𝑛−1]。
2. 选取区间[0,𝑛−1]中的最小元素，将其与索引0处的元素交换。完成后，数组前1个元素已排序。
3. 选取区间[1,𝑛−1]中的最小元素，将其与索引1处的元素交换。完成后，数组前2个元素已排序。
4. 以此类推。经过𝑛−1轮选择与交换后，数组前𝑛−1个元素已排序。
5. 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。

代码实现：

//简单选择排序
void SelectSort1(int* arr, size_t size) {
	//外层循环：[0,size-1]
	for (size_t i = 0; i < size - 1; i++)
	{
		//记录最小值的索引
		size_t mini = i;
		//内层循环：找到未排序区间[1,size-1]的最小值
		//需要找size-1个数
		for (size_t j = i + 1; j < size; j++)
		{
			if (arr[mini] > arr[j])
				mini = j;
		}
			Swap(&arr[i], &arr[mini]);
	}
}

优化版本：

从区间两边缩小，区间最左侧放最小值，区间最右侧放最大值

void SelectSort2(int* arr, size_t size) {
	size_t left = 0, right = size - 1;

	while (left <= right) {
		//假设第一个索引的值既是最大值也是最小值
		size_t mini = left, maxi = left;
		//只需要从第二个值开始遍历 找新的最大值最小值
		for (size_t i = left + 1; i <= right; i++)
		{
			if (arr[i] > arr[maxi]) 
				maxi = i;
			if (arr[i] < arr[mini]) 
				mini = i;
		}
		//交换值
		Swap(&arr[left], &arr[mini]);
		//这里需要多个判断 如果maxi == left 两数交换两次相当于没有交换
		if (maxi == left) maxi = mini;
		Swap(&arr[right], &arr[maxi]);

		left++;
		right--;
	}
}

动图演示：

三、插入排序（InsertSort）

与手动整理一副牌的过程非常相似。 具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。

代码实现：

//插入排序
void InsertSort(int* arr, int size) {
	//end走到倒数第二个就停下，无需再做比较
	for (size_t i = 0; i < size - 1; i++)
	{
		//[0,end],end+1
		int end = i;
		int insertVal = arr[end + 1];
		while (end >= 0) {
			if (insertVal < arr[end]) {
				arr[end + 1] = arr[end];
				end--;
			}
			else {
				break;
			}
		}
		arr[end + 1] = insertVal;
	}
	
}

 

动图演示：

四、希尔排序（ShellSort）

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

这里可以得到一个结论：

gap越大，数据跳跃越快，越小的越容易到前面，但是越不接近有序

gap越小，数据跳跃越慢，越小的不更易到前面，但是越接近有序

代码实现：

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

五、堆排序

流程：

1）建堆 实现升序建大根堆 实现降序建小根堆

核心原理：

堆排序通过反复提取堆顶元素（极值）实现排序，堆的类型决定了提取元素的顺序：

• 大顶堆：堆顶始终为当前最大值
• 小顶堆：堆顶始终为当前最小值

2） 排序 利用堆删除思想排序

注：此流程图来源 hello‑algo.com

代码实现：

//向下调整算法，参数：数组 数组元素个数 开始向下调整的父节点索引
AdjustDown(HpDataType* arr, size_t size, size_t parent) {
	//找较大的子节点，假设左子节点较大
	size_t child = 2 * parent + 1;
	//child索引不断增大，但不会超过数组元素个数
	while (child < size) {
		//假设错误，右子节点更大，更新索引
		if (child + 1 < size && arr[child] < arr[child + 1]) {
			child++;
		}
		//如果父节点小于等于子节点，交换两节点的值
		if (arr[parent] <= arr[child]) {
			Swap(&arr[parent], &arr[child]);
			//更新父节点的索引，现在变成儿子了
			parent = child;
			//继续找儿子比较
			child = 2 * parent + 1;
		}
		else {
			break;
		}
	}
}

void HeapSort(HpDataType* arr, int size) {
	// 建堆 升序建大根堆 降序建小根堆
	for (int i = (size - 2) / 2; i >= 0; i--) {
		AdjustDown(arr, size, i);
	}

	// 排序
	int end = size - 1;
	while (end > 0) {
		Swap(&arr[0], &arr[end]);  
		AdjustDown(arr, end, 0);   
		end--;
	}
}

六、快排（QuickSort）

Hoare版本

快排最早是由Hoare提出的，所以，他的经典思想我们有必要学习一下

有如下步骤：

1.基准元素选择

        选择数组第一个元素作为基准，记录基准索引keyi

2.双向指针扫描

• 设置两个指针left和right，left从数组左端（begin）开始向右扫描，right从右端（end）开始向左扫描，一定要让右指针先走，这样才能保证较大值右移、较小值左移 
•  right指针寻找第一个小于等于基准的元素，找到之后停止不动
• left指针寻找第一个大于等于基准的元素，找到之后停止不动
• 当两指针相遇或交叉时停止扫描       

3.  ​​​​​​元素交换

        当left < right时，交换arr[left]和arr[right]的值。这个交换操作能使较大值右移、较小值左移

4.分区完成判断

       重复步骤2-3直到left >= right，此时j所指位置即为当前分区的中间点。此时数组被划分           为：左区间：[begin,keyi-1]右区间：[keyi+1,end]

5.递归排序

        对左右两个子数组分别递归执行上述过程，直到子数组长度为1时终止递归

第一趟详细排序：

递归完成最后排序：

动图演示：

代码实现：

//Hoare版本快排
void QuickSort2(int* arr, int left, int right) {
	if (left >= right)
		return;
	//创建变量保存区间边界
	int keyi = left;
	int begin = left, end = right;

	while (left < right) {
		//右边找小
		while (left < right && arr[keyi] <= arr[right]) {
			--right;
		}
		//左边找大
		while (left < right && arr[keyi] >= arr[left]) {
			++left;
		}
		Swap(&arr[left], &arr[right]);
	}

	Swap(&arr[keyi], &arr[left]);
	keyi = left;

	// [begin, keyi-1]keyi[keyi+1, end]
	QuickSort2(arr, begin, keyi - 1);
	QuickSort2(arr, keyi + 1, end);
	
}

前后指针法

动图演示：

核心思路：

1.选定最左侧元素为基准值并保存，将prev设置为left，cur设置为left+1

2.cur去寻找当前区间内比基准值小的元素

3.如果没找到，说明基准值右侧的元素都是大于基准值的，不需要其他操作，直接跳出循环即可

4.如果找到了先prev++，再将prev和cur位置的元素交换，然后cur++。

5.等到cur越界之后，说明遍历完序列中的所有元素了，将基准值位置的元素和prev位置的元素交换

6.最后返回prev即可

代码实现：

//前后指针法快排
void QuickSort1(int* arr, int left, int right) {
	if (left >= right)
		return;

	int prev = left, keyi = left;
	int cur = left + 1;

	while (cur <= right) {
		if (arr[cur] < arr[keyi] && prev++ != cur) {
			Swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	Swap(&arr[prev], &arr[keyi]);
	keyi = prev;
	//[left, keyi - 1] keyi [keyi + 1, right]
	QuickSort1(arr, left, keyi - 1);
	QuickSort1(arr, keyi + 1, right);
}

优化之三数取中

如果遇到有序序列或者是接近有序序列，快排的效率就会接近O(n^2)，原因是我们每次选择keyi都是区间左值，这样可能选取到极端值（比如最小或最大元素）作为基准，这样会导致分区不平衡。

三数取中，顾名思义：取三个数中第二大的数

代码实现：

//三数取中
int ThreeNumMid(int* arr, int left, int right) {
	int mid = (left + right) / 2;

	if (arr[mid] < arr[right]) {
		if (arr[mid] > arr[left]) {
			return mid;
		}
		else if(arr[left] < arr[right]) {
			return left;
		}
		else {
			return right;
		}
	}
	else {// arr[mid] > arr[right]
		if (arr[mid] < arr[left]) {
			return mid;
		}
		else if (arr[right] < arr[left]) {
			return left;
		}
		else {
			return right;
		}
	}
}

但是如果数据量过小，我们三数取中法又显得十分累赘，这种情况下，我们可以选择更高效的排序，插入排序

优化后的代码：

//Hoare版本快排
void QuickSort2(int* arr, int left, int right) {
	if (left >= right)
		return;
	// 小区间选择走插入，可以减少90%左右的递归
	if (right - left + 1 < 10)
	{
		InsertSort(arr + left, right - left + 1);
	}
	else {
		//创建变量保存区间边界
		int midi = ThreeNumMid(arr, left, right);
		Swap(&arr[left], &arr[midi]);
		int keyi = left;
		int begin = left, end = right;

		while (left < right) {
			//右边找小
			while (left < right && arr[keyi] <= arr[right]) {
				--right;
			}
			//左边找大
			while (left < right && arr[keyi] >= arr[left]) {
				++left;
			}
			Swap(&arr[left], &arr[right]);
		}

		Swap(&arr[keyi], &arr[left]);
		keyi = left;

		// [begin, keyi-1]keyi[keyi+1, end]
		QuickSort2(arr, begin, keyi - 1);
		QuickSort2(arr, keyi + 1, end);

	}
	
	//双指针法快排
void QuickSort1(int* arr, int left, int right) {
	if (left >= right)
		return;

	// 新增三数取中逻辑
	int mid = ThreeNumMid(arr, left, right);
	Swap(&arr[left], &arr[mid]);
	int keyi = left;

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

	QuickSort1(arr, left, keyi - 1);
	QuickSort1(arr, keyi + 1, right);
}

七、归并排序（MergeSort）

归并排序利用分治的思想，分为划分区间和归并排序两个阶段

1.划分区间阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题

2.归并排序阶段：当子数组长度为1时终止划分，开始归并，持续地将左右两个较短的有序数组归并为一个较长的有序数组，直至结束

如下图所示：

观察发现，归并排序与二叉树后序遍历的递归顺序是一致的。 ‧ 后序遍历：先递归左子树，再递归右子树，最后处理根节点 ‧ 归并排序：先递归左子数组，再递归右子数组，最后处理合并

代码实现：

//归并排序
void _MergeSort(int* arr, int* tmp, int begin, int end) {
	//递归到最小子区间
	if (begin == end)
		return;

	int mid = (begin + end) / 2;
	//[begin,mid] [mid+1,end]
	_MergeSort(arr, tmp, begin, mid);
	_MergeSort(arr, tmp, mid+1, end);

	//归并排序 将更大的值尾插到tmp数组中
	//分出两个区间范围值
	int left1 = begin, right1 = mid;
	int left2 = mid + 1, right2 = end;
	int i = begin;
	//判断两个区间的值谁更小
	while (left1 <= right1 && left2 <= right2) {
		if (arr[left1] < arr[left2]) {
			tmp[i++] = arr[left1++];
		}
		else {
			tmp[i++] = arr[left2++];
		}
	}
	//任何一个区间结束，将剩余的直接尾插
	while (left1 <= right1) {
		tmp[i++] = arr[left1++];
	}
	while (left2 <= right2) {
		tmp[i++] = arr[left2++];
	}

	//将排序好的tmp拷贝到arr中
	memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* arr, size_t size) {
	int* tmp = (int*)malloc(sizeof(int) * size);
	if (tmp == NULL) {
		perror("malloc() err!");
		return;
	}
	_MergeSort(arr, tmp, 0, size - 1);
	free(tmp);
	tmp = NULL;
}

动图演示：

八、计数排序（CountSoort）

核心原理：

统计每个数出现的次数，一个数出现几次，映射的位置值就加几次

这个排序算法有一定的局限性：

• 只适用于整型排序
• 只适用于数据集中的数据群
• 不适用于数据较为分散的数据群

代码实现：

//计数排序
void CountSoort(int* arr, size_t size) {
	//找最大值和最小值
	int min = arr[0], max = arr[0];
	for (size_t i = 1; i < size; i++)
	{
		if (arr[i] < min) min = arr[i];
		if (arr[i] > max) max = arr[i];
	}
	//创建临时数组用于统计次数
	int range = max - min + 1;
	int* tmp = (int*)malloc(sizeof(int) * range);
	if (tmp == NULL) {
		perror("malloc() err!");
		return;
	}
	memset(tmp, 0, sizeof(int) * range);

	//统计次数
	for (size_t i = 0; i < size; i++)
	{
		tmp[arr[i] - min]++;
	}
	//排序
	int j = 0;
	for (size_t i = 0; i < range; i++)
	{
		while (tmp[i]--) {
			arr[j++] = i + min;
		}
	}

}

动图演示：

九、小结

算法的稳定性：稳定排序在完成排序后，相等元素在数组中的相对顺序不发生改变 

 看到了这里，麻烦点个赞和关注再走吧~