我的雙節日誌——學習快速排序

排序過程

• 橙色爲排序的基準數 綠色爲交換後的基準數位置
• 黃色爲右哨兵 青色爲左哨兵
• 粉色爲兩即將交換的數

本人用python寫的(感覺效果不好)

原理

這是序列：

我們需要以基準數爲分界點，讓pivot左邊的數比它小(即左邊序列的元素都 <= -1)，pivot右邊的數比它大(即又邊序列的元素都 >= -1)。

下面以序列最左側的元素(首元素)爲基準數(後面就叫它pivot吧)。

再通過設置兩個哨兵left,right(left < right)，從序列兩端開始與pivot比較。

橙色背景爲基準數pivot

<1>先移動右邊的哨兵(後面解釋爲什麼)：

由於 -1 < 1，符合條件(條件：arr[right] >= pivot)，所以我們將哨兵right左移到下一元素與pivot比較。

我們移動到-3處，發現 -1 > -3,不符合我們之前的條件，所以我們讓哨兵right停下。

<2>現在移動左哨兵left：

首元素爲 -1 ， -1 = -1,符合條件(條件：arr[left] <= pivot)，現在左哨兵繼續左移。

我們發現移動後設備left處的數 2 > -1，不符合條件，所以哨兵停下。

快速排序的核心思想就是分治。

我們以基準數爲界，基準數左側所有元素皆小於基準數，右側所有元素皆大於基準數。

我們左側所有元素和右側所有元素可以繼續進行這個操作，再取出一個基準數爲界，如此反覆下去，最後使得整個序列有序。

故而我們在兩哨兵停下時，讓其所在元素進行交換以達目的。

<3>交換元素：

<4>繼續移動右哨兵直到遇到左哨兵:

我們發現左右哨兵已經相遇，這時候說明相遇位置的左側所有元素<=基準數，右側所有元素>基準數。這時候我們將相遇位置處元素與基準數交換來分界序列

<5>交換基準數位置：

交換位置後我們發現，基準數-1左側已經排序完成，右側還未排序完，下面我們開始用相同的思路對右側序列進行排序。

排序子序列

我們快速排序的函數是QuickSort(array[],begin,end);

其中array爲待排序序列(數組)，begin(begin = left + 1)是array中要排序的起始位置，end是結束位置。

紅色框內是要排序的序列

現在我們按照之前排序總序列的方法來排序右邊子序列。

由於我們不對左側範圍外序列排序，所以這邊我沒寫出來。不過注意，左側的序列仍然是存在的，我們仍然可以對其操作，所以我們要避免這種越界事情發生。

左側序列我沒寫出來

現在我們移動右哨兵right到符合條件位置：

發現與左哨兵相遇，所以繼續之前的交換基準數位置的操作。

這時我們發現基準數與哨兵相遇位置相同，那麼怎麼辦呢？

這證明了右邊序列元素都比基準數大，所以我們繼續對右邊排序！

QuickSort(array[],left+1,right);

下面我直接列出後面的所有步驟：

結果：

爲什麼右哨兵先行

我直接舉個例子給大家瞭解一下。

下面是待排序的序列：

1 0 3 7 2

哨兵left移動到3

1 0 3 7 2

      ^

下面移動哨兵right到3，然後與基準數交換

3 0 1 7 2

很顯然這使得比基準數大的數交換到了左邊。

如果是右哨兵先行的話就能保證交換的數是絕對比基準數小的。

 原因：

哨兵left移動後到達比基準數大的數位置，可能該位置後的還有一個數大於這個基準數，但left已經無法移動。

如果此時哨兵left所在位置右邊都大於基準數的話，只能等待right移動會面，被迫把大於基準數的數交換到了前面。

當然這也是我們使用的基準數是第一位數才造成的問題，我們也可以自行改動代碼來解決問題。

代碼：

C語言：

VS得使用動態數組編譯，這用的是dev

C++：

VS上可編譯。

Python：

寫blog也是雙節日記。

歡迎大家指出錯誤，互相學習讓我們一起成長！