排序小结

1.快速排序（手写）

#include <bits/stdc++.h>
using namespace std;
int n, a[100005]; 
void quick_sort(int left, int right, int a[]) {
	if (left >= right) return ;
	int x = a[(left + right) / 2];
	int i = left, j = right;
	while (i <= j) {
		while (a[i] < x) ++i;
		while (a[j] > x) --j;
		if (i <= j) swap(a[i++], a[j--]);
	}
	quick_sort(left, j, a);
	quick_sort(i, right, a);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", a + i);
	quick_sort(1, n, a);
	for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
	return 0;
}

2.快速排序（sort）
大家都会
3.归并排序

#include <bits/stdc++.h>
using namespace std;
int n, a[100005], tmp[100005];
void merge_sort(int a[], int left, int right) {
    if (left >= right) return ;
    int mid = left + right >> 1;
    merge_sort(a, left, mid), merge_sort(a, mid + 1, right);
    int tt = 0, i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (a[i] < a[j]) tmp[++tt] = a[i++];
        else tmp[++tt] = a[j++];
    }
    while (i <= mid) tmp[++tt] = a[i++];
    while (j <= right) tmp[++tt] = a[j++];
    for (int i = left, t = 1; i <= right; ++i, ++t) a[i] = tmp[t];
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    merge_sort(a, 1, n);
    for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
    return 0;
}

4.基数排序
时间复杂度为O(n)

#include <bits/stdc++.h>
using namespace std;
int n, a[100010], b[100010], num[100010];
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		++num[a[i] % 100000];
	}
	for(int i = 1; i < 100000; ++i) num[i] += num[i - 1];
	for (int i = n; i; --i) b[num[a[i] % 100000]--] = a[i];
	
	memset(num, 0, sizeof num);
	for (int i = 1; i <= n; ++i) ++num[b[i] / 100000];
	for (int i = 1; i <= 10000; ++i) num[i] += num[i - 1];
	for (int i = n; i; --i) a[num[b[i] / 100000]--] = b[i];
	for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
	return 0;
}

5.桶排序
大家都会

排序小结

原文：https://www.cnblogs.com/cyyhhyyc/p/14826224.html