codeup 快速排序 qsort

题目描述
输入n个整数，用快速排序的方法进行排序

Input

第一行数字n 代表接下来有n个整数
接下来n行，每行一个整数

Output

Output

升序输出排序结果
每行一个数据

Sample Input

5
12
18
14
13
16
Sample Output

12
13
14
16
18
Hint

n<=5000
每个数据<=5000

#include<iostream>
#include<time.h>
using namespace std;

int number[5005];

int Partition(int A[], int left, int right) {
	int p = rand() % (right - left) + left;
	swap(A[left], A[p]);
	int temp = A[left];//保存A[left]的值
	while (left < right) {
		while (left<right&&A[right]>temp)
			right--;
		A[left] = A[right];//把right从右向左扫描遇到的第一个小于A[temp]的值放到A[left]的位置
		while (left < right&&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 = Partition(A, left, right);
		quickSort(A, left, pos-1);
		quickSort(A, pos + 1, right);
	}
}

int main() {
	int n, index;
	srand((unsigned)time(NULL));
	while (scanf_s("%d", &n) != EOF) {
		for (int i = 0;i < n;i++) {
			scanf_s("%d", &number[i]);
		}
		quickSort(number, 0, n - 1);
		for (int i = 0;i < n;i++)
			printf("%d\n", number[i]);
	}
	return 0;
}