排序算法模板——归并，快排【C++】

embedded/2025/2/26 17:21:42/

前言

二者都是分治思想的体现，区别是归并是以整个数组的mid（下标的中间值）来分，分别将左右两个区间排好序，再合并；而快排是以数组中的一个数来划分，将小于等于这个数的放在该数左边，大于的放在右边。

ps.下面的代码中，归并排序使用传统int数组，快排使用vector数组，其实都是可以的，不过需要注意的是传统数组直接传数组名就相当于传地址了，但是vector数组需要使用引用&，否则是复制一个新数组作为参数；

归并排序

#include <iostream>
using namespace std;
int N;void mergeSort(int q[], int l, int r) {if(l >= r) return;int mid = (l + r) >> 1;mergeSort(q, l, mid);mergeSort(q, mid + 1, r);int temp[N];int k = 0, i = l, j = mid + 1;while(i <= mid && j <= r) {if(q[i] <= q[j]) temp[k++] = q[i++];else temp[k++] = q[j++];}while(i <= mid) temp[k++] = q[i++];while(j <= r) temp[k++] = q[j++];for(int i = l, j = 0; i <= r; i++, j++) {q[i] = temp[j]; }
}int main () {cin >> N;int q[N];for(int i = 0; i < N; i++) {cin >> q[i];}mergeSort(q, 0, N - 1);for(int i = 0; i < N; i++) {cout << q[i] << ' ';}
}

归并：先递归后合并；稳定；O(nlogn)

快速排序

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;void quicksort(vector<int> &q, int l, int r) {if(l >= r) return;int x = q[(l + r) >> 1],i = l - 1, j = r + 1;while(i < j) {do i++; while(q[i] < x);do j--; while(q[j] > x);if(i < j) swap(q[i], q[j]);}quicksort(q, l, i);quicksort(q, i + 1, r);
}int main () {int n;cin >> n;vector<int>q(n);for(int i = 0; i < n; i++) {cin >> q[i];}quicksort(q, 0, n - 1);for(int i = 0; i < n; i++) {cout << q[i] << ' ';}
}