8大ソートアルゴリズム(2)高速ソートの最適化

最も大きな話のデータ構造を見ています.本文の中の最適化内容は基本的にこの本の総括である.コードが少し違うかもしれません.
高速ソートは21世紀の古典的な10大アルゴリズムの一つである.中枢要素を選択し、シーケンス内で中枢位置を一意に決定する方法、すなわち、前のものが中枢値より小さく、後ろのものが中枢値より大きいことを考えます.これにより、並べ替えられるシーケンスを半分に分割します.もちろんこれが一番いい場合、この時の効果が一番いいです.以下3つの側面から最適化する.
最適化されていないソートは次のとおりです.

void quicksort(int a[],int first,int last)
{
	if(first<last)
	{
		 int i=first,j=last; 
		 int tmp=a[first];
		 while( i<j )
		 {
			 while(i<j && a[j]>=tmp)
			 --j;		// find the first index j that a[j] < tmp from right to left
			 if(i<j)
				 a[i++]=a[j];		// cover the a[i]. 
			 while( i<j && a[i]<tmp)
				 i++;			//find the first index i that a[i]>tmp from left to right
			 if(i<j)
				 a[j--]=a[i];		//cover the a[j] 
		 }
		if(i==j)
			a[i]=tmp;
		quicksort(a,first,i-1);
		quicksort(a,i+1,last);
	}
}

欠点:
1.中枢値は、毎回シーケンスの先頭要素として選択されます.可能な限り中間値であることは保証できません.
2.データの並べ替えの場合、小さいデータの場合、直接挿入を使用した並べ替えの方が効果的かもしれません.
3.クイックソートは2つの再帰呼び出しを使用しており、さらに最適化することはできません.
最適化は3つの側面から行います.
1.中枢値を選択します.ここではランダムな方法を採用することができますが、ランダムなシーケンス自体を生成するのに時間がかかり、効果が悪い可能性があります.確率の観点から、ヘッド、中、尾の3つの値を選択します.次に中間値をとります.中枢値としては、効果的です.

/***********************************************************************
QuickSort optimized
1. optimize base value
2. optimize sort scale n 
3. optimize the way of recusion (tail recursion)
***********************************************************************/
#include <iostream>
#include <ctime>
using namespace std;
void Swap(int &x,int &y)
{
	int tmp=x;
	x=y;
	y=x;
}
//Unoptimized QuickSort
void quicksort(int a[],int first,int last)
{
	while(first<last)
	{
		 int i=first,j=last; 
		 int mid=(first+last)/2; //mid value
		
		 if(a[first]>a[last])
			 Swap(a[first],a[last]); // ensure index pos=first value less than last
		 if(a[mid]>a[last])
			Swap(a[mid],a[last]);  // ensure index pos=mid value less than last
		 if(a[first]>a[mid])
			 Swap(a[first],a[mid]); // ensure first val less than mid
		 int tmp=a[first];  //now  a[first] is the mid-value of low -mid-high

		 while( i<j )
		 {
			 while(i<j && a[j]>=tmp)
				 --j;		// find the first index j that a[j] < tmp from right to left
			 if(i<j)
				 a[i++]=a[j];		// cover the a[i]. 
			 while( i<j && a[i]<tmp)
				 i++;			//find the first index i that a[i]>tmp from left to right
			 if(i<j)
				 a[j--]=a[i];		//cover the a[j] 
		 }
		if(i==j)
			a[i]=tmp;
		quicksort(a,first,i-1);
		first=i+1;			//reduce one recursion
		//quicksort(a,i+1,last);
	}
}

void QuickSort(int a[],int len)
{	
	if(len>32)
		quicksort(a,0,len-1);
	//else   // when data scale less than 32 use InsertSort
	//	InsertSort(a,len); 
}
void print(int a[],int len)
{
	for(int i=0;i<len;i++)
		printf("%d ",a[i]);
	printf("
");
}
int main()
{
	srand(time(NULL));
	const int MAX=1000;
	int a[MAX];
	for(int i=0;i<MAX;i++)
		a[i]=rand();
	clock_t timebegin=clock();
	QuickSort(a,MAX);
	clock_t timeend=clock();
	//cout<<"          :\t"<<timeend-timebegin<<"ms"<<endl;
	print(a,MAX);
}