quicksort.cpp

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include <iostream.h>                  //快速排序

const int N=8;
void output(int table[],int n);        //输出数组的n个元素,略

void quicksort(int table[],int left,int right)  //实现一趟快速排序
{ 
    int i,j,vot;
    if(left<right)                     //左边界小于右边界，序列有效
    {
        i=left;
        j=right;
        vot=table[i];                  //第一个值作为基准值
        while(i!=j)                    //进行一轮比较
        {
            while(vot<table[j] && i<j)
                j--;                   //从右向左寻找较小值
            if(i<j)
            {
                table[i]=table[j];     //较小值元素向左移动
                i++;
            }     
            while(table[i]<vot && i<j)
                i++;                   //从左向右寻找较大值
            if(i<j)
            {
                table[j]=table[i];     //较大值元素向右移动
                j--;
            }     
        }
        table[i]=vot;                  //基准值的最终位置
        i++;
        j--;
        cout<<left<<"~"<<right<<"  vot="<<vot<<"  ";
        output(table,N);
        quicksort(table,left,j);       //左边子序列再排序
        quicksort(table,i,right);      //右边子序列再排序
    }
}

void main()
{
    int a[N]={5,6,2,4,8,3,1,7};
    cout<<"N="<<N;
    output(a,N);
    quicksort(a,0,N-1);
}
/*程序运行结果 ：
N=8  table: 5 6 2 4 8 3 1 7 
0~7  vot=5    table: 1 3 2 4 5 8 6 7 
0~3  vot=1    table: 1 3 2 4 5 8 6 7 
1~3  vot=3    table: 1 2 3 4 5 8 6 7 
5~7  vot=8    table: 1 2 3 4 5 7 6 8 
5~6  vot=7    table: 1 2 3 4 5 6 7 8 
*/

void output(int table[],int n)         //输出数组的n个元素
{
    cout<<"  table: ";
    for(int i=0;i<n;i++)
        cout<<table[i]<<" ";
    cout<<"\n";
}