什么是快速排序？

1. 如何理解快速排序

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

快速排序的基本思想：

選擇一個基準數(shù)，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小。然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以達到全部數(shù)據(jù)變成有序。

快速排序的步驟：

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

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

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

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

2. 快速排序的過程描述

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

（2）將小于7的放在左邊，大于7的放在右邊，然后將基準數(shù)放到中間；

（3）然后再重復操作從左邊的數(shù)組選擇一個基準點2；

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

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

（6）最后出來的結(jié)果就是從左到右 2 ，3，7，12，15了。