题目描述

利用快速排序算法将读入的N个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++选手请不要试图使用STL，虽然你可以使用sort一遍过，但是你并没有掌握快速排序算法的精髓。）

输入输出格式

输入格式：

 

输入文件sort.in的第1行为一个正整数N，第2行包含N个空格隔开的正整数a[i]，为你需要进行排序的数，数据保证了A[i]不超过1000000000。

 

输出格式：

 

输出文件sort.out将给定的N个数从小到大输出，数之间空格隔开，行末换行且无空格。

 

输入输出样例

输入样例#1： 

54 2 4 5 1

输出样例#1： 

1 2 4 4 5

说明

对于20%的数据，有N≤1000；

对于100%的数据，有N≤100000。

【代码】：

std::ios::sync_with_stdio(false);

std::cin.tie(0);//cin优化

#include
      
       using namespace std;int a[100000];//因为输入数的最大值为十万。void qsort(int left,int right)//从哪里开始搜索，又搜索到哪里{    if(left==right)return;//如果互相等于就结束    int mid=a[(left+right)/2];//取中间的值    int i=left;//i代替左边    int j=right;//j代替右边    while(i<=j)//i从左边开始找    {        while(a[i]
       
        mid)j--;//大的        if(i<=j)//要写！在这个循环结束之前我们无法判断        {            int tmp=a[i];            a[i]=a[j];            a[j]=tmp;            i++;j--;}//交换    }    if(left
        
         >n;//个数    for(int i=0;i
         
          >a[i];//输入    qsort(0,n-1);//循环，是从零开始循环的    for(int i=0;i
          
           <
           
            <<" ";//输出 cout<
           
          
         
        
       
      

#include 
      
       using namespace std;int main(){    multiset
       
        sort;//新建一个红黑树    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++)    {            int a;            cin>>a;            sort.insert(a);//将数据插入红黑树    }    set
        
         ::iterator it;    for(it=sort.begin();it!=sort.end();it++)    cout << *it<<' ';//遍历输出红黑树，即排序结果    cout<< endl;    return 0;}