q_sort.cpp

快速排序C++源码

#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include <time.h>
#include <conio.h>
#include <stdlib.h> 

#define N 1000

int array[N+1];

void interchange(int &x,int &y);
int partition(int m,int p);
void quicksort(int p,int q);

void interchange(int &x,int &y)
{
    int elem;
    elem=y;
    y=x;
    x=elem;
}

int partition(int m,int p)
{
    int i,v;
    v=array[m];
    i=m;
    do{
        do{
            i=i+1;
        }while(array[i]<v);

        do{
            p=p-1;
        }while(array[p]>v);

        if(i>=p)  // if ">=" has been change to ">" ,this program is  
            break;
        else interchange(array[i],array[p]);//exit(0);
        }while(1);

    array[m]=array[p];

    array[p]=v;
    return p;
}
void quicksort(int p,int q)
{   
    if(p<q)
    {
        int j;    
        j=q+1;
        j=partition(p,j);

        quicksort(p,j-1);

        quicksort(j+1,q);
    }
}

void main(void)
{
    int n=N;
    int i;
    time_t start,finish;
    ofstream Table;
    for(i=0;i<n;i++)
        array[i]=(int)((rand()/32768.0)*(100000000));
         array[n]=99999999;
    cout<<"排序前:"<<endl;
    for(i=0;i<n;i++)
         {
             cout.fill('0');
             Table.fill('0');
                cout<<setw(8)<<array[i]<<" ";
                Table<<setw(8)<<array[i]<<" ";
           if((i+11)%10==0)
            cout<<endl;
        }

    //cout<<endl;
    time(&start);
     cout<<endl<<"排序前时间为:"<<start<<endl;
    quicksort(0,N-1);
    time(&finish);
    
    Table.open("e:\\result.doc");
    if(!Table.is_open())
              Table<<"open file failed!"<<endl;
    else{
       cout<<"排序后:"<<endl;
         for(i=0;i<n;i++)
         {
             cout.fill('0');
             Table.fill('0');
             cout<<setw(8)<<array[i]<<" ";
             Table<<setw(8)<<array[i]<<" ";
           if((i+11)%10==0)
            cout<<endl;
         }
    cout<<endl<<"排序完毕时间为:"<<finish<<endl;
    cout<<"排序时间为"<<difftime(start,finish)<<endl;
    }
    Table.close();
cout<<endl;

getch();
}