1. 如何理解快速排序

快速排序是對氣泡排序的一種改進， 它是不穩定的。由C. A. R. Hoare在1962年提出的一種劃分交換排序，採用的是分治策略（一般與遞迴結合使用），以減少排序過程中的比較次數，它的最好情況O(nlogn)，最壞情況O(n^2)，平均時間複雜度為O(nlogn)。分而治之不是一種解決問題的演算法，而是一種希望問題分解，將複雜的問題劃分為多個簡單問題來解決的思想。

快速排序的基本思想：

選擇一個基準數，透過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小。然後再按此方法對這兩部分資料分別進行快速排序，整個排序過程可以遞迴進行，以達到全部資料變成有序。

快速排序的步驟：

(1) 從數列中挑出一個"基準值"（pivot）。

(2) 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割槽退出之後，該基準就處於數列的中間位置。這個稱為分割槽（partition）操作。

(3) 遞迴地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

注意：基準元素/左遊標/右遊標都是針對單趟排序而言的，也就是說在整個排序過程的多趟排序中，各趟排序取得的基準元素/左遊標/右遊標一般都是不同的。對於基準元素的選取，原則上是任意的，但是一般我們選取陣列中第一個元素為基準元素（假設陣列隨機分佈）。

2. 快速排序的過程描述

（1）選擇最右邊的元素為基準數7；

（2）將小於7的放在左邊，大於7的放在右邊，然後將基準數放到中間；

（3）然後再重複操作從左邊的陣列選擇一個基準點2；

（4）3比2大則放到基準樹的右邊；

（5）右邊的陣列也是一樣選擇12作為基準數，15比12大所以放到了12的右邊；

（6）最後出來的結果就是從左到右 2 ，3，7，12，15了。