快速排序里的學問:快速排序的過程

理解快速排序的工作機制
服務器君一共花費了114.829 ms進行了5次數據庫查詢,努力地為您提供了這個頁面。
試試閱讀模式?希望聽取您的建議

通過前面問題以及引入了“信息熵”的概念,我們可以重新來理解排序的本質:

一組未排序的N個數字,它們一共有N!種重排,其中只有一種排列是滿足題意的(譬如從大到小排列)。

換句話說,排序問題的可能性一共有N!種。任何基于比較的排序的基本操作單元都是“比較a和b”,這就相當于猜數字游戲里面的一個問句,顯然這個問句的答案只能是“是”或“否”,一個只有兩種輸出的問題最多只能將可能性空間切成兩半,根據上面的思路,最佳切法就是切成1/2和1/2(將數組切成一半)。也就是說,我們希望在比較了a和b的大小關系之后,如果發現a < b的話剩下的排列可能性就變成N!/2,如果發現a>b也是剩下N!/2種可能性。

由于假設每種排列的概率是均等的,所以這也就意味著支持a < b的排列一共有N!/2個,支持a > b的也是N!/2個,換言之,a < b的概率等于a > b的概率。

我們希望每次在比較a和b的時候,a < b和a > b的概率是均等的,這樣我們就能保證無論如何都能將可能性縮小為原來的一半的最優下界。

一個直接的推論是,如果每次都像上面這樣的完美比較,那么N個元素的N!種可能排列只需要log2N!就排查完了,而log2N!近似于NlogN。這正是快排的復雜度。

快速排序的實現

我們先理解一下快速排序的工作機制吧,下面是《算法導論》里的快排:

QUICKSORT(A, p, r)
 if p < r
	then q ← PARTITION(A, p, r)   //關鍵
         QUICKSORT(A, p, q - 1)
         QUICKSORT(A, q + 1, r)

快速排序算法的關鍵是PARTITION過程,它對A[p..r]進行就地重排:

PARTITION(A, p, r)
  x ← A[r]
  i ← p - 1
  for j ← p to r - 1
       do if A[j] ≤ x
             then i ← i + 1
                  exchange A[i] <-> A[j]
  exchange A[i + 1] <-> A[r]
  return i + 1

我們將上面的過程用C語言描述一下:

#include "stdio.h"
#include "math.h"
#include "stdlib.h"

void PrintArray(int *arr);
void swap(int *a,int *b);

int num = 10;

void QuickSort(int *arr, int beg, int end)
{
	if(beg < end)
	{
		int pivot = Partition(arr, beg, end);
		QuickSort(arr, beg, pivot-1);
		QuickSort(arr, pivot+1, end);
	}
}

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

int Partition(int *arr, int beg, int end)
{
    int j;
	int sentinel = arr[end];
	printf("\n    sentinel = arr[%d] = %d", end, sentinel);
	int i = beg-1;
	for(j=beg; j<=end-1; ++j)
	{
		if(arr[j] <= sentinel)
		{
		    printf("\n    arr[%d](%d) <= sentinel(%d)", j, arr[j], sentinel);
			i++;
			swap(&arr[i], &arr[j]);
		}
	}
	swap(&arr[i+1], &arr[end]);

	printf("\n排序過程:");
	PrintArray(arr);
	return i+1;
}

void PrintArray(int arr[])
{
    int i;
	for(i=0; i < num; ++i)
	{
	    printf("%d ", arr[i]);
	}
}

int main()
{
    int i;
	int arr[10];

	srand(time(0));
    for(i=0; i < 10; i++)
    {
        arr[i] = rand()%100+1;
        //printf("%d ", rand()%100+1);
    }
    printf("初始數組:");
    PrintArray(arr);

	QuickSort(arr, 0, num-1);
	printf("\n最后結果:");
	PrintArray(arr);
	return 0;
}
初始數組:59 40 55 92 73 69 27 79 3 30
    sentinel = arr[9] = 30
    arr[6](27) <= sentinel(30)
    arr[8](3) <= sentinel(30)
排序過程:27 3 30 92 73 69 59 79 40 55
    sentinel = arr[1] = 3
排序過程:3 27 30 92 73 69 59 79 40 55
    sentinel = arr[9] = 55
    arr[8](40) <= sentinel(55)
