归并排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 20;
int n, a[N], b[N];
// 合并单序列
void merge(int l, int r) {
int mid = (l + r) / 2;
int i = l;
int j = mid + 1;
int cnt = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
b[cnt] = a[i];
cnt++;
i++;
} else {
b[cnt] = a[j];
cnt++;
j++;
}
}
while (i <= mid) {
b[cnt] = a[i];
cnt++;
i++;
}
while (j <= r) {
b[cnt] = a[j];
cnt++;
j++;
}
for (int i = l; i <= r; i++) {
a[i] = b[i];
}
}
void mergeSort(int l, int r) {
if (l == r) {
return;
}
// 分
int mid = (l + r) / 2;
mergeSort(l, mid);
mergeSort(mid + 1, r);
// 合
merge(l, r);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
mergeSort(1, n);
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}
快速排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 560;
int n, a[N], b[N], c[N], d[N];
int randint(int l, int r) { // 生成一个随机数
return rand() % (r - l) + l + 1;
}
void quickSort(int l, int r) {
if (l >= r) {
return;
}
int k = randint(l, r);
int index1 = 0;
int index2 = 0;
int index3 = 0;
for (int i = l; i <= r; i++) { // 分割a数组
if (a[i] < a[k]) {
b[index1++] = a[i];
} else if (a[i] == a[k]) {
c[index2++] = a[i];
} else {
d[index3++] = a[i];
}
}
for (int i = 0; i < index1; i++) { // 放入a 数组
a[l + i] = b[i];
}
for (int i = 0; i < index2; i++) {
a[l + i + index1] = c[i];
}
for (int i = 0; i < index3; i++) {
a[l + i + index1 + index2] = d[i];
}
quickSort(l, l + index1 - 1); // 左
quickSort(l + index1 + index2, r); // 右
}
int main() {
srand(time(0));
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
quickSort(0, n - 1);
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
return 0;
}
计数排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 50;
int n, a[N], mx;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a[x]++;
mx = max(mx, x);
}
for (int i = 0; i <= mx; i++) {
while (a[i]--) {
cout << i << " ";
}
}
return 0;
}