前言
$\qquad$话说排序算法是数据结构的基础。但是随着时代的发展, 很多编程语言里排序也不过就是sort一下而已, 那为什么要花费很大力气去掌握排序算法呢。
$\qquad$其实每一个经典的排序算法能流传到现在都是有原因的。因为它们的经典之处不仅仅在于排序。更在于思想, 并且凭借着这种思想还可以帮助我们去做其他的一些题目。
1. 归并排序(衍生题目: 求逆序对的个数)
关于此算法的一些闲聊:
$\qquad$ 归并排序的思想是分治思想, 同时也是一种递归, 也就是说我们要先把左边的排好序, 右边的也排好序。最后再整个的一起排个序。
归并排序原代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 1E5+4;
int a[N];
int temp[N];
void mergeSort(int l, int r) {
if (l == r) return;
int mid = (l + r) / 2;
mergeSort(l, mid), mergeSort(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) temp[k++] = a[i++]; // 此处的等于号决定了算法是否稳定, 带上等于号是稳定的
else temp[k++] = a[j++];
}
while (i <= mid) temp[k++] = a[i++]; // 左边剩余的要补上
while (j <= r) temp[k++] = a[j++]; // 右边剩余的也要补上
for (int k = 0, i = l; i <= r; i++, k++) a[i] = temp[k]; // 把答案贴回来
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
mergeSort(0, n - 1);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}
衍生题目:求逆序对的个数解题思路:
$\qquad$在归并排序中, 若左半边的某一个值a
大于右半边的某一个值b
, 则相对于右半边的这个值b
来说, 左半边的这个值以及到mid
的所有值都与右半边的这个值b
构成逆序。
衍生题目:求逆序对的个数代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 4;
int a[N];
int temp[N];
long long int res = 0;
void findRe(int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
findRe(l, mid), findRe(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) temp[k++] = a[i++]; // 此处要为小于等于
else {
res += mid - i + 1; // 此处就是统计结果的地方
temp[k++] = a[j++];
}
}
while (i <= mid) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
for (int k = 0, i = l; i <= r; i++, k++) a[i] = temp[k];
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
findRe(0, n - 1);
printf("%lld\n", res);
return 0;
}
衍生题目(力扣2426): 满足不等式的数对数目代码如下:
class Solution {
public:
int temp[100005];
long long res = 0;
void mergeSort(vector<int>& nums, int low, int high, int diff) {
if (low == high) return;
int n = nums.size();
int mid = (low + high) >> 1;
mergeSort(nums, low, mid, diff), mergeSort(nums, mid + 1, high, diff);
// 这里用到了双指针算法
for (int l = mid, r = high; r >= mid + 1; r--) {
while (l >= low && nums[l] - nums[r] > diff) l--;
res += l - low + 1;
}
int l = low, r = mid + 1, k = 0;
while (l <= mid && r <= high) {
if (nums[l] <= nums[r]) temp[k++] = nums[l++];
else temp[k++] = nums[r++];
}
while (l <= mid) temp[k++] = nums[l++];
while (r <= high) temp[k++] = nums[r++];
for (int i = low, k = 0; i <= high; i++, k++) nums[i] = temp[k];
}
long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int diff) {
vector<int> nums;
for (int i = 0; i < nums1.size(); i++) nums.push_back(nums1[i] - nums2[i]);
mergeSort(nums, 0, nums1.size() - 1, diff);
return res;
}
};
2. 快速排序(衍生题目: 线性时间复杂度内找第k小的数、找前k小的数)
关于此算法的一些闲聊:
$\qquad$快速排序是一个非常经典的算法, 该算法也是用到了分治和递归的思想, 它的理念是先找一个枢轴量, 使得一轮过后, 枢轴量左边的数都不大于枢轴量, 枢轴量右边的数都不小于枢轴量。然后左右递归, 直到每个区间仅剩一个数。
$\qquad$利用快速排序的衍生算法找第 $k$ 小的数也叫 $bfprt$ 算法, 是找第$k$小的数的终极最优算法, 因为该算法的时间复杂度期望达到了$O(n)$的级别, 是由 $Blum 、 Floyd 、 Pratt 、 Rivest、Tarjan$ 五位巨擘共同创作的算法, 这里面的 $Pratt$ 就是 $KMP$ 算法里的那个$P$, 没错, 这是同一个人。这个算法相当经典,它的从无到有, 是当时5位大佬共同创作的结果。 尽管随着时间的推移, 它已经成为y总算法基础课里面的第一节课的内容(可以稍微感慨一下, 其实我们是在以最快的速度去学习当年智商最高的那一批人费力创作出来的东西, 一开始想不到, 或者说学的时候感觉有点困难也是正常的, 不然的话这些大佬也太没面子了哈哈)。
快速排序代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;
int a[N];
void quickSort(int a[], int low, int high) {
if (low >= high) return;
int l = low - 1, r = high + 1, x = a[l + r >> 1];
while (l < r) {
do l++; while(a[l] < x);
do r--; while(a[r] > x);
if (l < r) swap(a[l], a[r]);
}
quickSort(a, low, r);
quickSort(a, r + 1, high);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
quickSort(a, 0, n - 1);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}
衍生题目: 线性时间复杂度内找第k小的数解题思路:
$\qquad$在快排一轮结束的时候, 我们要看左半边的所有数字的数量与 $k$ 的关系。若大于 $k$, 就递归左半边, 否则递归右半边。
衍生题目: 线性时间复杂度内找第k小的数代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+3;
int a[N];
int findKmin(int low, int high, int k) {
if (low == high) return a[low]; // 如果区间就剩一个数字, 就返回该数字
int l = low - 1, r = high + 1, x = a[low];
while (l < r) {
while (a[++l] < x);
while (a[--r] > x);
if (l < r) swap(a[l], a[r]);
}
int sl = r - low + 1; // 统计左半边的数字数量, 若K小于的话sl的话, 就递归左半边, 否则递归右半边
if (k <= sl) return findKmin(low, r, k);
else return findKmin(r + 1, high, k - sl);
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
printf("%d", findKmin(0, n - 1, k));
return 0;
}
还没有完, 快速排序还有一个衍生题目就是找前k小的数。
衍生题目: 找前k小的数解题思路:
$\qquad$快速排序的写法, 这个写法我觉得应该就是和各种教科书上的写法最相似的了。比较容易理解。关键是找枢轴量的位置。并且枢轴量之前的数是小于枢轴量本身对应的数的。当枢轴量为k
时, 返回前k
个数(arr[0] - arr[k - 1])
即可, 该算法时间复杂度的期望也是$O(n)$
衍生题目: 找前k小的数代码如下:
class Solution {
public:
vector<int> res;
int quickSort(vector<int> &arr, int low, int high) {
int pivot = arr[low]; // 枢轴量
while (low < high) {
while (low < high && arr[high] >= pivot) high--;
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) low++;
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
vector<int> getLeastNumbers(vector<int>& arr, int k) {
int l = 0, r = arr.size() - 1;
while (l < r) {
int pivotPos = quickSort(arr, l, r); // 得到枢轴量位置
if (pivotPos < k) l = pivotPos + 1;
else if (pivotPos > k) r = pivotPos - 1;
else if (pivotPos == k) break; // 直到枢轴量位置为k, 把枢轴量之前的数装入答案即可。
}
for (int i = 0; i < k; i++) res.push_back(arr[i]);
return res;
}
};
3. 堆排序(衍生题目: 求前k小的数)
$\qquad$关于此算法的一些闲聊: 因为堆排序的时间复杂度为$O(nlog(n))$, 所以找前 $k$ 小这个题目比较适合用这个算法。当然用刚刚提到的快排思想去做也是一种好的选择。因为这个题目相比于堆排序本身只多了一行代码, 所以我把它们放到了一起。堆排序算法的实现需要我们比较好的理解关于树的顺序存储。并且节点编号是从1开始的。对于 $i$ 节点, 它的两个孩子节点下标编号是 $2i$ 和 $2i + 1$。
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int m, n, Size;
int a[N];
// 迭代建立大根堆, 并把堆顶元素移动到数组最后一位, 完成整个数组的排序
void adjustHeap(int k) {
for (int i = 2 * k; i <= Size; i *= 2) {
if (i < Size && a[i] < a[i + 1]) i = i + 1;
if (a[k] > a[i]) break; // 此处是a[0];
else {
swap(a[k], a[i]);
k = i;
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
Size = n;
for (int i = n / 2; i > 0; i--) adjustHeap(i);
while (Size > 1) {
swap(a[1], a[Size--]); // 让a[1]和a[i]交换
adjustHeap(1);
}
for (int i = 1; i <= m; i++) printf("%d ", a[i]);
return 0;
}
$\qquad$然后还没完, 在顺便讲一下关于二叉树的顺序存储, 力扣的第 662 题是让求二叉树的最大宽度。因为做题还不多, 这是我见过的仅有的一道用到了顺序存储思想的题目。
解题思路
$\qquad$ 二叉树层序遍历的变体, 注意本题需要无符号的长整型, 不然会溢出(怪恶心的)。这题顺便巩固了一下二叉树的顺序存储。$i$ 节点的两个孩子存的下标为 $2i$ 和 $2i + 1$。之前我一直在想要是做一些从下标1开始才比较方便处理的问题怎么搞(比如堆排序),因为力扣下标都是从0开始的。通过这个题, 学到了可以建立一个pair<TreeNode*, int>
的映射(本题是pair<TreeNode*, ull>
)。把根节点映射成1, 其他节点依次类推就行了。
$\qquad$ 本题在把节点装入队列的时候,会把下标index
也装进去。在用一个Index
装入每一层结点的下标。然后每一个for
循环结束时。就能得到每一层的宽度ull width = Index[Index.size() - 1] - Index[0] + 1;
。然后更新一下最大值即可。
代码如下:
class Solution {
public:
typedef unsigned long long ull;
int widthOfBinaryTree(TreeNode* root) {
ull maxWidth = 0;
queue<pair<TreeNode*, ull>> q;
q.push({root, 1}); // 先把根节点放进去, 顺序对应着树的顺序存储
while (!q.empty()) {
ull size = q.size();
vector<ull> Index; // 收集每一层的下标
for (int i = 0; i < size; i++) {
TreeNode* cur = q.front().first;
ull index = q.front().second;
Index.push_back(index);
q.pop();
// 在层序遍历的基础上加上每个节点在顺序存储时应得的下标。
if (cur -> left) q.push({cur -> left, 2 * index});
if (cur -> right) q.push({cur -> right, 2 * index + 1});
}
ull width = Index[Index.size() - 1] - Index[0] + 1;
maxWidth = max(maxWidth, width);
}
return maxWidth;
}
};
4. 冒泡排序(衍生题目: 力扣1460. 通过翻转子数组使两个数组相等)
关于此算法的一些闲聊:
$\qquad$冒泡排序应该是最经典最简单的一个排序算法了。它的思想其实也很经典,算是一个火出圈的算法了吧。这里在力扣上找了一个比较简单的衍生题目。
冒泡算法代码如下:
#include<bits/stdc++.h>
using namespace std;
void BubbleSort(int A[], int n){
int i, j;
for(i=0; i<n; i++){
int flag=0;
for(j=0; j<n-i-1; j++){
if(A[j] > A[j+1]){
swap(A[j], A[j+1]);
flag=1;
}
}
if(!flag) break;
}
}
int main(){
int A[1003]={0};
int n;
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d", &A[i]);
}
BubbleSort(A, n);
for(int i=0; i<n; i++){
printf("%d ", A[i]);
}
printf("\n");
return 0;
}
衍生题目: 通过翻转子数组使两个数组相等思路:
$\qquad$ 证明思路:其实翻转的过程, 就是可以看作冒泡的过程, 也就是说如果我们按照冒泡排序能把两个数组排成一样的, 那就说明符合要求。
衍生题目: 通过翻转子数组使两个数组相等代码:
class Solution {
public:
bool canBeEqual(vector<int>& target, vector<int>& arr) {
sort(target.begin(), target.end());
sort(arr.begin(), arr.end());
bool flag = true;
for (int i = 0; i < target.size(); i++) if (target[i] != arr[i]) flag = false;
if (flag) return true;
else return false;
}
};
5. 选择排序(衍生题目: 力扣670: 最大交换)
关于此算法的一些闲聊:
$\qquad$ 选择算法的思路也很简单,这个算法是最接近人直觉的一个算法, 也就是说它是最人性的一个算法。如果一个人没有任何算法基础。你让他排序大概率就是这个思想(像快排, 堆排序我觉得很少有人在学习数据结构之前就能想到这些算法), 就是不定的找数组中最小的元素然后交换。注意该算法是非稳定的算法, 在一趟选择,如果一个元素比当前元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。
选择算法代码如下:
#include<bits/stdc++.h>
using namespace std;
void SelectSort(int A[], int n){
int i, j;
for(i = 0; i < n - 1; i++){
int min = i;
for(j = i + 1; j < n; j++){
if(A[j] < A[min])
min = j;
}
if(min != i){
swap(A[i], A[min]);
}
}
}
int main(){
int A[1003] = {0};
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &A[i]);
}
SelectSort(A, n);
for(int i = 0; i < n; i++){
printf("%d ", A[i]);
}
printf("\n");
return 0;
}
衍生题目: 最大交换解题思路:
$\qquad$这个题目有点像选择排序。但是需要注意的就是这句if (nums[j] >= nums[temp] && nums[j] != nums[i]) temp = j;
前半部分的等号不能少, 因为我们需要的是一个尽可能大的、并且位置尽可能后面的数和前面的数交换。因此要加上等号。否则若后面有两个相同的数字的话, 找到的是第一个数字。比如样例 1993
, 不加等号的话, 结果是9193
(因为找到第一个9
, temp
就不会更新了)。而加上等号的话, 就会找到第二个9
, 答案变为9913
。
$\qquad$if
语句的后半部分nums[j] != nums[i]
也是必不可少的。因为有可能出现无效交换。比如数字98368
。不加nums[j] != nums[i]
的话, 就会是8
和8
交换。其实我们想要的是8
和3
交换。因此我们需要进入下一轮循环才行。即需要加上nums[j] != nums[i]
。不让temp
更新。
代码
衍生题目: 最大交换代码如下:
class Solution {
public:
int maximumSwap(int num) {
vector<int> nums;
while (num) {
nums.push_back(num % 10);
num /= 10;
}
reverse(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
int temp = i;
for (int j = i; j < nums.size(); j++) {
if (nums[j] >= nums[temp] && nums[j] != nums[i]) temp = j;
}
if (temp != i) {
swap(nums[temp], nums[i]);
break;
} else continue;
}
string s;
for (int i = 0; i < nums.size(); i++) s.push_back(nums[i] + '0');
int res = atoi(s.c_str());
return res;
}
};
6. 插入排序(暂无衍生题目)
关于此算法的一些闲聊:
$\qquad$这个算法虽然看起来简单, 但其实它并不简单, 至少对于初学者来说是要想那么一会的, 它并不像选择排序和冒泡排序那样符合人类的直觉。不过掌握之后就很简单了。
插入排序算法代码如下:
#include<bits/stdc++.h>
using namespace std;
void InsertSort(int a[], int n) {
int temp, j;
for (int i = 2; i <= n; i++) {
if (a[i] < a[i - 1]) {
temp = a[i];
for (j = i - 1; a[j] > temp; j--) a[j + 1] = a[j];
a[j + 1] = temp;
}
}
}
int main() {
int A[10005], n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
InsertSort(A, n);
for (int i = 1; i <= n; i++) printf("%d ", A[i]);
return 0;
}
7. 希尔排序(暂无衍生题目)
关于此算法的一些闲聊:
$\qquad$这个算法是对插入算法的改进, 但用的并不多, 并且时间复杂度是个谜。
希尔排序算法代码如下:
#include<bits/stdc++.h>
using namespace std;
void ShellSort(int A[], int n) {
int i, j, dk;
for (dk = n / 2; dk >= 1; dk /= 2) {
for (i = dk + 1; i <= n; i++) {
if (A[i] < A[i - dk]) {
int temp = A[i];
for (j = i - dk; j > 0 && A[j] > temp; j -= dk) A[j + dk] = A[j];
A[j + dk] = temp;
}
}
}
}
int main(){
int A[1003]={0};
int n;
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &A[i]);
}
ShellSort(A, n);
for(int i=1; i<=n; i++){
printf("%d ", A[i]);
}
printf("\n");
return 0;
}
8. 基数排序(暂无衍生题目)
关于此算法的一些闲聊:
$\qquad$这个算法并不是直接进行数字的比较, 而是按位比较。不断地入队出队, 直到把所有的位都比完。
基数排序代码如下(C代码)
#include<bits/stdc++.h>
using namespace std;
typedef struct LinkNode {
int data;
struct LinkNode *next;
}LinkNode, *LinkList;
typedef struct Queue{
LinkNode *front, *rear;
}Queue;
Queue Q[15];
// 初始化队列
void Inital(Queue Q[]) {
for (int i = 0; i < 10; i++) {
Q[i].front = Q[i].rear = (LinkNode *)malloc(sizeof(LinkNode));
Q[i].front -> next = NULL;
}
}
// 基数排序
void Sort(int A[], int n, int c, Queue Q[]) {
int v = 1;
// 把每一个数字都插入到对应的队列当中
for (int k = 1; k <= n; k++) {
int j = (A[k] / c) % 10; // 提取某一位的数字
LinkNode* p = (LinkNode *)malloc(sizeof(LinkNode));
p -> data = A[k];
p -> next = NULL;
Q[j].rear -> next = p;
Q[j].rear = p;
}
// 回收每根柱子(队列)上的数字
for (int i = 0; i < 10; i++) {
LinkNode *pre, *q = Q[i].front -> next;
while (q) {
int u = q -> data;
A[v++] = u;
pre = q;
q = q -> next;
free(pre);
}
}
for (int i = 0; i < 10; i++) {
Q[i].front -> next = NULL;
Q[i].rear = Q[i].front;
}
}
int main() {
int n, e, A[100003];
scanf("%d", &n);
int Max = -1e9;
for (int i = 1; i <= n; i++) {
scanf ("%d", &A[i]);
Max = max(Max, A[i]);
}
Inital(Q);
for (int c = 1; Max / c > 0; c *= 10) Sort(A, n, c, Q);
for (int i = 1; i <= n; i++) printf("%d ", A[i]);
return 0;
}
下面写出基数排序的C++代码, 用vector真的方便很多。
基数排序代码如下(C++代码)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
vector<int> bucket[10];
int main() {
int n;
scanf("%d", &n);
int Max = INT_MIN;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
Max = max(a[i], Max);
}
int cnt = 1;
while (cnt <= Max) {
for (int i = 0; i <= 9; i++) bucket[i].clear(); // 清空bucket
for (int i = 1; i <= n; i++) bucket[a[i] / cnt % 10].push_back(a[i]); // 把各种数字按位数整理
int k = 1;
for (int i = 0; i <= 9; i++) for (int j = 0; j < bucket[i].size(); j++) a[k++] = bucket[i][j];
cnt *= 10;
}
for (int i = 1; i <= n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
9. 计数排序(暂无衍生题目)
关于此算法的一些闲聊:
$\qquad$这个算法也比较符合人类直觉, 有哈希的思想在里面。用空间换时间把时间复杂度降到了$O(n)$的级别, 不过若是数值太大的话并不好。
计数排序代码如下(C代码)
#include<bits/stdc++.h>
using namespace std;
int main(){
int cnt[100003]={0}, n, num, Min = INT_MAX, Max = INT_MIN;
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &num);
cnt[num]++;
Min = min(Min, num), Max = max(Max, num);
}
for (int i = Min; i <= Max; i++) {
while (cnt[i]--) printf("%d ", i);
}
printf("\n");
return 0;
}
10. 桶排序(暂无衍生题目)
关于此算法的一些闲聊:
$\qquad$这个算法属于分治思想, 其实基数排序和计数排序都用了桶的思想。并且可以联想一下, 大数据里面的MapReduce也是分治的思想。就这个算法而言, 先把数据都分到每个桶里面。把每个桶内的元素进行排序, 然后再把数据都拿出来。
计数排序代码如下(C代码)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main() {
int n, Min = INT_MAX, Max = INT_MIN;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
Max = max(Max, a[i]), Min = min(Min, a[i]); // 收集数组中的最大最小值
}
int num = 10; // 桶中元素的个数, 为了不使桶中元素太多。先固定好桶中元素个数。
int m = (Max - Min) / num + 1; // 桶的个数
vector<vector<int> > bucket(m); // 初始化桶
for (int i = 1; i <= n; i++) bucket[(a[i] - Min) / num].push_back(a[i]); // 把元素放入桶中
for (int i = 0; i < m; i++) sort(bucket[i].begin(), bucket[i].end()); // 桶内排序
for (int i = 0, k = 1; i < m; i++) {
for (int j = 0; j < bucket[i].size(); j++) a[k++] = bucket[i][j]; // 取出桶中元素
}
for (int i = 1; i <= n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}