Introduction
本篇是对十大排序的总结，会涉及每个排序的重要步骤、时间复杂度、空间复杂度、稳定性、代码实现
Summary
| 排序算法 | 最差时间复杂度 | 空间复杂度 | 平均时间复杂度 | 数据对象稳定性 |
|---|---|---|---|---|
| 冒泡排序 | \(O(n^2)\) | \(O(1)\) | \(O(n^2)\) | 稳定 |
| 插入排序 | \(O(n^2)\) | \(O(1)\) | \(O(n^2)\) | 稳定 |
| 选择排序 | \(O(n^2)\) | \(O(1)\) | \(O(n^2)\) | 数组不稳定，链接稳定 |
| 希尔排序 | \(O(n^2)\) | \(O(1)\) | \(O(nlog_2n)\) | 不稳定 |
| 归并排序 | \(O(nlog_2n)\) | \(O(n)\) | \(O(nlog_2n)\) | 稳定 |
| 快速排序 | \(O(n^2)\) | \(O(log_2n)\) | \(O(nlog_2n)\) | 不稳定 |
| 桶排序 | \(O(n)\) | \(O(m)\) | \(O(n)\) | 稳定 |
| 基数排序 | \(O(n^2)\) | \(O(r)\).r为基数 | \(O(kn)\) | 稳定 |
| 计数排序 | \(O(n+m)\) | \(O(n+m)\) | \(O(n+m)\) | 稳定 |
| 堆排序 | \(O(nlog_2n)\) | \(O(1)\) | \(O(nlog_2n)\) | 不稳定 |
不稳定：快速排序，选择排序，希尔排序，堆排序(简称，快选希堆)
非原地：归并、计数、桶、基数
冒泡排序(Bubble)
-
思想：比较交换相邻元素
-
主要步骤
- 比较相邻元素.若第一个比第二大，则交换
- 对每一对相邻元素进行同样的工作，会使得最后一个元素的值是最大的
- 针对所有元素重复以上步骤，除开最后一个元素
-
动态图
-
实现
输入输出描述如下：
#include <iostream> #include <vector> using namespace std; int main() { int temp; vector<int> target{20,413,3,53,90,324}; for(int i = 0; i < target.size() - 1; ++i) { for(int j = 0; j < target.size() - i - 1; ++j) { if(target[j] > target[j+1]) swap(target[j], target[j+1]); } } for(auto const& n : target) { cout << n << ',' <<' '; } return 0; }
选择排序(Select)
-
思想：找最小元素，放到目标位置
-
适用：数据量少
-
主要步骤
- 在未排序的序列中寻找最小(大)元素，放在序列的起始位置
- 从剩余未排序的序列中继续重复上述操作，直到所有元素排序完毕
-
动态图
-
实现
输入输出描述：
#include <iostream> #include <vector> using namespace std; void select(vector<int>&); int main() { int nums; cin >> nums; vector<int> vec(nums); //输入目标序列 for(int i = 0; i < nums; ++i) { cin >> vec[i]; } //快排 select(vec); for(const auto& n : vec) cout << n << ' '; return 0; } void select(vector<int>& vec) { for(uint i = 0; i < vec.size() - 1; i++) { int minIndex = i; //最小值索引 for(uint j = i + 1; j < vec.size(); j++) { if(vec[j] < vec[minIndex]) minIndex = j; } //交换 int temp = vec[i]; vec[i] = vec[minIndex]; vec[minIndex] = temp; } }
插入排序(Insert)
-
思想：与抓牌类似，插入牌中适合位置
-
适用：基本有序
-
主要步骤
- 从第一个元素开始，将第一个元素视为已经排序后的序列
- 取出下一个元素，并在已排序的序列中从后向前扫描
- 若已排序的元素大于新元素，则该元素向后移动一位
- 重复步骤三，直至找到合适位置(小于等于新元素)，将新元素插入该位置
- 重复步骤2-4
-
动态图
-
实现
输入输出描述：
#include <iostream> #include <vector> using namespace std; class Insert { public: void MySort(vector<int>& nums) { for(uint i = 1; i < nums.size(); ++i) { if(nums[i] < nums[i-1]) { int j = i - 1; int tar = nums[i]; //待排序元素 //nums[i] = nums[i-1]; //后移一个元素 while(j >= 0 && tar < nums[j]) { nums[j+1] = nums[j]; j--; } nums[j+1] = tar; } } } }; int main() { int _size; cin >> _size; vector<int> target(_size, 0); for(int i = 0; i < _size; ++i) { cin >> target[i]; } Insert insert; insert.MySort(target); for(const auto& n : target) { cout << n << " "; } return 0; }
希尔排序(Shell)
希尔排序是更高效的插入排序
-
思想：间隔分组+自定义排序
-
适用：数据量大
-
主要步骤
- 将整个待排序列分割为多个子序列
- 按照增量分别进行插入排序
- 再依次缩减增量进行插入排序
-
动态图
-
实现
#include <iostream> #include <vector> using namespace std; class Shell { public: void MySort(vector<int>& nums) { int s = nums.size(); int gap = s / 2; //增量 while (gap > 0) { for (int i = gap; i < s; ++i) { int j = i; while (j >= gap && nums[j] < nums[j - gap]) { swap(nums[j], nums[j - gap]); j -= gap; } } //缩减增量 gap /= 2; } } }; int main() { vector<int> vec{ 9, 7, 5, 3, 1, 0, 8, 4, 6, 2 }; Shell shell; shell.MySort(vec); for (const auto& n : vec) { cout << n << " "; } return 0; }
归并排序(Merge)
-
思想：分治(递归)
-
适用：不受数据影响，所需空间和n成正比
-
主要步骤
- 将长度为n的待排序序列分成两个长度为n/2的子序列
- 对这两个子序列采用归并排序
- 将两个排序后的子序列合并为最终的序列
-
动态图
-
实现
#include <iostream> #include <vector> using namespace std; class Merge { public: void MySort(vector<int>& nums, int l, int r) { if (l < r) { int mid = l + ((r - l) >> 1); MySort(nums, l, mid); MySort(nums,mid + 1, r); MergeSort(nums, l, r); } } void MergeSort(vector<int>& nums, int l, int r) { vector<int> temp(nums.size()); int mid = l + ((r - l) >> 1); int p = l; int q = mid + 1; int k = l; while (p <= mid && q <= r) { if (nums[p] < nums[q]) { temp[k++] = nums[p++]; //若右边元素大于左边元素，跳过 } else { temp[k++] = nums[q++]; //若右边元素小于等于左边元素，将右边元素赋值给左边 } } //赋值余下元素 while(p <= mid) temp[k++] = nums[p++]; while (q <= r) temp[k++] = nums[q++]; for (int i = l; i <= r; ++i) { nums[i] = temp[i]; } } }; int main() { vector<int> vec{ 9, 7, 5, 3, 1, 0, 8, 4, 6, 2 }; Merge merge; merge.MySort(vec, 0 , vec.size() - 1); for (const auto& n : vec) { cout << n << " "; } return 0; }
快速排序(Quick)
-
思想：选择中轴元素，小于它的放左边，大于它的放右边，重复直至各区间只剩一个数
-
适用：广泛(最快)
-
主要步骤
- 以未排序序列中的第一个元素作为基准元素
- 两个哨兵，一个在最左边，一个在最右边。右边的向左移动，一旦找到小于基准的数则停止，左边的向右移动，一旦找到大于基准的数停止，交换他们
- 重复步骤2，直至右哨兵的索引 == 左哨兵的索引
- 交换基准元素和左哨兵
- 以左哨兵为基准划分左右两边界，分别再进行快排
-
动态图
-
实现
#include <iostream> #include <vector> using namespace std; class Qucik { public: void MySort(vector<int>& nums, int start, int end) { if (start >= end) return; //判断区间是否只剩一个元素 int l = start; int r = end; int temp = nums[l]; //基准元素 while (l < r) { //最右边的先动 //找小于基准的 while (l < r && nums[r] >= temp) { r--; } //找大于基准的 while (l < r && nums[l] <= temp) { l++; } //交换符合条件的两个数 if (r > l) { swap(nums[l], nums[r]); } } swap(nums[l], nums[start]); //l == r 处赋予基准值，再进行分治,如此使得左边的数都小于基准值，右边的数都大于基准值 //以基准值为分界点 MySort(nums, start, l - 1); MySort(nums, l + 1, end); } }; int main() { vector<int> vec{ 9, 7, 5, 3, 1, 0, 8, 4, 6, 2 }; Qucik qucik; qucik.MySort(vec, 0 , vec.size() - 1); for (const auto& n : vec) { cout << n << " "; } return 0; }
计数排序(Count)
-
思想：利用数组下标确定元素的正确位置
-
适用：max和min的差值不大,待排序序列中所有数均为整数
-
主要步骤：
- 找出待排序序列中最大和最小的元素
- 统计序列中每个值为i的元素出现的次数，存入计数数组c的第i项
- 对所有计数累加
- 将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减一
-
动态图
-
实现
#include <iostream> #include <vector> #include <algorithm> using namespace std; class Count { public: void MySort(vector<int>& target, vector<int>& temp) { //保证待排序序列非空 if (target.size() == 0) return; //使用target容器中的最大值+1作为计数容器的大小 int vecCountLen = (*max_element(target.begin(), target.end())) + 1; vector<int> vecCount(vecCountLen, 0); //计数容器 //统计每个键值出现的次数 for (int i = 0; i < target.size(); ++i) { vecCount[target[i]]++; } //后面的键值出现的位置是前面所有键值出现的次数之和 for (int i = 1; i < vecCountLen; ++i) { vecCount[i] += vecCount[i - 1]; } //将键值放于目标位置.也就是从中取出键值，每取一个，对应计数器减1，直到所有计数器为0，使得目标序列排序完毕 for (int i = target.size(); i > 0; --i) { temp[--vecCount[target[i - 1]]] = target[i - 1]; } } }; int main() { vector<int> vec{ 9, 7, 5, 3, 1, 0, 8, 4, 6, 2 }; vector<int> temp(vec.size(), 0); Count count; count.MySort(vec, temp); for (const auto& n : temp) { cout << n << " "; } return 0; }
桶排序(Bucket)
-
思想：将值为i的元素放入i号桶，最后依次把桶里的元素倒出来
-
适用：均匀分布的数据
-
主要步骤：
- 设置一个定量的数组作为空桶
- 从序列中把项目一一放进对应的桶中
- 对每个不是空的桶子排序
- 从桶中把项目放回原来的序列
-
动态图
-
实现
#include <iostream> #include <vector> #include <list> #include <algorithm> using namespace std; class Bucket { public: void MySort(vector<int>& target) { //初始化桶 vector<list<int>> buckets(target.size()); //将数据放入桶中并进行排序 for (const auto& n : target) { int index = GetBucketIndex(n); InsertSort(buckets[index], n); } //排序后，从桶中取数据，放入原数组 int i = 0; for (const auto& bucket : buckets) { for (const auto& b : bucket) { target[i++] = b; } } } //获得桶的序号 int GetBucketIndex(int num) { return num / 3; } //使用插入排序将数据放入对应桶中 void InsertSort(list<int>& bucket, int n) { bool flag = true; for (auto it = bucket.begin(); it != bucket.end(); ++it) { //小于目标值，插入当前位置 if (n <= *it) { bucket.insert(it, n); flag = false; break; } } if (flag) bucket.emplace_back(n); } }; int main() { vector<int> vec{ 9, 7, 5, 3, 1, 0, 8, 4, 6, 2 }; Bucket bucket; bucket.MySort(vec); for (const auto& n : vec) { cout << n << " "; } return 0; }
基数排序(Radix)
-
思想：是桶排序的一种, 按数位分桶
-
适用：min和max的差值不大
-
主要步骤
- 取得数组中的max及其位数
- 从最低位开始取每个位组成radix数组
- 对radix进行计数排序
-
动态图
-
实现
#include <iostream> #include <vector> #include <list> #include <algorithm> using namespace std; class Radix { public: void MySort(vector<int>& target, int d) { int p = 1; vector<vector<int>> buckets(10, vector<int>(target.size())); vector<int> order(10); while (p < d) { //分桶 for (const auto& n : target) { int index = n / p % 10; //获得桶号 buckets[index][order[index]] = n; //将n放入第index号桶的order[index] order[index]++; //放入的位置++ } //排序 int k = 0; for (int i = 0; i < 10; ++i) { if (order[i] == 0) continue; //当前位置没有放入 for (int j = 0; j < order[i]; ++j) { target[k++] = buckets[i][j]; } order[i] = 0; //当前位置计算完后清零 } p *= 10; } } }; int main() { vector<int> vec{ 9, 7, 5, 3, 1, 0, 8, 4, 6, 2 }; Radix radix; radix.MySort(vec, 10); for (const auto& n : vec) { cout << n << " "; } return 0; }
堆排序
推荐这个讲解【算法】排序算法之堆排序 - 知乎 (zhihu.com)或是参见STL
-
思想：利用堆进行排序
-
主要步骤
- 将未排序序列构建为大顶堆
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成
-
实现
#include <iostream> #include <vector> #include <list> #include <algorithm> using namespace std; class Heap { public: void MySort(vector<int>& target) { int s = target.size(); //构造初始堆,自底向上 //从第一个非叶子节点(倒数第二行的最后一个)开始调整 //左右子节点中较大的和父节点交换 for (auto i = s / 2 - 1; i >= 0; --i) { HeadAdjust(target, s, i); } /* 排序 1.交换nums[0](nums[0]为最大值)和nums[i] 2.再次构建大顶堆 */ for (int i = s - 1; i > 0; --i) { swap(target[i], target[0]); //再次构建 HeadAdjust(target, i, 0); } } //调整堆 //len是nums的长度,i是当前三个节点中的根节点 void HeadAdjust(vector<int>& nums, int len, int i) { int index = 2 * i + 1; //将较小值下沉，较大值上位 while (index < len) { //index 指向子节点中较大的 if (index + 1 < len) { if (nums[index + 1] > nums[index]) { index = index + 1; } } //较大子节点和根节点进行比较 if (nums[index] > nums[i]) { //交换 swap(nums[index], nums[i]); //更新 i = index; index = 2 * i + 1; } else { break; } } } }; int main() { vector<int> vec{ 9, 7, 5, 3, 1, 0, 8, 4, 6, 2 }; Heap heap; heap.MySort(vec); for (const auto& n : vec) { cout << n << " "; } return 0; }