快速排序基本思想：
1. 选任意值与首元素交换（王道基础课没讲）
2. 进行逐个对比，先right--，后来left++
3. 结束的标志是left==right，因此所有的判断都是left<right

 

/*
-------------------------------------------------
   Author:       wry
   date:         2022/3/2 10:21
   Description:  QuickSort
-------------------------------------------------
*/

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000+10;
int arr[MAXN];

int Getlocation(int left,int right) {
    int random = left + rand()%(right-left+1);     //0 1 2 3 ,则除以4，余数为0，1，2，3
    swap(arr[random],arr[left]);
    while (left < right) {     //当left==right时候，就left就是最终位置
        while (left<right && arr[left]<arr[right]) {    //第一轮时空位在left，则在一切顺利下，right--
            right--;
        }
        swap(arr[left],arr[right]);
        while (left<right && arr[left]<arr[right]) {
            left++;
        }
        swap(arr[left],arr[right]);
    }
    return left;
}

void MergeSort(int left,int right) {
    if (left<right) {
        int position = Getlocation(left,right);
        MergeSort(left,position-1);
        MergeSort(position+1,right);
    }
}

int main() {
    int n;
    while (cin>>n) {
        for (int i=0;i<n;i++) {
            cin >> arr[i];
        }
        MergeSort(0,n-1);
        for (int i=0;i<n;i++) {
            cout << arr[i] << " ";
        }
    }
    return 0;
}