學習算法導論——快速排序

快速排序用的也是分治法，快速排序分為三個步驟：

1.分解

數組A[low..high]被劃分為兩個(可能為空)的子數組A[low...q-1]和A[q+1...high]，使得A[low...q-1]中的每個元素都小于等于A[q]，而A[q]小于等于A[q+1...high]中的每個元素。

q是一個劃分點。

2.解決

通過遞歸調用快速排序，對字數組A[low...q-1]和A[q+1...high]進行快速排序。

3.合并

因為字數組都是原址排序的，是以不需要合并操作。

C++代碼：

unsigned Partition(unsigned A[], unsigned low, unsigned high)
{
	unsigned i = low - 1;
	unsigned x = A[high];//以最後一個值作為分界數
	for (unsigned j = low; j < high; ++j)
	{
		if (A[j] <= x)
		{
			++i;
			unsigned temp = A[i];
			A[i] = A[j];
			A[j] = temp;
		}
	}
	unsigned temp = A[i+1];
	A[i+1] = A[high];
	A[high] = temp;
	return i + 1;
}
           

void Quick_Sort(unsigned A[], unsigned low, unsigned high)
{
	if (low < high)
	{
		unsigned q = Partition(A, low, high);
		Quick_Sort(A, low, q - 1);
		Quick_Sort(A, q + 1, high);
	}
}
           

Partition()函數是找一個分界點，它的原理是這樣的：

定義一個"訓示器"i，i所指的位置A[i]往左到A[0]均是小于等于分界數的，i+1到j-1這個區間的值都是大于等于分界數的。是以，隻要j循環時找到一個小于等于分界數的值，那麼就A[i=1]和A[j]交換，訓示器i+1。因為以最後一個值為分界數，是以循環到倒數第二個值時結束，這時，隻要把A[i+1]和最後的分界數交換就行。

過程如圖：

（來自算法導論）