归并排序

#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;
}