重生之我在黑盒學編程4

今天我們來學點算法——快速排序算法

快速排序作爲多種排序方法中效率最高的一種，其底層原理被廣泛運用（應該是吧），他的核心思想與二叉樹結構中的遞歸邏輯相似，首先標記一個元素作爲基準點，然後利用該基準點把數組分成左右兩個區間，並且使小於該基準點的元素放在左區間，大於該基準點的元素放在右區間，如此反覆遞歸，直到數組爲一個有序數組。

下面‘簡單’的講解一下

比如將一個數組的起始位置記成left，最後一個元素位置記成right，那麼標記left的位置的元素，把該元素看成基準點

這時候right要不斷的向左移動，若right所在位置的元素是小於key位置的元素，那麼right停止移動。left要不斷的向右移動，若left所在位置的元素是大於key位置的元素，那麼left停止移動。總結就是：left找大，right找小。

注：思路來自csdn

簡單推導一下得到上圖。

你如果覺得這個方法太難，沒關係還有一個更難的方法

和上一個方法一樣先定義一個基準點，只不過把這個基準點叫做“坑”，“坑”裏的元素是要被抹除的（也就是“坑”裏不能有元素），因此先用一個變量key來保存“坑”裏的元素。right向左移動找到小於該基準點（“坑”）的元素就把這個元素填到“坑”裏，這時候“坑”裏有了元素，可以表示“坑”被填滿了，但是right位置的就變成了新的“坑”，因爲right位置的元素被用來“填坑”了。

下一次就是left找大的元素給到right位置的”坑“，然後left的位置就成了新坑，如此反覆，直到left和righ相遇，待到他們相遇的位置必然是一個”坑“，這時候把key存儲的元素放到這個”坑“裏，此時會發現數組也以5（key）爲中心點分成了兩個區間，而且左區間的元素都是小於key的，右區間的元素都是大於key的。