【算法篇】——数据结构中常见八大排序算法的过程原理详解

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

C++数据结构中的排序算法是编程基础中的重要内容。本文将介绍八大经典排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、希尔排序和计数排序。每种算法都有其独特的优势和应用场景，从小规模数据到大规模数据，从简单的整数排序到复杂的排序需求。通过理解和应用这些算法，可以更好地解决实际编程中的排序问题，提升程序性能和效率。
八大排序性能对比表：
“不改变相同元素的相对排布，即为稳定”

一、插入排序

1.直接插入法

核心的思想：和前面的比，找到对应的位置插入（对应的位置是指，使得该位置的前面的数都是有序数的位置）

流程（从小到大排）：
1.取数组中的第一个
2.取数组中的第二个，从后往前，前面的逐个对比，若比前面的小，则往前移，
3.取数组中的第三个，从后往前，前面的逐个对比，若比前面的小，则往前移，
n.依次类推，取数组中的第n个，从后往前，前面的逐个对比，若比前面的小，则往前移

2.希尔排序法

核心的思想：对每个子表进行直接的插入排序
子表：

流程：

流程（从小到大）：
1.第一趟：步长d=4时，分割的子表为：[49,76]，[38,13]，[65,27]，[97,49]
对每个子表执行直接插入排序，得到第一次排序数组为：
[49，13，27，49，76，38，65，97]

2.第二趟：步长d=d/2=2时，在第一次排序的基础上：[49,13,27,49,76,38,65,97]
分割的子表为：[49,27]，[76,65]，[13,49]，[38,97]
对每个子表执行直接插入排序，得到第二次排序数组为：
[27，13，49，38，65，49，76，97]

3.第三趟：步长d=d/2=1时，在第二次排序的基础上：[27,13,49,38,65,49,76,97]
分割的子表为：[27,13]，[49,38]，[65,49]，[76,97]
对每个子表执行直接插入排序，得到最终的排序数组为：
[13，27，38，49，49，65，76，97]

注意：一般第一趟的步长，题目都会给，不然就去取d=数组的大小/2，每次的步长取上一次的步长的1/2。

二、交换排序

1. 冒泡排序

核心的思想：从后两两相比，更小的往后放
流程：

示例：

#include<iostream>
#include<vector>
using namespace std;
void swap1(int &a,int &b)
{
	int temp = a;
	a = b;
	b = temp;
}
void Sort(vector<int> &c,int n) {
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n;j++) {
			if (c[i] > c[j]) {
				swap1(c[i], c[j]);
			}
		}
	}
}
int main() {
	int n; 
	cin >> n;         //输入排序的元素的个数
	cout << "数日排序元素的大小：" << endl;
	vector<int> c(n);
	for (int i = 0; i < n;i++) {
		cin >> c[i];  //输入排序的元素
	}
	Sort(c, n);    //进行冒泡排序
	cout << "排序后的数位" << endl;
	for (auto c1 : c) {
		cout << c1 <<" "  ;
	}
	system("pause");
	return 0;
}

优化冒泡排序的思路：
增加一个判断是否交换的标志，如果某一轮的排序中，没有发生交换，则结束排序算法（代表已经排好序了）

2. 快速排序

快排的打油诗：
小放枢轴左，大放枢轴右；
高低所指换，换针向枢轴；
高低所遇处，枢轴所落入；
递归再排至，左右仅一头。

流程：
1.选择枢轴：选择数组的第一个元素为枢轴值（上述例子的49）
2.定义高低移动的双指针：数组的两头
3.每次移动前都和枢轴进行判断：
注意：一开始是高指针和枢轴进行对比（枢轴选择第一个元素，相当于低指针的初值）
a.指针和枢轴的值比较，如果相等：当前运动的指针移一位（高向前移，低向后移），继续移动当前指针进行对比判断。
b.指针和枢轴的值比较，如果不等：当前指针的值比枢轴，那就将当前指针的值放在低指针的位置；反之，放在高指针的位置(小放枢轴左，大放枢轴右)；然后换指针运动，将当前运动的指针换成另外一个进行运动

