目录
0 概述
1 冒泡排序
2 选择排序
3 插入排序
4 希尔排序
5 归并排序
6 堆排序
7 快速排序
8 计数排序
9 桶排序
10 基数排序
本文为C++实现的十大排序算法及基于排序算法解决的一些常见问题，每一种算法均实际运行，确保正确无误。文中内容为自己的一些理解，如有错误，请大家指正。
0 概述
在十种排序算法中，前七种是比较类排序，后三种是非比较类排序，每种算法的最好、最坏、平均时间复杂度，空间复杂度以及稳定性如下表所示。稳定性是指排序前后相等的元素相对位置保持不变。
具体思路和代码均为升序排序。
前三种排序比较类似，都是将数组划分成已排序部分和未排序部分，因此有两层循环，一层循环划分已排序和未排序部分的边界，一层循环选择不同的方法依次对未排序的部分进行排序。
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;}//testint 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;}//testint 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;}//testint 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;}//testint 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;}
5 归并排序
归并排序（Merge Sort）是分治思想的一个典型应用，如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了（前后两部分也采用相同的方法排序，即将前后两部分分别再从中间分成两部分排序后合并，以此类推，直到数组不可再分）。因此，归并排序是一个先分再合的过程，用到的思想为分治，具体实现方式为递归。
下面的图解很清晰的说明了归并排序的原理。
现在弄清楚原理了，但还有一个问题没有解决：如何合并两个排好序的前后数组？答案很简单，双指针 + 临时数组。指针P1指向前面数组的首元素，指针P2指向后面数组的首元素，比较大小，将较小的元素放在临时数组helper中，然后将指向较小元素的指针后移，再次比较，将较小的元素放入临时数组。如此反复，直到前后两个数组中的某个指针到达边界，然后将未到达边界的数组剩余的元素放入临时数组尾部，合并完成。最后将合并好的元素拷贝到原数组。
具体代码如下：
#include <iostream>#include <vector>using namespace std;void mergeSort(vector<int> &vec, int left, int right);void merge(vector<int> &vec, int left, int mid, int right);void printVec(vector<int> vec);//testint main(){vector<int> test_vec = {1, 5, 2, 7, 23, 5, 9, 33, 44, 99, 55};printVec(test_vec);mergeSort(test_vec, 0, test_vec.size() - 1);printVec(test_vec); system("pause");return 0;}//归并排序，先分再合void mergeSort(vector<int> &vec, int left, int right){if (left >= right){return;}//int mid = left + (right - left) / 2;int mid = left + ((right - left) >> 1); mergeSort(vec, left, mid);mergeSort(vec, mid + 1, right);merge(vec, left, mid, right); //合并}//合并，双指针 + 临时数组void merge(vector<int> &vec, int left, int mid, int right){int n = right - left + 1;vector<int> helper(n, 0); //临时数组int i = 0;int p1 = left; //第一个指针int p2 = mid + 1; //第二个指针//在两个指针都没有越过边界的情况下，将两个数组中较小的数放入临时数组，并将指针后移while (p1 <= mid && p2 <= right){ helper[i++] = vec[p2] < vec[p1] ? vec[p2++] : vec[p1++];}//将未到达边界的数组的剩余元素拷贝到临时数组尾部while (p1 <= mid){helper[i++] = vec[p1++];}while (p2 <= right){helper[i++] = vec[p2++];}//将临时数组的元素拷贝到原数组for (int j = 0; j < n; j++){vec[left + j] = helper[j];}}//打印数组void printVec(vector<int> vec){for (auto c : vec){cout << c << " ";}cout << endl;}
6 堆排序
堆排序（Heap Sort）的思路步骤为（假设数组共有n个元素）：将待排序数组构造成一个大顶堆，此时，整个数组的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个大顶堆，这样会得到n个元素的次小值，再次交换堆顶元素和第n-1个元素，这样倒数后两个数为最大的两个数且有序。如此反复执行，便能得到一个有序数组了。
动态图解：
简化一下：①构建大顶堆 → ②交换元素 → ③重构大顶堆 → ④交换元素 → 循环③④ 步
具体代码如下：
#include <iostream>#include <vector>using namespace std;void heapSort(vector<int> &vec);void heapInsert(vector<int> &vec, int index);void heapify(vector<int> &vec, int index, int len);void print_vec(vector<int> vec);int main(){vector<int> test_vec = {3, 1, 4, 6, 2, 7, 5, 8, 2, 12};int len = test_vec.size();print_vec(test_vec);heapSort(test_vec);print_vec(test_vec);system("pause");return 0;}//堆排序void heapSort(vector<int> &vec){int len = vec.size();if (len <= 1){return;}//构建大顶堆for (int i = 0; i < len; i++){heapInsert(vec, i);}//交换堆顶元素和末尾元素swap(vec[0], vec[--len]);//循环，重构大顶堆，交换元素while (len > 0){heapify(vec, 0, len); swap(vec[0], vec[--len]);}}//index的父节点为(index - 1) / 2void heapInsert(vector<int> &vec, int index){while (vec[index] > vec[(index - 1) / 2]){swap(vec[index], vec[(index - 1) / 2]);index = (index - 1) / 2;}}//重构[index, len)的区间为大顶堆void heapify(vector<int> &vec, int index, int len){int leftson = index * 2 + 1; //index的左子节点，leftson + 1为右子节点while(leftson < len){int largest = (leftson + 1 < len && vec[leftson+ 1] > vec[leftson]) ? leftson + 1 : leftson;largest = vec[largest] > vec[index] ? largest : index;if (largest == index){break;}swap(vec[index], vec[largest]);index = largest;leftson = index * 2 + 1;}}//打印数组 void print_vec(vector<int> vec){for (auto c : vec){cout << c <<" ";}cout << endl;}
7 快速排序
快速排序（Quick Sort）也用到了分治思想，如果要排列下标从 left 到 right 的数组，我们可以选择从 left 到 right 之间的任意一个元素作为分区点q，然后遍历从 left 到 right 的元素，将小于等于分区点q的数放在左边，大于分区点q的数放在右边，将分区点q放在中间。然后使用相同的方法将小于等于分区点的数划分成三部分，将大于分区点q的数分成三部分。依次类推，直到数组不可再分，则整个数组实现有序。因此，快速排序用到的思想为分治，具体实现方式为递归。
动态图解（该图解是将最后一个数最为分区点，借助这个图也可以理解将随机选取的数作为分区点）：
与归并排序一样，理解了原理之后，还有一个问题没有解决：如何根据随机选取的数来分区（partition）？答案是借助指针来分界。我们设置两个指针，指针small为小于等于分区点q的数边界，指针P所指的数为待分区的数，初始指针位置如下图(1)所示。
将P与随机选取的数value比较，有两种结果：
（1） P <= value，则先将small指针后移一位，然后交换small与P的值，再将P后移一位，如下图(2)所示。
具体代码如下：
swap(vec[++small], vec[P++]);
（1） P >value，直接将P指针后移一位（P++）即可，如下图(3)所示；
完整代码如下：
#include <iostream>#include <vector>#include <ctime>using namespace std;void quickSort(vector<int> &vec, int l, int r);int partition(vector<int> &vec, int l, int r);void print_vec(vector<int> vec);int main(){vector<int> vec_test = {3, 2, 4, 1, 9, 6, 11, 8};print_vec(vec_test);quickSort(vec_test, 0, vec_test.size() - 1);print_vec(vec_test);system("pause");return 0;}void quickSort(vector<int> &vec, int l, int r){if (l >= r){return;}int i = partition(vec, l, r);quickSort(vec, l, i -1);quickSort(vec, i + 1, r);}int partition(vector<int> &vec, int l, int r){int small = l - 1;int p = l;//以下代码是为了获得介于[l, r]之间的随机数srand(time(0));int rand_num = l + rand() % (r - l);int value = vec[rand_num];while(p <= r){if (vec[p] <= value){swap(vec[++small], vec[p++]);}else{p++;}}return small;}void print_vec(vector<int> vec){for (auto i = vec.begin(); i != vec.end(); i++){cout << *i << " ";}cout << endl;}
接下来我们来看一个荷兰国旗问题：
给定一个数组vec，和一个数target，请把小于target的数放在数组的 左边，等于target的数放
在数组的中间，大于target的数放在数组的 右边。要求额外空间复杂度O(1)，时间复杂度
O(N)。
思路：将整个数组划为三个区域（小于target的部分，等于target的部分和大于target的部分），区域的边界用下标small和big进行区分，即下标（包含）small左侧的数都小于target，下标（包含）big右侧的数都大于target，p为未比较的数。未比较的数vec[p]与target相比有三种情况：
(1) vec[p] < target，将small的下标右移一位并与p所在位置的数进行交换，交换后p右移一位。
(2) vec[p] > target，将big的下标左移一位，并与i所在位置的数进行交换。
(3) vec[p] = target，将p右移一位。
具体代码：
#include <iostream>#include <vector>using namespace std;void netherlandFlag(vector<int> &vec, int left, int right, int target);void print_vec(vector<int> vec);//testint main(){vector<int> test_vec = {1, 9, 4, 10, 5, 33, 5,22, 11, 3, 4, 4, 5, -1};print_vec(test_vec);netherlandFlag(test_vec, 0, test_vec.size() - 1, 5);print_vec(test_vec);system("pause"); return 0;}//荷兰国旗问题void netherlandFlag(vector<int> &vec, int left, int right, int target){if (left >= right){return;}int small = left - 1;int big = right + 1;int p = left;while(p < big){if (vec[p] < target){swap(vec[++small], vec[p++]);}else if(vec[p] > target){swap(vec[--big], vec[p]);}else{p++;}}}//打印数组void print_vec(vector<int> vec){for(auto i = vec.begin(); i != vec.end(); i++){cout << *i << " ";}cout << endl;}
理解了荷兰国旗问题我们可以对快排进行改进。
我们依然选择从 left 到 right 之间的任意一个元素作为分区点q，然后遍历从left到right的元素，与之前不同的是，这次我们将数组分成小于，等于和大于三个部分，先后使用相同的方法对小于和大于部分分区，以此类推，直到不可再分。这样做的好处是，我们每次只用考虑小于和大于部分，而等于部分就不用再进行排序。
具体代码如下：
#include <iostream>#include <vector>#include <ctime>using namespace std;void quickSort(vector<int> &vec, int l, int r);void print_vec(vector<int> vec);//testint main(){vector<int> test_vec = {1, 9, 4, 10, 5, 33, 5,22, 11, 3, 4, 4, 5, -1};print_vec(test_vec);quickSort(test_vec, 0, test_vec.size() - 1);print_vec(test_vec);system("pause"); return 0;}//快速排序void quickSort(vector<int> &vec, int left, int right){if (left >= right){return;}int small = left - 1;int big = right + 1;int p = left;//以下代码是为了获得介于[l, p]之间的随机数srand(time(0));int rand_num = left + rand() % (right - left);//分区partitionint value = vec[rand_num];while (p < big){if (vec[p] < value){swap(vec[++small], vec[p++]);}else if(vec[p] > value){swap(vec[--big], vec[p]);}else{p++;}}//递归小于和大于value的部分quickSort(vec, left, small);quickSort(vec, big, right);}//打印数组void print_vec(vector<int> vec){for(auto i = vec.begin(); i != vec.end(); i++){cout << *i << " ";}cout << endl;}
8 计数排序
计数排序对于数据有较高要求，必须是有确定范围的整数。
算法实现：
1)查找数组的最大值，并根据最大值来创建计数数组countArr中元素的个数;
2) 统计原数组中各个元素出现的次数，countArr；
2) 清空原数组，并根据counArr并重新创建原数组。
动态图解：
代码：
#include <iostream>#include <algorithm>#include <vector>using namespace std;void countingSort0(vector<int> &vec){//注意max_element用来取最大值下标，*max_element用来取最大值int max_num = *max_element(vec.begin(), vec.end());//int min = *min_element(vec.begin(), vec.end());//创建计数数组vector<int> countArr(max_num + 1);for (auto c : vec){countArr[c]++;}//根据数组countArr重新构建vecvec.clear();for (int i = 0; i <= max_num; i++){while(countArr[i] != 0){vec.push_back(i);countArr[i]--;}}}//countingSort1函数使用累加数组void countingSort1(vector<int> &vec){int len = vec.size();int max_num = *max_element(vec.begin(), vec.end());vector<int> countArr(max_num + 1);for (auto c : vec){countArr[c]++;}for(int i = 1; i <= max_num; i++){countArr[i] += countArr[i - 1];}vector<int> helper(len);for (int j = 0; j < len; j++){helper[--countArr[vec[j]]] = vec[j];}vec.swap(helper);}void print_vec(vector<int> vec){for (auto c : vec){cout << c << " ";}cout << endl;}//testint main(){vector<int> test_vec = {1, 5, 2, 7, 3, 5};print_vec(test_vec);//countingSort0(test_vec);countingSort1(test_vec);print_vec(test_vec); system("pause");return 0;}
方法二所用累加数组图解：
9 桶排序
桶排序的思想很简单，先根据数据规模划分同的个数，尽量保证桶内数的个数均匀，然后分别对各个桶内的数据进行再次排序，排序方法可以是前面所说的，也可以递归。
算法实现：
1) 根据数据的规模划分桶的个数（count = (max - min) / n + 1)；
2) 依次将原数组中的数放到对应的桶中;
3) 依次对每一个桶进行排序，并将排好序的桶插入到原数组的末尾。
动态图解：
代码：
#include <iostream>#include <vector>#include <algorithm>using namespace std;void insertSort(vector<int> &vec);void bucketSort(vector<int> &vec);void printVec(vector<int> vec);//testint main(){vector<int> test_vec = {1, 5, 2, 7, 3, 5, 9, 33, 44, 99, 55};printVec(test_vec);bucketSort(test_vec);printVec(test_vec); system("pause");return 0;}//桶排序void bucketSort(vector<int> &vec){//划分桶的个数int len = vec.size();int maxNum = *max_element(vec.begin(), vec.end());int minNum = *min_element(vec.begin(), vec.end());int count = (maxNum - minNum) / len + 1;//初始化桶vector<vector<int>> bucket(count, vector<int>());//依次将数组vec中数放到对应的桶中for (int i = 0; i < len; i++){int k = (vec[i] - minNum) / len; //对用第K个桶bucket[k].push_back(vec[i]);}//对每一个桶内进行排序，并将排序好的桶依次插入到原vec数组的末尾vec.clear();for (int i = 0; i < count; i++){insertSort(bucket[i]); //本例使用插入排序vec.insert(vec.end(), bucket[i].begin(), bucket[i].end());}}//插入排序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] > temp){swap(vec[j+1], vec[j]);}}}}//打印数组void printVec(vector<int> vec){for (auto c : vec){cout << c << " ";}cout << endl;}
10 基数排序
先现根据个位数字决定每个数字进到哪个桶里，然后把桶从左往右所有的数字依次倒出来（先进先出）；再根据十位数组决定每个数字进到哪个桶里，然后从左往右依次把桶里的数字依次倒出来；依次类推，直到最高位。
算法实现：
1) 确定最大数的位数，最大数的位数即需要进桶出桶的次数；
2) 根据最低位到最高位依次排序（先最低位排序，再最高位排序）；
动态图解：
代码：
#include <iostream>#include <vector>#include <algorithm>using namespace std;void radixSort(vector<int> &vec){int len = vec.size();if (len <= 1){return;}//确定最大数的位数int maxNum = *max_element(vec.begin(), vec.end());int bigBit = 0;int base = 1;while(maxNum / base > 0){bigBit++;base *= 10;}//需要排序的次数=位数base = 1;for (int i = 0; i < bigBit; i++){//依次计算每个数最低位到最高位每个数出现的次数vector<int> bucket(10);for (int j = 0; j < len; j++){//根据base = 1, 10, 100...依次取个、十、百位数。bucket[(vec[j] / base) % 10] ++; }//使用累加数组for (int j = 1; j < 10; j++){bucket[j] += bucket[j - 1];}//根据累加数组，反向重建数组vector<int> temp(len);for (int j = len -1; j >= 0; j--){temp[--bucket[(vec[j] / base) % 10]] = vec[j];}temp.swap(vec);base *= 10;}}//打印数组void printVec(vector<int> vec){for (auto c : vec){cout << c << " ";}cout << endl;}//testint main(){vector<int> testVec = {1, 4, 2, 11, 77, 32, 123, 432, 888};printVec(testVec);radixSort(testVec);printVec(testVec);system("pause");return 0;}
C++实现十大排序算法（冒泡排序 选择排序 插入排序 希尔排序 归并排序 堆排序 快速排序 计数排序 桶排序和基数排序）
