基本概念
快速排序（Quicksort）是對冒泡排序算法的一種改進。
性質
内部排序
快速排序是一種内部排序方法。也就是說快速排序的排序對象是讀入内存的數據。
比較排序
快速排序确定元素位置的方法基于元素之間關鍵字大小的比較。
所有基于比較方法的排序方法的時間下界不會低于O(nlgn)。這個結論的具體證明，請參考有關算法的書籍，例如《算法導論》第8章。
快速排序在理想情況下，能嚴格地達到O(nlgn)的下界。一般情況下，快速排序與随機化快速排序的平均情況性能都達到了O(nlgn)。
不穩定性
快速排序是一種不穩定的排序方法。簡單地說，元素a1,a2的關鍵字有a1.key=a2.key，則不穩定的排序方法不能保證a1,a2在排序後維持原來的位置先後關系。
原地排序
在排序的具體操作過程中，除去程序運行實現的空間消費（例如遞歸棧），快速排序算法隻需消耗确定數量的空間（即S(1)，常數級空間）。
這個性質的意義，在于在内存空間受到限制的系統（例如MCU）中，快速排序也能夠很好地工作。
時空複雜度
快速排序每次将待排序數組分為兩個部分，在理想狀況下，每一次都将待排序數組劃分成等長兩個部分，則需要logn次劃分。而在最壞情況下，即數組已經有序或大緻有序的情況下，每次劃分隻能減少一個元素，快速排序将不幸退化為冒泡排序，所以快速排序時間複雜度下界為O(nlogn)，最壞情況為O(n^2)。在實際應用中，快速排序的平均時間複雜度為O(nlogn)。快速排序在對序列的操作過程中隻需花費常數級的空間。空間複雜度S(1)。但需要注意遞歸棧上需要花費最少logn最多n的空間。
随機化算法
快速排序的最壞情況基于每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在數組已經有序的情況下，每次劃分将得到最壞的結果。一種比較常見的優化方法是随機化算法，即随機選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴于輸入數據，而是由于随機函數取值不佳。實際上，随機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以随機化快速排序可以對于絕大多數輸入數據達到O(nlogn)的期望時間複雜度。一位前輩做出了一個精辟的總結：“随機化快速排序可以滿足一個人一輩子的人品需求。”
随機化快速排序的唯一缺點在于，一旦輸入數據中有很多的相同數據，随機化的效果将直接減弱。對于極限情況，即對于n個同的數排序，随機化快速排序的時間複雜度将毫無疑問的降低到O(n^2)。
算法基本思想
快速排序的基本思想是基于分治策略的。對于輸入的子序列L【p..r】，如果規模足夠小則直接進行排序（比如用前述的冒泡、選擇、插入排序均可），否則分三步處理：
分解(Divide)：将待排序列L【p..r】劃分為兩個非空子序列L【p..q】和L【q 1..r】，使L【p..q】中任一元素的值不大于L【q 1..r】中任一元素的值。具體可通過這樣的途徑實現：在序列L【p..r】中選擇數據元素L【q】，經比較和移動後，L【q】将處于L【p..r】中間的适當位置，使得數據元素L【q】的值小于L【q 1..r】中任一元素的值。
遞歸求解(Conquer)：通過遞歸調用快速排序算法，分别對L【p..q】和L【q 1..r】進行排序。合并(Merge)：由于對分解出的兩個子序列的排序是就地進行的，所以在L【p..q】和L【q 1..r】都排好序後不需要執行任何計算L【p..r】就已排好序，即自然合并。這個解決流程是符合分治法的基本步驟的。因此，快速排序法是分治法的經典應用實例之一。
區别
快速排序法是對冒泡排序法的一種改進，也是基于交換排序的一種算法。因此，被稱為"分區交換排序"。在待排序序列中按某種方法選取一個元素K，以它為分界點，用交換的方法将序列分為兩個部分：比該值小的放在左邊，否則在右邊。形成"{左子序列}K{右子序列}"。再分别對左、右兩部分實施上述分解過程，直到各子序列長度為1，即有序為止。分界點元素值K的選取方法不同，将構成不同的排序法，也将影響排序的效率：例如，可取左邊第1個元素為分界點、取中點A【（left right）/2】為分界點、或選取最大和最小值的平均值為分界點等。
