排序2，接上一篇

例2.3  明明的随机数(Noip2006)
【问题描述】
    明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
【输入文件】
    输入文件random.in 有2行，
    第1行为1个正整数，表示所生成的随机数的个数：N
    第2行有N个用空格隔开的正整数，为所产生的随机数。
【输出文件】
    输出文件random.out 也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
【输入样例】
    10
    20 40 32 67 40 20 89 300 400 15
【输出样例】
    8
    15 20 32 40 67 89 300 400
【分析】
    本题有一个重要的特点就是每一个数都介于0到1000之间的整数,可以开设一个下标为0～1000的数组b，b[0]记录值为0的个数,b[1]记录值为1的个数，……，b[x]记录值为x的个数，那么从小到大的顺序输出b数组值不为0的b数组下标值。

程序如下：

#include<iostream>
 #include<cstdio>
 #include<cstring>
 using namespace std;
 int main()
 {
    int b[1001],n,i,j,m=0,x;
    memset(b,0,sizeof(b));        //初始化
    cin>>n;
    for (i=1;i<=n;i++) 
    {
       cin>>x;
       if (b[x]==0)  m++;            //b[x]为0表示x为新的随机数,m加1
          b[x]++;                          //将等于x的值全部装入第x桶中
    }
    cout<<m<<endl;                 //不相同的随机数的个数
    for (i=0;i<=1000;i++)           //输出排序结果
      if (b[i]>0) cout<<i<<" ";
    cout<<endl;  
    return 0;
 }

5.快速排序

       快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

       假设待排序的序列为{a[L],a[L+1],a[L+2],……,a[R]}，首先任意选取一个记录（通常可选中间一个记作为枢轴或支点），然后重新排列其余记录，将所有关键字小于它的记录都放在左子序列中，所有关键字大于它的记录都放在右子序列中。由此可以将该“支点”记录所在的位置mid作分界线，将序列分割成两个子序列和。这个过程称作一趟快速排序（或一次划分）。

        一趟快速排序的具体做法是：附设两个指针i和j，它们的初值分别为L和R，设枢轴记录取mid，则首先从j所指位置起向前搜索找到第一个关键字小于的mid的记录，然后从i所指位置起向后搜索，找到第一个关键字大于mid的记录，将它们互相交换，重复这两步直至i>j为止。

       快速排序的时间的复杂性是O(nlog2n)，速度快,但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法

       由以上讨论可知，从时间上看，快速排序的平均性能优于前面讨论过的各种排序方法，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为log(n+1

快速排序算法

void qsort(int l,int r)
{  
    int i,j,mid,p;
    i=l;  j=r; 
    mid=a[(l+r) / 2];            //将当前序列在中间位置的数定义为分隔数
    do
    {
       while (a[i]<mid) i++;  //在左半部分寻找比中间数大的数
       while (a[j]>mid) j--;    //在右半部分寻找比中间数小的数
       if (i<=j) 
        {                                //若找到一组与排序目标不一致的数对则交换它们
            p=a[i];
            a[i]=a[j];
            a[j]=p;
            i++;   j--;                //继续找
        }
    }
    while (i<=j);                  //注意这里不能有等号
    if (l<j)  qsort(l,j);           //若未到两个数的边界，则递归搜索左右区间
    if (i<r)  qsort(i,r);
}