提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、插入排序
- 1.直接插入法
- 2.希尔排序法
- 二、交换排序
- 1. 冒泡排序
- 2. 快速排序
- 三、选择排序
- 1. 简单选择排序
- 2. 堆排序
- 四、归并排序
- 五、基数排序
前言
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
这个排序他是稳定的，因为”基你太稳！！！“
