最容易了解的快速排序方法和程式

        希爾排序相當于直接插入排序的更新，它們同屬于插入排序類，堆排序相當于簡單選擇排序的更新，它們同屬于選擇排序類。而快速排序其實就是我們前面認為最慢的冒泡排序的更新，它們都屬于交換排序類。即它也是通過不斷的比較和移動交換來實作排序的，隻不過它的實作，增大了記錄的比較和移動的距離，将關鍵字較大的記錄從前面直接移動到後面，關鍵字較小的記錄從後面直接移動到前面，進而減少了總的比較次數和移動交換次數。

        快速排序（Quick Sort）的基本思想是：通過一趟排序将待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分别對這兩部分記錄繼續進行排序，以達到整個序列有序的目的。

        以前總覺得快速排序挺晦澀的，大學的時候考試還是得死記硬背呢！今天看到了伍迷老師對各種排序算法的講解，覺得思路清晰，十分易懂，以後應該不會忘記的幹幹淨淨了。放在這裡為學習備份~~

下面看這個思想十分容易接受的程式：

#include <stdio.h>

void swap(int *a,int *b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

/* 交換a中子表的記錄，使樞軸記錄到位，并傳回其所在位置 */
/* 此時在它之前(後)的記錄均不大(小)于它。 */
int partition(int a[],int low,int high)
{
	int pivotKey;
	pivotKey = a[low];//用子表的第一個記錄作樞軸記錄

	while(low < high)// 從表的兩端交替地向中間掃描 
	{
		while(low < high && a[high] >= pivotKey)
			high--;
		swap(&a[low],&a[high]);//将比樞軸記錄小的記錄交換到低端
		while(low < high && a[low] <= pivotKey)
			low++;
		swap(&a[low],&a[high]);//将比樞軸記錄大的記錄交換到高端
	}
	return low;//傳回樞軸所在位置
}

void QSort(int a[],int low,int high)
{
	int pivot;
	if(low < high)
	{
		pivot = partition(a,low,high);//将a數組一分為二，且傳回樞值的位置
		QSort(a,low,pivot-1);//對低子表遞歸
		QSort(a,pivot+1,high);//對高子表遞歸
	}
}

//快速排序
void QuickSort(int a[],int n)
{
	QSort(a,0,n-1);//由于需要遞歸調用，是以我們外封裝了一個函數
}

void main()
{
	int i;
	int a[8] = {5,4,1,3,9,5,8,2};
	QuickSort(a,8);
	for(i=0;i<8;i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}
           

因為在現實中，待排序的系列極有可能是基本有序的，此時，總是固定選取第一個關鍵字（其實無論是固定選取哪一個位置的關鍵字）作為首個樞軸就變成了極為不合理的作法。

改進，于是就有了三數取中（median-of-three）法。即取三個關鍵字先進行排序，将中間數作為樞軸，一般是取左端、右端和中間三個數，也可以随機選取。這樣至少這個中間數一定不會是最小或者最大的數，從機率來說，取三個數均為最小或最大數的可能性是微乎其微的，是以中間數位于較為中間的值的可能性就大大提高了。由于整個序列是無序狀态，随機選取三個數和從左中右端取三個數其實是一回事，而且随機數生成器本身還會帶來時間上的開銷，是以随機生成不予考慮。

我們來看看取左端、右端和中間三個數的實作代碼，在Partition函數代碼的第3行與第4行之間增加這樣一段代碼。

int pivotkey;

 int m = low + (high - low)  /* 計算數組中間的元素的下标 */  
 if (a[low]>a[high])   
  swap(&a[low],&a[high]);    /* 交換左端與右端資料，保證左端較小 */
 if (a[m]>a[high])
  swap(&a[high],&a[m]);    /* 交換中間與右端資料，保證中間較小 */
 if (a[m]>a[low])
  swap(&a[m],&a[low]);    /* 交換中間與左端資料，保證左端較小 */
 
 /* 此時L.r[low]已經為整個序列左中右三個關鍵字的中間值。*/
pivotkey=L->r[low];    /* 用子表的第一個記錄作樞軸記錄 */