4.直到两个指针相遇：该位置即为对应的值，应该所处的位置。

5.再进行递归快排

a.对第一次快排的结果，从第一次的枢轴的值49处，进行分区间执行快排，

b.直到左右仅一头

程序的实现，思考两个问题：
1.如何实现分区的逻辑？
如何返回每个区间的枢轴
2.如何控制分区的次数？
实际上是一个二叉树的遍历的问题，可使用递归
示例：

#include<iostream>
#include<vector>
using namespace std;
//进行分区
int partition(vector<int> &A, int slow, int fast) {
	int pos_nums = A[slow];
	while (slow < fast) {
		//注意：下面的while一定要加上slow < fast这个条件，这里并不是多余的，当排序的数组为：23,56,23,652,32,45，即第一个元素为最小值时，
		//会出现fast一直将为负数的情况出现，血的教训！！！
		while (A[fast] >= pos_nums && slow < fast) {
			fast--;
			//cout << "fast的值为:" << fast << endl;
		}
		A[slow] = A[fast];
		while (A[slow] <= pos_nums && slow < fast) {
			slow++;
		}
		A[fast] = A[slow];
	}
	A[slow] = pos_nums;
	return slow;
}
//递归排序
void Quicksort(vector<int>& A, int low, int hight) {
	if (low < hight) {
		int pos = partition(A, low, hight);
		Quicksort(A, low, pos - 1);
		Quicksort(A, pos + 1, hight);
	}
}
int main() {
	int n;
	cout << " 请输入排序的序列的大小  " << endl;
	cin >> n;
	vector<int> c(n);
	cout << "请输入排序的元素：" << endl;
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}
	Quicksort(c, 0, c.size() - 1);
	cout << "排列后数组为：" << endl;
	for (const auto& elem : c) {
		cout << elem << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

三、选择排序

1. 简单选择排序

核心思想：先扫（遍历一遍），再找（找到最小的），放在最前（和第一个元素交换）

流程：

2. 堆排序

堆排序口诀：
先建堆，再找数；
找一次，建一次；
找到数，就输出；
输出完，排序完；
流程：
大根堆含义：根节点的值 > 左，右孩子节点的值
(1). 建立大根堆
a. 例如上述上午数组[49,38,65,97,76,13,27,49]建立的二叉树结构为：

b. 构建大根堆
原则：让大元素上升，小的元素下坠，直到构建完成
检查具有孩子节点的根节点，如上述的例子，即为节点97，38，65，49，将数值最大给父节点。
操作如下：
比如，上述的38节点，有孩子节点97，36，父节点的值不是最大值，那么将最大值97和父节点38互换，重复这个步骤，检查完所有的父节点。
构建的第一次大根堆为：

(2). 再找数
找数：找大根堆的根节点（即这个数组的最大值）
输出：将根节点的值保存，并将根节点的位置的值换成，堆中的最后一个元素的值，

(3) 找一次，建一次
经过**（2）**输出最大的结果之后，再将新的二叉树结构进行重新排列，使其满足大根堆的条件：

最后，再输出最大值，替换根节节点的数值，重复（1）,（2）的步骤，直到结束

四、归并排序

核心的思想：把两个有序的数组，并为一个有序的数组
方法：另外建表，分别从两序列的头依次对比

例程数组：

注意：单个元素属于也属于有序的数组
流程：
1.另外建表：将数组分成有序的数组（单个元素的数组）：

2.依次对比：分别进行两序列的头依次对比，数值小的往新表中添加

3.同理，重复上述的步骤，得到排序后的结果：

五、基数排序

例程数组：

设置的排序的列表：

流程：
存储的结构是链式的结构：49->38->65->97->76->13->27->49
1.看个位数：例如，第一个元素49，个位数为9，那么排到Q9的位置，同理，排其他的数字，如下图所示：

得到的初次排序：49->49->38->97->27->76->65->13

2.看十位数：例如，第一个元素49，个位数为9，那么排到Q9的位置，同理，排其他的数字，如下图所示：

最终的排序：97->76->65->49->49->38->27->13
这个排序他是稳定的，因为”基你太稳！！！“