快速排序

题目描述

给定你一个长度为$n$的整数数列。

请你对这个数列按照从小到大进行排序并输出。

输入格式

输入共两行，第一行包含整数$n$，第二行包含$n$个整数表示整个数列。

输出格式

输出一行排好序的数列。

解答

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e7 + 10;

int n, q[N];

// Q_sort函数实现快速排序，参数为数组q、排序开始位置l和结束位置r
void Q_sort(int q[], int l, int r) {
    if (l >= r) return; // 如果开始位置大于等于结束位置，则不进行排序
    
    // 快排模板
    int x = q[l + (r - l) / 2], i = l - 1, j = r + 1; // 选择中间位置的值作为基准值x，初始化左右指针i和j
    while (i < j) { // 当左指针小于右指针时进行循环
        do i++; while (q[i] < x); // 左指针右移，直到找到一个大于等于x的值
        do j--; while (q[j] > x); // 右指针左移，直到找到一个小于等于x的值
        if (i < j) swap(q[i], q[j]); // 如果左指针仍然小于右指针，则交换两个指针所指的值
    }
    // 递归调用Q_sort函数，对基准值左右的两部分分别进行排序
    Q_sort(q, l, j);
    Q_sort(q, j + 1, r);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    Q_sort(q, 0, n - 1); // 调用Q_sort函数进行快速排序
    for (int i = 0; i < n; i++) printf("%d ", q[i]);
    return 0;
}