🌰快排 

晴问算法 

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
using namespace std;
const int MAXN = 1000;
int A[MAXN];
//对区间[left, rigth]随机选择一个基准元素划分并返回所在位置,它右边的元素都大于它，左边都小于它
int randPatition(int* A, int left, int right){//生成【left, right]内的随机数p作为基准索引，防止随机数大于RAND_MAX报错，取整：int p = round(1.0*rand() / RAND_MAX * (right-left) )+ left; //交换A[left]和A[p]，让随机选择的基准元素放在第一个位置swap(A[left], A[p]);//暂存基准元素，此时A[left]可视作为空，可放入新元素 <--- 因为基准必须暂存（暂存后该位置即可放入新元素），又初始的A【left]必须可放入新元素（即不丢失原元素），因此要交换元素让基准放到第一个位置A[left].int pivot = A[left];while(left < right){//当left == right，再把基准元素放入即完成//此时left可放入新元素，所以先从right往回遍历while(left < right && A[right] > pivot)right --;//直到A[right]<=base就把该元素放入A[left],那么A[right]也可视为空了，就从left往后遍历A[left] = A[right];while(left < right && A[left] <= pivot)//要等于，因为初始的A[left]是基准元素left ++;A[right] = A[left];}//把基准元素放入相遇处：A[left] = pivot;return left;//返回此时的基准元素位置。
}
//对区间[left, right]快排：
void quickSort(int* A, int left, int right){//base case:只有一个元素或者空if(left >= right)return ;//将[left, right]区间一分为二,并获取基准的索引；int pivotIdx = randPatition(A, left, right);//对基准元素左子区间进行快排quickSort(A, left, pivotIdx-1);//对基准元素右子区间进行快排quickSort(A, pivotIdx+1, right);
}
int main(){//在main函数开头加上该语句生成随机数种子srand((unsigned)time(NULL));int n;cin >> n;for(int i = 0; i < n; i++)cin >> A[i];quickSort(A, 0, n-1);for(int i = 0; i  < n; i++)printf( i == n-1 ? "%d\n" : "%d ", A[i]);return 0;
}