快速排序

题目

思路

1. 随便选择一个数列中的数，使整个数列中位置在它左边的数都小于它，使整个数列中位置在它右边的数都大于它。

2. 递归的对该数的左、右子数列进行上面的操作。

3. 递归到子数列中只能1个数后返回，此时该数列整体有序。

递归过程如图：

图中的X可以随便选，为了方便处理边界问题，这里选择每个子序列的中间位置的值。上图是递归的过程

下面是对每一个子序列X左右两边的值，进行交换的过程：

C++代码实现

#include
using namespace std;

const int N = 100010;
int p[N];

void quick_sort(int p[], int l, int r) {
    
    if (l >= r) return;
    
    int x = p[(l + r) >> 1];
    int i = l - 1;
    int j = r + 1;
    while (i < j) {
        do i++; while(p[i] < x);
        do j--; while(p[j] > x);
        if (i < j) swap(p[i], p[j]);
    }
    
    quick_sort(p, l, j), quick_sort(p, j + 1, r);
    
}

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) cin>>p[i];
    
    quick_sort(p, 0, n - 1);
    
    for (int i = 0; i < n; i++) cout<