随机快排.cpp

来自「acm中各种代码」· C++ 代码 · 共 44 行

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

void RandQuickSort(int *arr,int begin,int end) 
{ 
        int m,k; 
        int a=begin,b=end; 
        if(a>=b) return; 
        k=begin+rand()%(end-begin); 
        m=arr[k]; 
       arr[k]=arr[begin]; 
        arr[begin]=m; 
        while(a<b) 
        { 
               while(a<b && m<=arr[b]) b--; 
               if(a<b) { arr[a]=arr[b]; a++;} 
               while(a<b && m>=arr[a]) a++; 
               if(a<b) { arr[b]=arr[a]; b--;} 
        } 
        arr[a]=m; 
        RandQuickSort(arr,begin,a-1); 
        RandQuickSort(arr,a+1,end); 
}
int main() 
{ 
        int a[11]; 
       int i; 
       int c;
       while(scanf("%d",&c) != EOF)
        {
                            for(i=0;i<9;i++) 
               scanf("%d",&a[i]); 
        srand((unsigned)time(NULL)); 
        RandQuickSort(a,0,8); 
        for(i=0;i<9;i++) 
               printf("%d ",a[i]); 
        putchar('\n');
        } 
        return 0; 
}