无交换的quicksort

2008-10-02 11:39


#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int partition(int array[],int i,int j);
void qs(int array[],int i,int j);
int main(void){
    int n,i,arr[100];
   
    cin>>n;
    srand(time(NULL));
    for(i=0;i<n;i++) arr[i] = rand();;
   
    qs(arr,0,n-1);
   
    for(i=0;i<n;i++) cout<<arr[i]<<"\t";
    getchar();getchar();
   
    return 0;
}
int partition(int array[],int i,int j){
    int k = array[i];
   
    do{
        while((i<j)&&array[j]>=k) j--;
        if(i<j){ array[i] = array[j]; i++;}
       
        while((i<j)&&array[i]<=k) i++;
        if(i<j){ array[j] = array[i]; j--;}
    }while(i!=j);
    array[i] = k;
   
    return i;
}
void qs(int array[],int i,int j){
     if(i>=j) return;
     int m = partition(array,i,j);
     qs(array,i,m-1);
     qs(array,m+1,j);
 }