十大排序算法
复杂度和稳定性一览
排序算法 |
平均时间 |
最好时间 |
最坏时间 |
空间 |
稳定性 |
冒泡排序 |
|
|
|
|
稳定 |
选择排序 |
|
|
|
|
不稳定 |
插入排序 |
|
|
|
|
稳定 |
希尔排序 |
|
|
|
|
不稳定 |
归并排序 |
|
|
|
|
稳定 |
快速排序 |
|
|
|
|
不稳定 |
堆排序 |
|
|
|
|
不稳定 |
计数排序 |
|
|
|
|
稳定 |
1、冒泡排序
思路
比较相邻元素，将大的数往后移，这样一次操作就将大的数移到了后面。
时间复杂度分析： O(n^2)
稳定排序
void bubble_sort(vector<int> &q) { for(int i = q.size() - 1; i > 0; i--) //排序数据摆放位置 for(int j = 0; j + 1 <= i; j++) if(q[j] > q[j+1]) swap(q[j], q[j + 1]); //前面的数比后面的数大，将数往后移 }
优化操作，设置一个flag,一次遍历后如果数据都没发生移动，则可以停止。
for(int i = q.size() - 1; i > 0; i--) { bool flag = true; for(int j = 0;j + 1 <= i; j++) { if(q[j] > q[j + 1]) { swap(q[j], q[j + 1]); flag = false; } } if(flag) break; }
2、选择排序
思路
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
时间复杂度分析： O(n^2)
不稳定排序
void select_sort(vector<int> &q) { for(int i = 0; i + 1 < q.size(); i++) { int idx = i; for(int j = i + 1; j < q.size(); j++) //得到最小元素 if(q[j] < q[idx]) idx = j; if(idx != i) swap(q[i], q[idx]); } }
3、插入排序
思路
从后往前找，如果当前的数大于我们要插入的数，就将当前的数往后移一位。
时间复杂度分析：
（1）最坏的时间复杂度为O(n^2)，就是所有的数都是倒序排列，每插入一个数都有移动全部的数
（2）最好的情况是O(N)，所有的数都是从小到大排列，不需要移动数组。
稳定排序
void insert_sort(vector<int> &q) { for(int i = 1;i < q.size(); i++) { int t = q[i], j; for(j = i-1;j >= 0; j--) { if(q[j] > t) swap(q[j], q[j+1]); else break; } q[j + 1] = t; } }
4、希尔排序
void shell_sort() { for (int gap = n >> 1; gap; gap >>= 1) { for (int i = gap; i < n; i ++ ) { int x = a[i]; int j; for (j = i; j >= gap && a[j-gap] > x; j -= gap) a[j] = a[j-gap]; a[j] = x; } } }
5、归并排序
思路
归并排序是建立在归并操作上的一种有效的排序算法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
时间复杂度分析： O(nlogn）
空间复杂度分析： O(n)
void merge_sort(vector<int>& nums, int l, int r){ if(l >= r) return ; int mid = (l + r ) / 2; merge_sort(nums, l, mid),merge_sort(nums, mid + 1, r); int i = l, j = mid + 1; vector<int> tmp; while(i <= mid && j <= r){ if(nums[i] <= nums[j]) tmp.push_back(nums[i++]); else tmp.push_back(nums[j++]); } while(i <= mid) tmp.push_back(nums[i++]); while(j <= r) tmp.push_back(nums[j++]); int k = l; for(int x : tmp) nums[k++] = x; }
#include<iostream> #include<cstdio> #include<string> #include<vector> using namespace std; vector<int> nums(1e5 + 10); void merge_sort(vector<int>& nums, int l, int r){ if(l >= r) return ; int mid = (l + r ) / 2; merge_sort(nums, l, mid),merge_sort(nums, mid + 1, r); int i = l, j = mid + 1; vector<int> tmp; while(i <= mid && j <= r){ if(nums[i] <= nums[j]) tmp.push_back(nums[i++]); else tmp.push_back(nums[j++]); } while(i <= mid) tmp.push_back(nums[i++]); while(j <= r) tmp.push_back(nums[j++]); int k = l; for(int x : tmp) nums[k++] = x; } int main() { int n; cin>>n; for(int i = 0; i < n; i++){ cin>>nums[i]; } merge_sort(nums, 0, n - 1); for(int i = 0; i < n; i++){ cout<<nums[i]<<" "; } return 0; }
6、快速排序
思路
快速排序的核心思想是分治，从整个数列中随机挑一个基准数，将数列中大于这个数放到右边，小于这个数的放到左边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。其中设置两个指针i，j(i从左边，j从右边)从两端开始，i遇到大于等于x的停下来，j遇到小于等于x的停下来，然后如果(i)就交换q[i]，q[j]，之后结束循环，递归排序两个子序列。
时间复杂度分析：平均情况下时间复杂度为 O(nlogn)，空间复杂度为 O(logn)。最坏情况为数组已排好序或者数组中的数都相等，此时每次划分只会将数组的长度减少1，那每次分区得到的两个子区间都是不均等的，会递归 n 次，导致时间复杂度为O(n^2)。
空间复杂度分析： O(n）
不稳定排序
void quick_sort(vector<int>& nums,int l,int r) { if(l >= r) return ; int i = l - 1,j = r + 1,x = nums[(l+r)/2]; while(i < j) { do i++; while(nums[i] < x); do j--; while(nums[j] > x); if(i < j) swap(nums[i],nums[j]); } quick_sort(nums,l,j); quick_sort(nums,j+1,r); }
7、堆排序
思路
对于一棵二叉树，若树中的任意一个节点的权值都小于等于其父节点的权值,则称该二叉树满足"大根堆性质"。若树中任意一个节点的权值都大于等于其父节点的权值,则称该二叉树满足"小根堆性质"。
满足"大根堆性质"的完全二叉树就是"大根堆"，而满足"小根堆性质"的二叉树就是"小根堆",二者都是二叉堆的形态之一。
存贮
考虑用数组来存贮二叉树，假设父节点编号为x，那么x的左儿子为：2x，x的右儿子为2x + 1。
down(x)操作
将x节点下沉，每次将x和x的左右儿子的最小值进行交换。
如何建堆？
for (int i = n / 2; i; i--){ // 时间复杂度为O(n) down(i); }
i为什么从n/2开始down？
首先要明确要进行down操作时必须满足左儿子和右儿子已经是个堆。
开始创建堆的时候，元素是随机插入的，所以不能从根节点开始down，因为此时的根节点还不满足堆的性质，而是要找到满足下面三个性质的结点：
- 左右儿子满足堆的性质（叶节点一定满足堆的性质）。
- 不是叶结点。
- 下标最大（因为要往上遍历）。
如何进行堆排序？
我们只需要两个操作：
- 得到heap[1]堆顶；
- 将堆顶删除。
时间复杂度分析：O(nlogn)
C++完整代码
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N = 1e5 + 10; int h[N], cnt; void down(int u) { int t = u; if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1; if (u != t) { swap(h[u], h[t]); down(t); } } int main() { int n, m; cin>>n>>m; for(int i = 1; i <= n; i++) cin>>h[i]; cnt = n; for(int i = n / 2; i >= 1; i--) down(i); //建堆 while(m--) { cout<<h[1]<<" "; h[1] = h[cnt--]; down(1); } return 0; }
时间复杂度分析： O(nlogn)
空间复杂度分析： O(1)
8、计数排序
思想
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
c++完整代码
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e8 + 10; long long n, cnt[MAXN]; int main() { scanf("%lld", &n); int x = 0, Max = -0x3f3f3f, Min = 0x3f3f3f; //初始化最大值和最小值 for (int i = 1; i <= n; i ++) { scanf("%d", &x); cnt[x]++; //统计 Max = max(Max, x); Min = min(Min, x); //更新最大值和最小值 } for (int i = Min;i <= Max; i++) while(cnt[i]) cnt[i]--, printf("%d ", i); //输出 return 0; }
9、 什么是稳定排序？
一个算法是否稳定，根据排序前后相同数的相对位置是否发生变化来判断。相对位置变化的称为不稳定排序，不变化的称为稳定排序。
稳定排序分为以下四类：
- 冒泡排序
- 插入排序
- 归并排序
- 计数排序
不稳定的排序：
- 选择排序
- 堆排序
- 快速排序
- 希尔排序
