本文讲解排序算法中常见又较复杂的几种排序算法：归并排序、快速排序、桶排序、基数排序.
1. 归并排序
步骤：
- 递归排序中点左边和中点右边
- 然后归并
- 两个指针，各自指向最值，然后对比两边的最小值，最小的放入临时数组中
- 更新指针，类推
- 最后剩余的一边直接塞入临时数组的尾部
- 即完成排序
算法分析：
（1）时间复杂度：O(nlog2n)
（2）空间复杂度：O(n)
优点：
- 稳定性： 相同元素的相对顺序保持不变
- 可扩展性： 很容易扩展到计算环境中，通过并行归并来提高排序效率
缺点：
- 额外空间：需要开辟一个额外的空间来存储合并后的结果
- 复杂性：算法实现相对复杂，相比于简单的算法而言
以下是C++归并排序的代码模板
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;vector<int> temp; // 定义临时数组// 输出函数
void merge_print(const vector<int>& v) {for (int i = 0; i < v.size(); i++) {cout << v[i] << " ";}cout << endl;
}void mergeSort(vector<int>& arr, int l, int r) {if (l >= r) {return;}int mid = (l + r) / 2;mergeSort(arr, l, mid); // 递归排序左边mergeSort(arr, mid + 1, r); // 递归排序右边int i = l, j = mid + 1;int cnt = 0;while (i <= mid && j <= r) { // 归并if (arr[i] <= arr[j]) {temp[cnt++] = arr[i++];}else {temp[cnt++] = arr[j++];}}while (i <= mid) { // 剩余的一边直接塞入数组temp[cnt++] = arr[i++];}while (j <= r) {temp[cnt++] = arr[j++];}for (int i = 0; i < r - l + 1; i++) {arr[i + l] = temp[i]; // 重新赋值回来}
}int main() {vector<int> v;v.push_back(2);v.push_back(5);v.push_back(1);v.push_back(4);v.push_back(6);v.push_back(3);temp.resize((int)v.size(), 0);cout << "排序前：" << endl;merge_print(v);mergeSort(v, 0, (int)v.size() - 1);cout << "归并排序后：" << endl;merge_print(v);cout << endl;system("pause");return 0;
}2. 快速排序
步骤：
设当前的待排序的序列为 R[low,hight] ， 其中 low<=hight。同时选取首元素为基准元素。
- 步骤一：选取首元素的第一个元素作为基准元素 pivot=R[low] ，i=low ，j=hight。
- 步骤二：从右向左扫描，找到小于等于 pivot 的数，如果找到，R[i] 和 R[j] 交换 ，i++。
- 步骤三：从左向右扫描，找到大于 pivot 的数，如果找到，R[i] 和 R[j] 交换，j--。
- 步骤四：重复 步骤二~步骤三，直到 j 与 i 的指针重合 返回位置 mid=i ，该位置的数正好是 pivot 元素。
算法分析：
（1）时间复杂度：O(nlogn)
（2）空间复杂度：O(lognn)
优点：
- 高效性：快速排序在大多数情况下具有较高的排序效率
- 适应性：适合各种数据类型的额排序
- 原地排序：不需要额外的存储空间
缺点：
- 最坏情况下时间复杂度为 O(n^2)
- 不稳定性：相同元素的相对顺序可能会改变
以下是 C++快速排序算法的模板
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;int part(vector<int>& nums, int low, int hight) { // 划分函数int i = low, j = hight, pivot = nums[low]; // 以首元素为基准元素while (i < j) {while (i < j && nums[j] > pivot) { // 从左向右开始找一个小于等于pivot数的值j--; } if (i < j) { // 如果当前元素小于pivot的值，则交换，i向右移一位swap(nums[i], nums[j]);i++;}while (i < j && nums[i] <= pivot) { // 左边和右边相反的操作i++;}if (i < j) {swap(nums[i], nums[j]);j--;}}return i; //返回最终划分完成后基准元素所在的位置
}// 快速排序
void QuickSort(vector<int>& nums, int low, int hight) {int mid;if (low < hight) {mid = part(nums, low, hight); // 返回基准元素位置QuickSort(nums, low, mid - 1); // 左区间递归快速排序QuickSort(nums, mid + 1,hight);// 右区间递归快速排序}
}int main() {vector<int> nums;nums.push_back(30);nums.push_back(24);nums.push_back(5);nums.push_back(58);nums.push_back(18);cout << "排序前：" << endl;for (int i = 0; i < nums.size(); i++) {cout << nums[i] << " ";}cout << endl;QuickSort(nums, 0, nums.size()-1);cout << "快速排序后：" << endl;for (int i = 0; i < nums.size(); i++) {cout << nums[i] << " ";}cout << endl;system("pause");return 0;
}
3. 桶排序
步骤：
- 分组
- 桶内排序
- 合并
算法分析：
（1）时间复杂度：取决于对桶内选择的排序算法
（2）空间复杂度：O(n)
优点：
- 适用于一定范围内的整数或浮点数排序，不需要比较元素之间的大小
- 较稳定的一种排序算法
缺点：
- 当数据范围较大是，需要的桶数量较多，会消耗较多的内存空间
- 桶排序是一种线性排序，不适合大规模数据排序
以下是 C++桶排序算法的模板
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;// 输出函数
void bucket_print(const vector<int>& v) {for (int i = 0; i < v.size(); i++) {cout << v[i] << " ";}cout << endl;
}// 插入排序
void insert_sort(vector<int>& v) {for (int i = 1; i < v.size(); i++) {int key = v[i];int j = i - 1;while (j >= 0 && v[j] > key) {v[j + 1] = v[j];j--;}v[j + 1] = key;}
}void bucket_sort(vector<int>& v) {int i;int maxValue = v[0];for (i = 1; i < v.size(); i++) {if (maxValue < v[i]) {maxValue = v[i];}}// 设置10个桶vector<int> buckts[10];// 桶的大小bucketSize根据数组最大值确定：比如最大值99， 桶大小10// 最大值999，桶大小100// 根据最高位数字映射到相应的桶，映射函数为 v[i]/bucketSizeint bucktSize = 1;while (maxValue) {maxValue /= 10;bucktSize *= 10;}bucktSize /= 10;// 放入桶中for (int i = 0; i < v.size(); i++) {int index = v[i] / bucktSize; // 映射函数buckts[index].push_back(v[i]);// 插入排序，对每个桶都排序insert_sort(buckts[index]);}// 顺序访问桶，合并成一个有序序列int index = 0;for (int i = 0; i < v.size(); i++) {for (int j = 0; j < buckts[i].size(); j++) {v[index++] = buckts[i][j];}}}int main() {vector<int> v;v.push_back(6);v.push_back(15);v.push_back(3);v.push_back(422);v.push_back(25);cout << "排序前：" << endl;bucket_print(v);// 桶排序bucket_sort(v);cout << "桶排序后：" << endl;bucket_print(v);cout << endl;system("pause");return 0;
}4. 基数排序
步骤：
- 步骤一： 申请 10 个队列基数桶，根据每个元素的基数，来映射到对应桶中 0~9
- 步骤二： 求出数组中最大的元素，并求出他的位数n，作为操作排序的次数
- 步骤三： 操作 n 次，从个位数开始，取出各个数的位数，根据各个数的位数值放入不同的桶中
- 步骤四： 顺序访问桶，如果桶中有数据，则取出桶中最底下元素放入到数组中，队列桶出队
- 步骤五： 操作 n 次以后，不断更新数组和队列桶，n 次时，数组中元素已有序
图示：
第一轮：
第二轮
第三轮
算法分析：
（1）时间复杂度：O(d(n+r)), d 是数字的位数，n 是待排序元素的数量，r 是基数(radix)
（2）空间复杂度：取决于使用的桶的数量和存储桶的方式
优点：
- 不需要进行元素间的比较
缺点：
- 需要用额外的空间来存储桶，对于大型数据可能会消耗较多的内存
- 对于复杂的数据类型如浮点数或者负数的情况，需要额外的处理来实现基数排序
以下是 C++基数排序算法的代码模板：
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;// 输出函数
void radix_print(const vector<int>& v) {for (int i = 0; i < v.size(); i++) {cout << v[i] << " ";}cout << endl;
}// 基数排序
void radix_sort(vector<int>& arr) {int n = arr.size();vector<queue<int>> bucket(10);// 取出待排序元素中的最大值，求出它的最大位数，即为判断循环的条件int maxElement = *max_element(arr.begin(), arr.end());int N = 0; // 判断待排序次数while (maxElement) {maxElement /= 10;N++;}int t = 1; // 取位数while (N > 0) {// 取出每个数的基数，从个位数开始for (int i = 0; i < n; i++) {int index = (arr[i] / t) % 10; // 找到对应的基数桶塞入 bucket[index].push(arr[i]);}int index = 0; // 重新放回数组中for (int i = 0; i < 10; i++) {while (!bucket[i].empty()) { // 如果该桶不为空，再出队arr[index++] = bucket[i].front(); // 则取出队首元素,加入数组中bucket[i].pop();}}t *= 10;N--;}
}int main() {// 待排数据vector<int> v;v.push_back(6);v.push_back(15);v.push_back(3);v.push_back(422);v.push_back(25);cout << "排序前：" << endl;radix_print(v);// 桶排序radix_sort(v);cout << "桶排序后：" << endl;radix_print(v);cout << endl;system("pause");return 0;
}
