快速排序-书上算法.cpp

快速排序的递归算法实现 效率要比选择法排序、冒泡法排序要高

// *******************************************
// * 程    序：6_6.cpp                                                   *
// * 作    者：wuwh                                                      *
// * 编制时间：2002年10月28日                                *
// * 主要功能：快速排序                                            *
// *******************************************
#include <iostream.h>		//预编译命令
void sort(int array[ ], int zz, int yy)	//被调用函数，数组array,zz,yy为形参
{                                         		//函数体开始
 int z,y,i,k;                          		//定义变量
 if ( zz<yy  )                            	//如果 zz < yy ,则做下列 7 件事:
 {                                      		// 7 件事开始
	z = zz; y = yy; k = array[ z ];     //第1件事
	do{                                   	//第2件事(开始)
          while(( z<y)&&(array[y]>=k)) y--;  //2.1,右边的元素>=k,让 y 往中间移
	  if( z < y )                         	//2.2,右边的元素<k,让
	  {                                 
              array[ z ] = array[ y ];       //array[ y ]送给 array[ z ]，
	       z = z+1;                       	//同时让 z 往中间移
	   }
	   while(( z< y) && (array[z] <= k)) z++;  //2.3,左边的元素<=k,让 z 往中间移
	   if ( z < y )			//2.4,左边的元素>k, 让 array[ z ]
		 array[ y ] = array [ z ];     //送给array[ y ]
        } while( z != y ) ;                       //第2件事(结束)
	array[ z ] = k;                           	//第3件事,k已排到位
	for(i = zz ;i <= yy ;i++)                  //第4件事，输出
	{ cout<<"a["<<i<<"]="<<array[i]<<"; ";}
	cout << endl;                          	//第5件事，换行
	sort( array, zz ,z-1 );                    	//第6件事，排左边部分
	sort( array ,z+1, yy);                    //第7件事，排右边部分
	}                                      		//7件事结束
}                                          		//函数体结束
void main()                         		//主函数开始
{                                                            
	int a[10],i;                      		//整型变量
	cout << "请输入10个整数\n";	//提示信息
	for (i = 0; i<10; i++)		//输入10个整数
		cin >> a[ i ];
	sort(a,0,9);		//调用sort函数,实参为数组a和0，9
	cout << "排序结果为:"; 	//提示信息
	for (i =0; i<10 ;i++ ) 
		cout << a[ i ] << ";";		//输出排序结果
	cout << endl;
}						//主函数结束