快速排序

模板

#include <iostream>

using namespace std;

int n;
const int N = 1e6 + 10;
int q[N];

void quick_sort(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]);
	}
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &q[i]);
	quick_sort(q, 0, n - 1);
	for (int i = 0; i < n; i++) printf("%d ", q[i]);
	return 0;
}

考研版王道写法

#include <iostream>

using namespace std;

int n;
const int N = 1e6 + 10;
int nums[N];

int partition(int nums[], int low, int high) {
    int x = nums[low];
    while(low < high) {
        while(low < high && nums[high] >= x) --high;
        nums[low] = nums[high]; // 比枢轴小的元素移动到左端
        while(low < high && nums[low] <= x) ++low;
        nums[high] = nums[low]; // 比枢轴大的元素移动到右端
    }
    nums[low] = x; // 枢轴元素存放到最终位置
    return low;
}

void quick_sort(int nums[], int low, int high) {
    if(low < high) {
        int pivotpos = partition(nums, low, high); // 划分
        quick_sort(nums, low, pivotpos - 1);
        quick_sort(nums, pivotpos + 1, high);
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &nums[i]);
    quick_sort(nums, 0, n - 1);
    for(int i = 0; i < n; i++) printf("%d ", nums[i]);
    return 0;
}