quicksort.cpp

四种排序算法的比较

// QuickSort.cpp: implementation of the QuickSort class.
//
//////////////////////////////////////////////////////////////////////

#include "QuickSort.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

QuickSort::QuickSort()
{

}

QuickSort::~QuickSort()
{

}

void QuickSort::quickSort(int left, int right) 
{ 
	int i,j; 
	int middle, iTemp; 
	i = left; 
	j = right; 

	middle = QuickSort::data[(left+right) / 2]; //求中间值 
	do 
	{ 
		while ((QuickSort::data[i] < middle) && (i < right)) //从左扫描大于中值的数 
			i++; 
		while ((QuickSort::data[j] > middle) && (j > left)) //从右扫描小于中值的数 
			j--; 
		if (i <= j) //找到了一对值 
		{ 
			//交换 
			iTemp = QuickSort::data[i]; 
			QuickSort::data[i] = QuickSort::data[j]; 
			QuickSort::data[j] = iTemp; 
			i++; 
			j--; 
		} 
	} while (i <= j) ; //如果两边扫描的下标交错，就停止（完成一次） 

	//当左边部分有值(left<j)，递归左半边 
	if(left<j) 
		quickSort (left,j);

	//当右边部分有值(right>i)，递归右半边 
	if(right>i) 
		quickSort (i,right);


}

void QuickSort::Init(int n)
{
	data=new int[n];
	Count=n;
	cout<<"Please input the data:"<<endl;
	for(int i=0;i<n;i++)
		cin>>data[i];
} 
void QuickSort::Show()
{
	cout<<"The result is:"<<endl;
	for(int i=0;i<QuickSort::Count;i++)
		cout<<data[i]<<"  ";
}