PAT练习 快速排序 qsort [2*]
Description
输入n个整数，用快速排序的方法进行排序
Input
第一行数字n 代表接下来有n个整数
接下来n行，每行一个整数
Output
升序输出排序结果
每行一个数据
Sample Input
5 12 18 14 13 16
Sample Output
12 13 14 16 18
Hint
n<=5000
每个数据<=5000
c++实现
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;const int maxn=5001;int randPartition(int A[],int left,int right){int p=round(1.0*rand()/RAND_MAX*(right-left)+left);swap(A[p],A[left]);int temp=A[left];while(right>left){while(right>left && A[right]>temp){right--;}A[left]=A[right];while(right>left && A[left]<=temp){left++;}A[right]=A[left];}A[left]=temp;return left;
}void quickSort(int A[],int left,int right){if(left<right){int pos=randPartition(A, left, right);quickSort(A,left,pos-1);quickSort(A,pos+1,right);}
}int main(){int n;int A[maxn];scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&A[i]);}quickSort(A, 0, n-1);for(int i=0;i<n;i++){printf("%d\n",A[i]);}
}