快速排序

最壞情形時間復雜度\(\mathrm{O}(N^2)\)
平均運行時間\(\mathrm{O}(NlogN)\)

//快速排序驅動程序
void QuickSort(int  *a; int N)
{
	Qsort(a, 0, N - 1);
}

//實現三數中值分割法的程序
int Median3(int *a, int Left, int Right)
{
	int Center = (Left + Right) / 2;

	if (a[Left] < a[Center]) swap(&a[Left], &a[Center]);
	if (a[Left] < a[Right]) swap(&a[Left], &a[Right]);
	if (a[Center] < a[Right]) swap(&a[Center], &a[Right]);

	swap(&a[Center], &a[Right - 1]);
	return a[Right - 1];
}

//快速排序主例程
#define Cutoff 3

void Qsort(int *a, int Left, int Right)
{
	int i, j;
	int Pivot;

	if (Left + Cutoff <= Right)
	{
		Pivot = Median3(a, Left, Right);
		i = Left;
		j = Right - 1;
		for (; ; )
		{
			while (a[++i] < Pivot) {}
			while (a[--j] > Pivot) {}
			if (i < j) swap(&a[i], &a[j]);
			else break;
		}
		swap(&a[i], &a[Right - 1]);

		Qsort(a, Left, i - 1);
		Qsort(a, i + 1, Right);
	}
	else InsertionSort(a + Left, Right - Left + 1);//做一次插入排序
}

1. 該算法通過選取一個樞紐元，然后使數組的剩余部分大于樞紐元的在一側，小于樞紐元的在另一側，然后對兩邊使用同樣的方法，就是這樣使用遞歸的操作是的整個數組有序
2. 算法的移動策略大致如圖：

• 假如初始數組為8，1，4，9，6，3，5，2，7，0然后選取6為樞紐元，然后將樞紐元與數組最后一個元素交換

• 然后使用兩個指針i，j，i從第一個元素開始，j從倒數第二個元素開始

• 將i向右移動，將j向左移動，當i指向的數字大于樞紐元時停下，當j指向的數字小于樞紐元時停下

8| 1| 4| 9| 0| 3| 5| 2| 7| 6
-|-|-|-|-|-|-|-|-|-|-
i↑|-|-|-|-|-|-|j↑|-|-

• 此時若i在j的左邊，則交換兩個元素

2| 1| 4| 9| 0| 3| 5| 8| 7| 6
-|-|-|-|-|-|-|-|-|-|-
i↑|-|-|-|-|-|-|j↑|-|-

• 經過若干次這樣的操作后i指針將跑到j指針的右邊

2| 1| 4| 5| 0| 3| 9| 8| 7| 6
-|-|-|-|-|-|-|-|-|-|-
-|-|-|-|-|j↑|i↑|-|-|-

• 此時i和j已交錯，故不再交換，此時將樞紐元與i指向的元素交換，至此就完成了一次快速排序

2| 1| 4| 5| 0| 3| 6| 8| 7| 9
-|-|-|-|-|-|-|-|-|-|-
-|-|-|-|-|j↑|i↑|-|-|-

3 示例代碼中的三數中值分割法是將a[Left],a[Right]與a[Center]先進行排序，得到適當的樞紐元且在交換后返回，i和j也從Left + 1與Right - 2開始判斷