目录
?本文为C++实现的十大排序算法及基于排序算法解决的一些常见问题，每一种算法均实际运行，确保正确无误。文中内容为自己的一些理解，如有错误，请大家指正。
0 概述
在十种排序算法中，前七种是比较类排序，后三种是非比较类排序，每种算法的最好、最坏、平均时间复杂度，空间复杂度以及稳定性如下表所示。稳定性是指排序前后相等的元素相对位置保持不变。
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn) | O( | O(n2) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n + logn) | 稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(n2) | O(logn) | 不稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 计数排序 | O(n + k) | O(n + k) | O(n2) | O(n + k) | 稳定 |
| 桶排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 稳定 |
| 基数排序 | O(n × k) | O(n × k) | O(n × k) | O(n + k) | 稳定 |
具体思路和代码均为顺序排序。
前三种排序比较类似，都是将数组划分成已排序部分和未排序部分，因此有两层循环，一层循环划分已排序和未排序部分的边界，一层循环选择不同的方法依次对未排序的部分进行排序。
1 冒泡排序
顾名思义，冒泡排序（bubble sort）是将最大的数依次 “上浮” 到数组的末尾，实现数组有序。
具体的算法实现原理：
两层循环，第一层划分边界，从后向前。第二层循环从最前往后依次两两比较，如果前面的数比后面的数大，则交换两个数，如果前面的数比后面的数小，则保持不变。
动态图解：
代码：
#include <iostream>
#include <vector>
using namespace std;
//冒泡排序
void bubbleSort(vector<int> &vec){
int len = vec.size();
if (len <= 1){
return;
}
for (int i = len -1; i > 0; i--){
bool flag = false; //使用flag判断j前面的子序列是否已经有序
for (int j = 0; j < i; j++){
if (vec[j] > vec[j + 1]){
swap(vec[j], vec[j + 1]);
flag = true;
}
}
if (!flag){
break;
}
}
}
//打印数组
void printVec(vector<int> vec){
for (auto c : vec){
cout << c << " ";
}
cout << endl;
}
//test
int main(){
vector<int> test_vec = {1, 2, 5, 7, 3, 5, 9, 33, 44, 99, 55};
printVec(test_vec);
bubbleSort(test_vec);
printVec(test_vec);
system("pause");
return 0;
}2 选择排序
具体的算法实现原理：
选择排序（selection sort）已排序部分为数组的前部，然后选择数组后部未排序中的最小的数依次与未排序的第一个数交换（交换会造成排序不稳定），然后边界后移，继续选择、交换，直到数组有序。
两层循环，第一层划分边界，第二层循环查找未排序部分最小的数，并与未排序部分的第一个数交换。
动态图解：
代码：
#include <iostream>
#include <vector>
using namespace std;
//选择排序
void selectSort(vector<int> &vec){
int len = vec.size();
if (len <= 1){
return;
}
for (int i = 0; i < len; i++){
int min = i;
for (int j = i; j < len; j++){
if (vec[j] < vec[min]){
min = j;
}
}
swap(vec[i], vec[min]);
}
}
//打印数组
void printVec(vector<int> vec){
for (auto c : vec){
cout << c << " ";
}
cout << endl;
}
//test
int main(){
vector<int> test_vec = {1, 5, 2, 7, 3, 5, 9, 33, 44, 99, 55};
printVec(test_vec);
selectSort(test_vec);
printVec(test_vec);
system("pause");
return 0;
}3 插入排序
具体的算法实现原理：
插入排序（insertion sort）已排序部分也为数组的前部，然后将未排序部分的第一个数插入到已排序部分的合适的位置。
两层循环，第一层划分边界，第二层循环将已排序部分的数从后向前依次与未排序部分的第一个数比较，若已排序部分的数比未排序部分的第一个数大则交换，这样未排序部分的第一个数就插入到已排序部分的合适的位置，然后向后移动边界，重复此过程，直到有序。
动态图解：
?代码：
#include <iostream>
#include <vector>
using namespace std;
//插入排序
void insertSort(vector<int> &vec){
int length = vec.size();
if (length <= 1){
return;
}
for (int i = 1; i < length - 1; i++){
//int temp = vec[i];
for (int j = i - 1; j >= 0; j--){
if (vec[j] > vec[j + 1]){
swap(vec[j+1], vec[j]);
}
}
}
}
//打印数组
void printVec(vector<int> vec){
for (auto c : vec){
cout << c << " ";
}
cout << endl;
}
//test
int main(){
vector<int> test_vec = {1, 5, 2, 7, 3, 5, 9};
printVec(test_vec);
insertSort(test_vec);
printVec(test_vec);
system("pause");
return 0;
}4 希尔排序
希尔排序是插入排序的升级，算法原理如下：
1) 首先，从数组的首元素开始每隔“步长(间隔)”个元素就挑选一个元素出来作为子数组元素;
2) 然后每个子数组各自进行比较，比较好后，每个子数组都有顺序，进入下一轮，步长(间隔)减少，再根据步长(间隔)分组进行比较;
3) 重复以上操作，最后就有序了。
图解：
?代码：
#include <iostream>
#include <vector>
using namespace std;
//希尔排序
void shellSort(vector<int> &vec){
int len = vec.size();
if (len <= 1) return;
//以h为步长划分数组，h /= 2为缩小的增量，数字2可自己根据数据选择
for (int h = len / 2; h > 0; h /= 2){
//以下为插入排序
for (int j = h; j < len; j++){
int temp = vec[j];
for (int k = j - h; k >= 0; k -= h){
if (vec[k] > temp){
swap(vec[k], vec[k + h]);
}
}
}
}
}
//打印数组
void printVec(vector<int> vec){
for (auto c : vec){
cout << c << " ";
}
cout << endl;
}
//test
int main(){
vector<int> test_vec = {1, 5, 2, 7, 3, 5, 9, 33, 44, 99, 55};
printVec(test_vec);
shellSort(test_vec);
printVec(test_vec);
system("pause");
return 0;
}