quicksort.cpp

一个好用的快速排序算法

//快速排序
#include <iostream>
using namespace std;

void QuickSort( float* pData, int* pIndex, int left, int right)
{
	int i, j;
	float middle, fTemp;
	int iTemp;
	i = left;
	j = right;
	middle = pData[(left+right)/2]; //求中间值

	do{
		while( ( pData[i]<middle ) && ( i<right ) )//从左扫描大于中值的数
			i++; 
		while( ( pData[j]>middle ) && ( j>left ) )//从右扫描大于中值的数
			j--;
		if( i<=j )	//找到了一对值
		{
			//交换元素
			fTemp = pData[i];
			pData[i] = pData[j];
			pData[j] = fTemp;

			//交换索引
			iTemp = pIndex[i];
			pIndex[i] = pIndex[j];
			pIndex[j] = iTemp;

			i++;
			j--;
		}
	} while( i <= j );//如果两边扫描的下标交错，就停止（完成一次）

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

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

// void QuickSort(int* pData, int* pIndex,  int Count)
//  {
// 	 run( pData, pIndex, 0, Count-1 );
// }

void main()
{
	float data[] = {10,9,8,7,6,5,4,23, 54, 563, 86, 1, 564, 643, 6, 978, 90};
	int index[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};

	QuickSort( data, index, 0, 16 );
	for ( int i = 0; i < 17; i++)
		cout << data[i] << " ";
	cout << endl;
	for ( int i = 0; i < 17; i++)
		cout << index[i] << " ";
	cout << endl;
}