一，知识点
这题考察了快排的实现，我之前写过一篇博客总结了八大排序☞《详解八大排序》
二， 题目(简单）
给定你一个长度为 n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n个整数（所有整数均在 1∼109范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
三，思路
总体思路：选定一个key，然后把比key小的放到key左边，比key大的放在key的右边
怎么选key?
为了防止恰是逆序的情况，我们可以在数组中随机取值，或者在第一个元素、最中间一个元素、最后一个元素中选择中间值。
当然还有其他的方式，但是只要可以减小碰到极端情况的概率即可。在这里我是直接取中间一个元素作key。
怎么把比key小的放在左边，大的放在右边呢？
有几种方式可以看我在开头说的那篇文章里有介绍，这里所说的是其中一种：定义两个指针，指针一从左至右找到比key大的就停下，指针二从右至左找到比key小的就停下，然后交换两个元素，直至两个指针相遇，这样到最后我们就确定了key的位置。
递归
四，AC代码
#include<iostream> using namespace std; int nums[1000010]; void quiksort(int nums[],int left,int right) { if(left>=right)return; int index=nums[(left+right)/2]; int l=left-1,r=right+1; while(l<r) { do l++;while(index>nums[l]); do r--;while(index<nums[r]); if(l<r)swap(nums[l],nums[r]); } quiksort(nums,left,r); quiksort(nums,r+1,right); } int main() { int n; scanf("%d", &n); for(int i=0;i<n;++i) { scanf("%d",&nums[i]); } quiksort(nums,0,n-1); for(int j=0;j<n;++j) { printf("%d ",nums[j]); } return 0; }
五，小结
这题属于难者不会、会者不难，主要考察了快速排序的实现，没有其他的运用，所以属于简单题。
