排序--快速排序

快速排序的话，说先要要用一个随机的函数rand（），解决好时间复杂度在最坏的情况下出现的o（n^2）的问题。

思想： 选择第i个数（由随机函数生成），如果后面的元素比这个元素小，i++，交还a【i】与a【j】；

然后分别递归，选择随机数的左边和右边。

#include<cstdio>
#include<iostream>
#include<stdlib.h>
using namespace std;
int a[10];
int p,q;
void swaps(int s,int b)
{
    int temp;
    temp=s;
    s=b;
    b=temp;
}
int pari(int a[],int p,int q)   //选择排序
{
    int x=a[p];
    int i=p;
    int j,temp;
    for(j=p+1;j<=q;j++){
        if(a[j]<=x){
            i++;
            temp=a[j];a[j]=a[i];a[i]=temp;
        }
    }
    temp=a[p];a[p]=a[i];a[i]=temp;
    return i;
}

int randomized(int p,int q)  //产生随机数
{
    int i=rand()%6;
    swaps(i,p);
    return pari(a,p,q);
}

void qSort(int a[],int p,int q)
{
    if(p<q)
    {
        int m=randomized(p,q);
        qSort(a,p,m-1);  //数组的左边
        qSort(a,m+1,q);  //数组的右边
    }
}

int main()
{
    for(int i=0;i<5;i++) scanf("%d",&a[i]);
    qSort(a,0,4);
    for(int i=0;i<5;i++) printf("%d ",a[i]);
    printf("
");
}