quicksort.cpp

快速排序算法及其改进算法

// QuickSort.cpp : Defines the entry point for the console application.
//
/*
描述: 中枢元素位置随机生成的快速排序算法
作者: xiaocui
时间: 2008.1.6
版本: v1.0
*/
/*
描述: 中枢元素位置随机生成的快速排序算法
作者: yujing
时间: 2008.4.11
版本: v2.0
*/
#include <iostream>
#include <ctime>
using namespace std;

/* 交换元素 */
template<typename T>
void mySwap(T& x, T& y)
{
T tmp = x;
x = y;
y = tmp;
}

/* 中枢元素位置为第一个元素的快速排序算法 */
template<typename T>
void quickSort(T array[], int startIndex, int endIndex)
{
  if (endIndex <= startIndex)
  {
	  return;
  }
  
  int i = startIndex;
  int j = endIndex;
  int PivotIndex = startIndex;
  int PivotKey = array[PivotIndex]; 
  
  while ( i < j )
  {
	  while ( (i < j) && (array[j] >= PivotKey) ) //此处j永远不会小于startIndex,j >= startIndex 是为了醒目统一
		  --j;
	  array[i] = array[j];
	  
	  while ( (i < j) && (array[i] <= PivotKey) )
		  ++i;
	  array[j] = array[i];
  }
  
  array[j] = PivotKey;
  PivotIndex = j;
  
  quickSort(array, startIndex, PivotIndex - 1);
  quickSort(array, PivotIndex + 1, endIndex); 
}

/* 中枢元素位置随机生成的快速排序算法 */
template<typename T>
void newQuickSort(T array[], int startIndex, int endIndex)
{
//递归出口
	if ( endIndex <= startIndex )
	{
		return;
	}
	
	int i = startIndex;
	int j = endIndex;
	int PivotIndex = startIndex + rand()%(endIndex - startIndex + 1);
	int PivotKey = array[PivotIndex];

	mySwap(array[startIndex], array[PivotIndex]);
		
	while ( i < j )
	{
		while ( (i < j) && (array[j] >= PivotKey) )
			--j;
		array[i] = array[j];
		
		while ( (i < j) && (array[i] <= PivotKey) )
			++i;
		array[j] = array[i];
	}
	
	array[j] = PivotKey;
	PivotIndex = j;
	newQuickSort(array, startIndex, PivotIndex - 1);
	newQuickSort(array, PivotIndex + 1, endIndex); 
}

/* 
找三者
array[startIndex]、array[endIndex]、array[(startIndex+endIndex)/2往下取整]
中值
*/
template<typename T>
int FindMidValue(T array[], int startIndex, int endIndex)
{
	int Midloc = (startIndex + endIndex)/2;
	int MidIndex;

	if (array[startIndex] >= array[Midloc]  )
	{
		if (array[Midloc] >= array[endIndex])
		{
			MidIndex = 	Midloc;
		}
		else if (array[startIndex] >= array[endIndex])
		{
			MidIndex = 	endIndex;
		}
		else
		{
            MidIndex = 	startIndex;
		}
	}
	else
	{
		if (array[Midloc] < array[endIndex])
		{
			MidIndex = 	Midloc;
		}
		else if (array[startIndex] < array[endIndex])
		{
			MidIndex = 	endIndex;
		}
		else
		{
            MidIndex = 	startIndex;
		}
		
	}

return MidIndex;
}
/* 
中枢元素取三者
array[startIndex]、array[endIndex]、array[(startIndex+endIndex)/2往下取整]
中值的快速排序算法
*/
template<typename T>
void MidQuickSort(T array[], int startIndex, int endIndex)
{
//递归出口
	if ( endIndex <= startIndex )
	{
		return;
	}
	
	int i = startIndex;
	int j = endIndex;
	int PivotIndex = FindMidValue(array,startIndex,endIndex);
	int PivotKey = array[PivotIndex]  ;

	mySwap(array[startIndex], array[PivotIndex]);
		
	while ( i < j )
	{
		while ( (i < j) && (array[j] >= PivotKey) )
			--j;
		array[i] = array[j];
		
		while ( (i < j) && (array[i] <= PivotKey) )
			++i;
		array[j] = array[i];
	}
	
	array[j] = PivotKey;
	PivotIndex = j;
	MidQuickSort(array, startIndex, PivotIndex - 1);
	MidQuickSort(array, PivotIndex + 1, endIndex); 
}

/* 输出 */
template<typename T>
void print(T array[], int n)
{
for (int i = 0; i < n; ++i)
{
   cout << array[i] << " ";
}
cout << endl;
}

int main()
{
//int iarray[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
//test int iarray[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
//test int iarray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//test 
	int iarray[10] = {9, 6, 10, 1, 8, 2, 3, 5, 4, 7};
cout << "未排序时: " << endl;
print(iarray, 10);

srand((unsigned)(time(NULL)));

//quickSort(iarray, 0, 9);
//newQuickSort(iarray, 0, 9);
MidQuickSort(iarray,0,9);
cout << "排序后: " << endl;
print(iarray, 10);

return 0;
}