快速排序算法詳解
時間：2018-12-26 來源：華清遠見
快速排序(Quick Sort)是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出，其基本思想是選取一個記錄作為樞軸，經過一趟排序，將整段序列分為兩個部分，其中一部分的值都小于樞軸，另一部分都大于樞軸。然后繼續對這兩部分繼續進行排序，從而使整個序列達到有序。
1.基本思想:
例如對于一個待排序的源數組arr = { 4，1，3，2，7，6，8}。
我們可以隨便選一個元素，假如我們選數組的第一個元素吧，我們把這個元素稱之為“主元”吧。
然后將大于或等于主元的元素放在右邊，把小于或等于主元的元素放在左邊。
通過這種規則的調整之后，左邊的元素都小于或等于主元，右邊的元素都大于或等于主元，很顯然，此時主元所處的位置，是一個有序的位置,即主元已經處于排好序的位置了。
主元把數組分成了兩半部分。把一個大的數組通過主元分割成兩小部分的這個操作，我們也稱之為分割操作(partition)。
接下來，我們通過遞歸的方式，對左右兩部分采取同樣的方式，每次選取一個主元元素，使他處于有序的位置。當然是遞歸到子數組只有一個元素或者0個元素了，遞歸結束。
代碼：quick_sort 是快速排序的算法，partion函數是對于數組的分割操作，分割操作有很多種方法，我這里列舉三種。
2.分割操作
2.1 單向調整
選最后一個為主元，假設數組arr的范圍為[left, right]，即起始下標為left，末尾下標為right。源數組如下
然后可以用一個下標 i 指向 left，即 i = left ;用一個下標 j 也指向left，即j = left
接下來 j 從左向右遍歷，遍歷的范圍為 [left, right-1] ，遍歷的過程中，如果遇到比主元小的元素，則把該元素與 i 指向的元素交換，并且 i = i +1
當j指向1時，1比4小，此時把i和j指向的元素交換，之后 i++。
就這樣讓j一直向右遍歷，直到 j = right
遍歷完成之后，把 i 指向的元素與主元進行交換，交換之后，i 左邊的元素一定小于主元，而 i 右邊的元素一定大于或等于主元。這樣，就 i 完成了一次分割了。
代碼如下：
2.2 雙向調整
源數組如下：
然后用令變量i = left + 1，j = right。然后讓 i 和 j 從數組的兩邊向中間掃描。
i 向右遍歷的過程中，如果遇到大于或等于主元的元素時，則停止移動，j向左遍歷的過程中，如果遇到小于或等于主元的元素則停止移動。
當i和j都停止移動時，如果這時i < j，則交換 i, j 所指向的元素。此時 i < j，交換8和3
然后繼續向中間遍歷，直到i >= j。
此時i >= j，分割結束。最后在把主元與 j 指向的元素交換。
這個時候，j 左邊的元素一定小于或等于主元，而右邊則大于或等于主元。
到此，分割調整完畢。
代碼如下：
2.3 挖坑法
1.選取一個關鍵字(key)作為主元，一般取整組記錄的第一個數/最后一個，這里采用選取序列最后一個數為樞軸，也是初始的坑位。
2.設置兩個變量left = 0;right = N - 1;
3.從left一直向后走，直到找到一個大于key的值，然后將該數放入坑中，坑位變成了array[left]。
4.right一直向前走，直到找到一個小于key的值，然后將該數放入坑中，坑位變成了array[right]。
5.重復3和4的步驟，直到left和right相遇，然后將key放入最后一個坑位。
代碼如下：
