————— 第二天 —————
————————————
同冒泡排序一樣，快速排序也屬于交換排序，通過元素之間的比較和交換位置來達到排序的目的。
不同的是，冒泡排序在每一輪只把一個元素冒泡到數(shù)列的一端，而快速排序在每一輪挑選一個基準元素，并讓其他比它大的元素移動到數(shù)列一邊，比它小的元素移動到數(shù)列的另一邊，從而把數(shù)列拆解成了兩個部分。
這種思路就叫做分治法。
每次把數(shù)列分成兩部分，究竟有什么好處呢？
假如給定8個元素的數(shù)列，一般情況下冒泡排序需要比較8輪，每輪把一個元素移動到數(shù)列一端，時間復雜度是O（n^2）。
而快速排序的流程是什么樣子呢？
如圖所示，在分治法的思想下，原數(shù)列在每一輪被拆分成兩部分，每一部分在下一輪又分別被拆分成兩部分，直到不可再分為止。
這樣一共需要多少輪呢？平均情況下需要logn輪，因此快速排序算法的平均時間復雜度是?O（nlogn）。
基準元素的選擇
基準元素，英文pivot，用于在分治過程中以此為中心，把其他元素移動到基準元素的左右兩邊。
那么基準元素如何選擇呢？
最簡單的方式是選擇數(shù)列的第一個元素：
這種選擇在絕大多數(shù)情況是沒有問題的。但是，假如有一個原本逆序的數(shù)列，期望排序成順序數(shù)列，那么會出現(xiàn)什么情況呢？
..........
我們該怎么避免這種情況發(fā)生呢？
其實很簡單，我們可以不選擇數(shù)列的第一個元素，而是隨機選擇一個元素作為基準元素。
這樣一來，即使在數(shù)列完全逆序的情況下，也可以有效地將數(shù)列分成兩部分。
當然，即使是隨機選擇基準元素，每一次也有極小的幾率選到數(shù)列的最大值或最小值，同樣會影響到分治的效果。
所以，快速排序的平均時間復雜度是?O（nlogn），最壞情況下的時間復雜度是?O（n^2）。
元素的移動
選定了基準元素以后，我們要做的就是把其他元素當中小于基準元素的都移動到基準元素一邊，大于基準元素的都移動到基準元素另一邊。
具體如何實現(xiàn)呢？有兩種方法：
1.挖坑法
2.指針交換法
何謂挖坑法？我們來看一看詳細過程。
給定原始數(shù)列如下，要求從小到大排序：
首先，我們選定基準元素Pivot，并記住這個位置index，這個位置相當于一個“坑”。并且設(shè)置兩個指針left和right，指向數(shù)列的最左和最右兩個元素：
接下來，從right指針開始，把指針所指向的元素和基準元素做比較。如果比pivot大，則right指針向左移動；如果比pivot小，則把right所指向的元素填入坑中。
在當前數(shù)列中，1<4，所以把1填入基準元素所在位置，也就是坑的位置。這時候，元素1本來所在的位置成為了新的坑。同時，left向右移動一位。
此時，left左邊綠色的區(qū)域代表著小于基準元素的區(qū)域。
接下來，我們切換到left指針進行比較。如果left指向的元素小于pivot，則left指針向右移動；如果元素大于pivot，則把left指向的元素填入坑中。
在當前數(shù)列中，7>4，所以把7填入index的位置。這時候元素7本來的位置成為了新的坑。同時，right向左移動一位。
此時，right右邊橙色的區(qū)域代表著大于基準元素的區(qū)域。
下面按照剛才的思路繼續(xù)排序：
8>4，元素位置不變，right左移
2<4，用2來填坑，left右移，切換到left。
6>4，用6來填坑，right左移，切換到right。
3<4，用3來填坑，left右移，切換到left。
5>4，用5來填坑，right右移。這時候left和right重合在了同一位置。
這時候，把之前的pivot元素，也就是4放到index的位置。此時數(shù)列左邊的元素都小于4，數(shù)列右邊的元素都大于4，這一輪交換終告結(jié)束。
public class QuickSort {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
// 遞歸結(jié)束條件：startIndex大等于endIndex的時候
if (startIndex >= endIndex) {
return;
}
// 得到基準元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 用分治法遞歸數(shù)列的兩部分
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一個位置的元素作為基準元素
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
// 坑的位置，初始等于pivot的位置
int index = startIndex;
//大循環(huán)在左右指針重合或者交錯時結(jié)束
while ( right >= left ){
//right指針從右向左進行比較
while ( right >= left ) {
if (arr[right] < pivot) {
arr[left] = arr[right];
index = right;
left++;
break;
}
right--;
}
//left指針從左向右進行比較
while ( right >= left ) {
if (arr[left] > pivot) {
arr[right] = arr[left];
index = left;
right--;
break;
}
left++;
}
}
arr[index] = pivot;
return index;
}
public static void main(String[] args) {
int[] arr = new int[] {4,7,6,5,3,2,8,1};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
代碼中，quickSort方法通過遞歸的方式，實現(xiàn)了分而治之的思想。
partition方法則實現(xiàn)元素的移動，讓數(shù)列中的元素依據(jù)自身大小，分別移動到基準元素的左右兩邊。在這里，我們使用移動方式是挖坑法。
指針交換法
何謂指針交換法？我們來看一看詳細過程。
給定原始數(shù)列如下，要求從小到大排序：
開局和挖坑法相似，我們首先選定基準元素Pivot，并且設(shè)置兩個指針left和right，指向數(shù)列的最左和最右兩個元素：
接下來是第一次循環(huán)，從right指針開始，把指針所指向的元素和基準元素做比較。如果大于等于pivot，則指針向左移動；如果小于pivot，則right指針停止移動，切換到left指針。
在當前數(shù)列中，1<4，所以right直接停止移動，換到left指針，進行下一步行動。
輪到left指針行動，把指針所指向的元素和基準元素做比較。如果小于等于pivot，則指針向右移動；如果大于pivot，則left指針停止移動。
由于left一開始指向的是基準元素，判斷肯定相等，所以left右移一位。
由于7 > 4，left指針在元素7的位置停下。這時候，我們讓left和right指向的元素進行交換。
接下來，我們進入第二次循環(huán)，重新切換到right向左移動。right先移動到8，8>2，繼續(xù)左移。由于2<8，停止在2的位置。
切換到left，6>4，停止在6的位置。
元素6和2交換。
進入第三次循環(huán)，right移動到元素3停止，left移動到元素5停止。
元素5和3交換。
進入第四次循環(huán)，right移動到元素3停止，這時候請注意，left和right指針已經(jīng)重合在了一起。
當left和right指針重合之時，我們讓pivot元素和left與right重合點的元素進行交換。此時數(shù)列左邊的元素都小于4，數(shù)列右邊的元素都大于4，這一輪交換終告結(jié)束。
public class QuickSort {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
// 遞歸結(jié)束條件：startIndex大等于endIndex的時候
if (startIndex >= endIndex) {
return;
}
// 得到基準元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根據(jù)基準元素，分成兩部分遞歸排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一個位置的元素作為基準元素
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
while( left != right) {
//控制right指針比較并左移
while(left<right && arr[right] > pivot){
right--;
}
//控制right指針比較并右移
while( left<right && arr[left] <= pivot) {
left++;
}
//交換left和right指向的元素
if(left<right) {
int p = arr[left];
arr[left] = arr[right];
arr[right] = p;
}
}
//pivot和指針重合點交換
int p = arr[left];
arr[left] = arr[startIndex];
arr[startIndex] = p;
return left;
}
public static void main(String[] args) {
int[] arr = new int[] {4,7,6,5,3,2,8,1};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
和挖坑法相比，指針交換法在partition方法中進行的元素交換次數(shù)更少。
非遞歸實現(xiàn)
為什么這樣說呢？
因為我們代碼中一層一層的方法調(diào)用，本身就是一個函數(shù)棧。每次進入一個新方法，就相當于入棧；每次有方法返回，就相當于出棧。
所以，我們可以把原本的遞歸實現(xiàn)轉(zhuǎn)化成一個棧的實現(xiàn)，在棧當中存儲每一次方法調(diào)用的參數(shù)：
下面我們來看一下代碼：
public class QuickSortWithStack {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
// 用一個集合棧來代替遞歸的函數(shù)棧
Stack<Map<String, Integer>> quickSortStack = new Stack<Map<String, Integer>>();
// 整個數(shù)列的起止下標，以哈希的形式入棧
Map rootParam = new HashMap();
rootParam.put("startIndex", startIndex);
rootParam.put("endIndex", endIndex);
quickSortStack.push(rootParam);
// 循環(huán)結(jié)束條件：棧為空時結(jié)束
while (!quickSortStack.isEmpty()) {
// 棧頂元素出棧，得到起止下標
Map<String, Integer> param = quickSortStack.pop();
// 得到基準元素位置
int pivotIndex = partition(arr, param.get("startIndex"), param.get("endIndex"));
// 根據(jù)基準元素分成兩部分, 把每一部分的起止下標入棧
if(param.get("startIndex") < pivotIndex -1){
Map<String, Integer> leftParam = new HashMap<String, Integer>();
leftParam.put("startIndex", param.get("startIndex"));
leftParam.put("endIndex", pivotIndex -1);
quickSortStack.push(leftParam);
}
if(pivotIndex + 1 < param.get("endIndex")){
Map<String, Integer> rightParam = new HashMap<String, Integer>();
rightParam.put("startIndex", pivotIndex + 1);
rightParam.put("endIndex", param.get("endIndex"));
quickSortStack.push(rightParam);
}
}
}
private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一個位置的元素作為基準元素
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
while( left != right) {
//控制right指針比較并左移
while(left<right && arr[right] > pivot){
right--;
}
//控制right指針比較并右移
while( left<right && arr[left] <= pivot) {
left++;
}
//交換left和right指向的元素
if(left<right) {
int p = arr[left];
arr[left] = arr[right];
arr[right] = p;
}
}
//pivot和指針重合點交換
int p = arr[left];
arr[left] = arr[startIndex];
arr[startIndex] = p;
return left;
}
public static void main(String[] args) {
int[] arr = new int[] {4,7,6,5,3,2,8,1};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
和剛才的遞歸實現(xiàn)相比，代碼的變動僅僅在quickSort方法當中。該方法中引入了一個存儲Map類型元素的棧，用于存儲每一次交換時的起始下標和結(jié)束下標。
每一次循環(huán)，都會讓棧頂元素出棧，進行排序，并且按照基準元素的位置分成左右兩部分，左右兩部分再分別入棧。當棧為空時，說明排序已經(jīng)完畢，退出循環(huán)。