排序過程:3 27 30 40 55 69 59 79 92 73
    sentinel = arr[9] = 73
    arr[5](69) <= sentinel(73)
    arr[6](59) <= sentinel(73)
排序過程:3 27 30 40 55 69 59 73 92 79
    sentinel = arr[6] = 59
排序過程:3 27 30 40 55 59 69 73 92 79
    sentinel = arr[9] = 79
排序過程:3 27 30 40 55 59 69 73 79 92
最后結果:3 27 30 40 55 59 69 73 79 92
Process returned 0 (0x0)   execution time : 0.564 s
Press any key to continue.

從程序的運行結果我們就可以很清晰地看出快速排序的工作工程:

  1. 定點sentinel設為數組最后一個元素30
  2. 把比30小的劃成一個小組(27,3,30),并把它們放在數組的前面。
  3. 定點sentinel設為小組的最后一個,不包含30,即(27,3)中的3。
  4. 對小組原地排序,即(3,27)。這樣就完成這個小組的排序了(3,27,30)。
  5. 定點sentinel再次設為數組最后一個元素55。
  6. 把小于55的元素找出來劃分為另外的小組(40)。
  7. 那個小組的排序也已經完成(40,55)。
  8. 定點再設為73,同樣分組(69,59,73),排序為(59,69,73)。
  9. 定點再設為79,分組(79)
  10. 完成排序:3 27 30 40 55 59 69 73 79 92

總結下快排的過程:隨機選擇一個元素做“軸元素”(上面的定點sentinel),將所有小于軸元素的移到左邊,其余移到右邊。根據這個過程,快排的第一次比較就是將一個元素和軸元素比較,這個時候顯而易見的是,“大于”和“小于”的可能性各占一半。這是一次漂亮的比較。

延伸閱讀

此文章所在專題列表如下:

  1. 快速排序里的學問:從猜數字開始
  2. 快速排序里的學問:再看看稱球問題
  3. 快速排序里的學問:信息熵
  4. 快速排序里的學問:快速排序的過程
  5. 快速排序里的學問:霍爾與快速排序
  6. 快速排序里的學問:霍爾快排的實現
  7. 快速排序里的學問:樞紐元選擇與算法效率
  8. 快速排序里的學問:隨機化快排

本文地址:http://www.zqhthc.tw/librarys/veda/detail/2390,歡迎訪問原出處。

不打個分嗎?

轉載隨意,但請帶上本文地址:

http://www.zqhthc.tw/librarys/veda/detail/2390

如果你認為這篇文章值得更多人閱讀,歡迎使用下面的分享功能。
小提示:您可以按快捷鍵 Ctrl + D,或點此 加入收藏

閱讀一百本計算機著作吧,少年

很多人覺得自己技術進步很慢,學習效率低,我覺得一個重要原因是看的書少了。多少是多呢?起碼得看3、4、5、6米吧。給個具體的數量,那就100本書吧。很多人知識結構不好而且不系統,因為在特定領域有一個足夠量的知識量+足夠良好的知識結構,系統化以后就足以應對大量未曾遇到過的問題。

奉勸自學者:構建特定領域的知識結構體系的路徑中再也沒有比學習該專業的專業課程更好的了。如果我的知識結構體系足以囊括面試官的大部分甚至吞并他的知識結構體系的話,讀到他言語中的一個詞我們就已經知道他要表達什么,我們可以讓他坐“上位”畢竟他是面試官,但是在知識結構體系以及心理上我們就居高臨下。

所以,閱讀一百本計算機著作吧,少年!

《浪潮之巔》 吳軍 (作者)

近一百多年來,總有一些公司很幸運地、有意識或無意識地站在技術革命的浪尖之上。在長達十年甚至幾十年的時間里,它們代表著科技的浪潮,直到下一波浪潮的來臨。從19世紀末算起,AT&T公司、IBM公司、蘋果公司、英特爾公司、微軟公司、思科公司、雅虎公司和Google公司都先后被幸運地推到了浪尖。雖然,它們來自不同的領域,中間有些已經衰落或正在衰落,但是它們都極度輝煌過。吳軍的這本《浪潮之巔》系統地介紹了這些公司成功的本質原因及科技工業一百多年的發展。在這些公司興衰的背后,有著它必然的規律。《浪潮之巔》不僅講述科技工業的歷史,更重在揭示它的規律性。

更多計算機寶庫...

英超直播吻球网