快速排序
今天我們來說一下快速排序，這個排序算法也是面試的高頻考點，原理很簡單，我們一起來扒一下他吧。
我們先來說一下快速排序的基本思想，很容易理解。
1.先從數組中找一個基準數
2.讓其他比它大的元素移動到數列一邊，比他小的元素移動到數列另一邊，從而把數組拆解成兩個部分。
3.再對左右區間重複第二步，直到各區間只有一個數。
見下圖
快速排序上圖則為一次快排示意圖，下面我們再利用遞歸，分別對左半邊區間也就是 [3,1,2] 和右半區間 [7,6,5,8] 執行上訴過程，直至區間縮小為 1 也就是第三條，則此時所有的數據都有序。
簡單來說就是我們利用基準數通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比基準數小，另一部分記錄的關鍵字均比基準數大，然後分別對這兩部分記錄繼續進行分割，進而達到有序。
我們現在應該了解了快速排序的思想，那麼大家還記不記得我們之前說過的歸併排序，他們兩個用到的都是分治思想，那他們兩個有什麼不同呢？見下圖
註：這裡我們以區間的第一個元素作為基準數
對比雖然歸併排序和快速排序都用到了分治思想，但是歸併排序是自下而上的，先處理子問題，然後再合併，將小集合合成大集合，最後實現排序。
快速排序是由上到下的，先分區，然後再處理子問題。歸併排序雖然是穩定的、時間複雜度為 O(nlogn) 的排序算法，但是它是非原地排序算法。我們前面講過，歸併之所以是非原地排序算法，主要原因是合併函數需要利用輔助數組保存元素。
快速排序通過設計巧妙的原地分區函數，可以實現原地排序，解決了歸併排序佔用太多內存的問題。
我們根據思想可知，快速排序算法的核心就是如何利用基準數將記錄分區，這裡我們主要介紹兩種容易理解的方法，一種是挖坑填數，另一種是利用雙指針思想進行元素交換。
下面我們先來介紹下挖坑填數的分區方法
基本思想是我們首先以序列的第一個元素為基準數，然後將該位置挖坑，下面判斷 nums[hight] 是否大於基準數，如果大於，則左移 hight 指針，直至找到一個小於基準數的元素，將其填入之前的坑中，則 hight 位置會出現一個新的坑，此時移動 low 指針，找到大於基準數的元素，填入新的坑中。不斷迭代直至完成分區。
大家直接看我們的視頻模擬吧，一目了然。
註：為了便於理解所以採取了挖坑的形式展示
是不是很容易就理解啦，下面我們直接看代碼吧。
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort (int[] nums, int low, int hight) {
if (low < hight) {
int index = partition(nums,low,hight);
quickSort(nums,low,index-1);
quickSort(nums,index+1,hight);
}
}
public int partition (int[] nums, int low, int hight) {
int pivot = nums[low];
while (low < hight) {
//移動hight指針
while (low < hight && nums[hight] >= pivot) {
hight--;
}
//填坑
if (low < hight) nums[low] = nums[hight];
while (low < hight && nums[low] <= pivot) {
low++;
}
//填坑
if (low < hight) nums[hight] = nums[low];
}
//基準數放到合適的位置
nums[low] = pivot;
return low;
}
}
下面我們來看一下第二種交換方法的思路，原理一致，實現也比較簡單。
見下圖。
快速排序其實這種方法，算是對上面方法的挖坑填坑步驟進行合併，low 指針找到大於 pivot 的元素，hight 指針找到小於 pivot 的元素，然後兩個元素交換位置，最後再將基準數歸位。
兩種方法都很容易理解和實現，即使是完全沒有學習過快速排序的同學，理解了思想之後也能自己動手實現，下面我們繼續用視頻模擬下這種方法的執行過程吧。
兩種方法都很容易實現，對我們非常友好，大家可以自己去 AC 一下啊。
class Solution {
public int[] sortArray (int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort (int[] nums, int low, int hight) {
if (low < hight) {
int index = partition(nums,low,hight);
quickSort(nums,low,index-1);
quickSort(nums,index+1,hight);
}
}
public int partition (int[] nums, int low, int hight) {
int pivot = nums[low];
int start = low;
while (low < hight) {
while (low < hight && nums[hight] >= pivot) hight--;
while (low < hight && nums[low] <= pivot) low++;
if (low >= hight) break;
swap(nums, low, hight);
}
//基準值歸位
swap(nums,start,low);
return low;
}
public void swap (int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
快速排序的時間複雜度分析
快排也是用遞歸來實現的。所以快速排序的時間性能取決於快速排序的遞歸樹的深度。
如果每次分區操作，都能正好把數組分成大小接近相等的兩個小區間，那麼此時的遞歸樹是平衡的，性能也較好，遞歸樹的深度也就和之前歸併排序求解方法一致。
我們每一次分區需要對數組掃描一遍，做 n 次比較，所以最優情況下，快排的時間複雜度是 O(nlogn)。
但是大多數情況下我們不能劃分的很均勻，比如數組為正序或者逆序時，即 [1,2,3,4] 或 [4,3,2,1] 時，此時為最壞情況，那麼此時我們則需要遞歸調用 n-1 次，此時的時間複雜度則退化到了 O(n^2)。
快速排序的空間複雜度分析
快速排序主要時遞歸造成的棧空間的使用，最好情況時其空間複雜度為O (logn),對應遞歸樹的深度。最壞情況時則需要 n-1 次遞歸調用，此時空間複雜度為O(n)。
快速排序的穩定性分析
快速排序是一種不穩定的排序算法，因為其關鍵字的比較和交換是跳躍進行的，見下圖。
穩定性此時無論使用哪一種方法，第一次排序後，黃色的 1 都會跑到紅色 1 的前面，所以快速排序是不穩定的排序算法。
性能分析好啦，快速排序我們掌握的差不多了，下面我們一起來看看如何對其優化吧。
快速排序的迭代寫法
該方法實現也是比較簡單的，藉助了棧來實現，很容易實現。主要利用了先進先出的特性，這裡需要注意的就是入棧的順序，這裡算是一個小細節，需要注意一下，其中分區函數和上面一致。大家只需看入棧出棧情況即可。
class Solution {
public int[] sortArray(int[] nums) {
Stack<Integer> stack = new Stack<>();
stack.push(nums.length - 1);
stack.push(0);
while (!stack.isEmpty()) {
int low = stack.pop();
int hight = stack.pop();
if (low < hight) {
int index = partition(nums, low, hight);
stack.push(index - 1);
stack.push(low);
stack.push(hight);
stack.push(index + 1);
}
}
return nums;
}
public int partition (int[] nums, int low, int hight) {
int pivot = nums[low];
int start = low;
while (low < hight) {
while (low < hight && nums[hight] >= pivot) hight--;
while (low < hight && nums[low] <= pivot) low++;
if (low >= hight) break;
swap(nums, low, hight);
}
swap(nums,start,low);
return low;
}
public void swap (int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
快速排序優化
三數取中法
我們在上面的例子中選取的都是 nums[low] 做為我們的基準值，那麼當我們遇到特殊情況時呢？見下圖
特殊舉例我們按上面的方法，選取第一個元素做為基準元素，那麼我們執行一輪排序後，發現僅僅是交換了 2 和 7 的位置，這是因為 7 為序列的最大值。
所以我們的 pivot 的選取尤為重要，選取時應儘量避免選取序列的最大或最小值做為基準值。則我們可以利用三數取中法來選取基準值。
也就是選取三個元素中的中間值放到 nums[low] 的位置，做為基準值。這樣就避免了使用最大值或最小值做為基準值。
所以我們可以加上這幾行代碼實現三數取中法。
int mid = low + ((hight-low) >> 1);
if (nums[low] > nums[hight]) swap(nums,low,hight);
if (nums[mid] > nums[hight]) swap(nums,mid,hight);
if (nums[mid] > nums[low]) swap(nums,mid,low);
其含義就是讓我們將中間元素放到 nums[low] 位置做為基準值，最大值放到 nums[hight],最小值放到 nums[mid],即 [4,2,3] 經過上面代碼處理後，則變成了 [3,2,4]。
此時我們選取 3 做為基準值，這樣也就避免掉了選取最大或最小值做為基準值的情況。
三數取中法
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort (int[] nums, int low, int hight) {
if (low < hight) {
int index = partition(nums,low,hight);
quickSort(nums,low,index-1);
quickSort(nums,index+1,hight);
}
}
public int partition (int[] nums, int low, int hight) {
//三數取中，大家也可以使用其他方法
int mid = low + ((hight-low) >> 1);
if (nums[low] > nums[hight]) swap(nums,low,hight);
if (nums[mid] > nums[hight]) swap(nums,mid,hight);
if (nums[mid] > nums[low]) swap(nums,mid,low);
//下面和之前一樣，僅僅是多了上面幾行代碼
int pivot = nums[low];
int start = low;
while (low < hight) {
while (low < hight && nums[hight] >= pivot) hight--;
while (low < hight && nums[low] <= pivot) low++;
if (low >= hight) break;
swap(nums, low, hight);
}
swap(nums,start,low);
return low;
}
public void swap (int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
和插入排序搭配使用
我們之前說過，插入排序在元素個數較少時效率是最高的，沒有看過的同學可以去看一下之前的文章，所以當元素數量較少時，快速排序反而不如插入排序好用。
所以我們可以設定一個閾值，當元素個數大於閾值時使用快速排序，小於等於該閾值時則使用插入排序。我們設定閾值為 7 。
三數取中+插入排序
class Solution {
private static final int INSERTION_SORT_MAX_LENGTH = 7;
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort (int[] nums, int low, int hight) {
if (hight - low <= INSERTION_SORT_MAX_LENGTH) {
insertSort(nums,low,hight);
return;
}
int index = partition(nums,low,hight);
quickSort(nums,low,index-1);
quickSort(nums,index+1,hight);
}
public int partition (int[] nums, int low, int hight) {
//三數取中，大家也可以使用其他方法
int mid = low + ((hight-low) >> 1);
if (nums[low] > nums[hight]) swap(nums,low,hight);
if (nums[mid] > nums[hight]) swap(nums,mid,hight);
if (nums[mid] > nums[low]) swap(nums,mid,low);
int pivot = nums[low];
int start = low;
while (low < hight) {
while (low < hight && nums[hight] >= pivot) hight--;
while (low < hight && nums[low] <= pivot) low++;
if (low >= hight) break;
swap(nums, low, hight);
}
swap(nums,start,low);
return low;
}
public void insertSort (int[] nums, int low, int hight) {
for (int i = low+1; i <= hight; ++i) {
int temp = nums[i];
int j;
for (j = i-1; j >= 0; --j) {
if (temp < nums[j]) {
nums[j+1] = nums[j];
continue;
}
break;
}
nums[j+1] = temp;
}
}
public void swap (int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
好啦，我們的插入排序和快速排序的搭配使用就搞定啦。
我們繼續看下面這種情況
我們對其執行一次排序後，則會變成上面這種情況，然後我們繼續對藍色基準值的左區間和右區間執行相同操作。也就是 [2,3,6,3,1,6] 和 [8,6] 。我們注意觀察一次排序的結果數組中是含有很多重複元素的，我們之前的優化方式並不能很好的解決這種情況。
那麼我們為什麼不能將相同元素放到一起呢？這樣就能大大減小遞歸調用時的區間大小，見下圖。
三向切分這樣就減小了我們的左右區間大小，只需對區間 [3,1,2,4] 和 [8] 執行相同操作即可，我們將數組切分成了三部分，小於基準數的左區間，大於基準數的右區間，等於基準數的中間區間。
下面我們來看一下如何達到上面的情況，我們先來進行視頻模擬，模擬之後應該就能明白啦。
我們來剖析一下視頻，其實原理很簡單，我們利用探路指針也就是 i，遇到比 pivot 大的元素，則和 right 指針進行交換，交換後 right 指向的元素肯定比 pivot 大，則 right--，但是，此時我們的 nums[i] 指向的元素並不知道情況，所以我們的 i 指針先不動，繼續判斷。
如果此時 nums[i] < pivot 則與 left 指針交換，注意此時我們的 left 指向的值肯定是等於 povit的，所以交換後我們要 left++,i++, nums[i] == pivot 時，僅需要 i++ 即可，繼續判斷下一個元素。我們也可以藉助這個思想來解決經典的荷蘭國旗問題。
好啦，我們下面直接看代碼吧。
三數取中+三向切分+插入排序
class Solution {
private static final int INSERTION_SORT_MAX_LENGTH = 7;
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort(int nums[], int low, int hight) {
//插入排序
if (hight - low <= INSERTION_SORT_MAX_LENGTH) {
insertSort(nums,low,hight);
return;
}
//三數取中
int mid = low + ((hight-low) >> 1);
if (nums[low] > nums[hight]) swap(nums,low,hight);
if (nums[mid] > nums[hight]) swap(nums,mid,hight);
if (nums[mid] > nums[low]) swap(nums,mid,low);
//三向切分
int left = low, i = low + 1, right = hight;
int pvoit = nums[low];
while (i <= right) {
if (pvoit < nums[i]) {
swap(nums,i,right);
right--;
} else if (pvoit == nums[i]) {
i++;
} else {
swap(nums,left,i);
left++;
i++;
}
}
quickSort(nums,low,left-1);
quickSort(nums,right+1,hight);
}
public void insertSort (int[] nums, int low, int hight) {
for (int i = low+1; i <= hight; ++i) {
int temp = nums[i];
int j;
for (j = i-1; j >= 0; --j) {
if (temp < nums[j]) {
nums[j+1] = nums[j];
continue;
}
break;
}
nums[j+1] = temp;
}
}
public void swap (int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
好啦，一些常用的優化方法都整理出來啦，還有一些其他的優化算法九數取中，優化遞歸操作等因為不常用就不在這裡進行描述啦，
感興趣的可以自己看一下。好啦，這期的文章就到這裡啦，我們下期見，拜了個拜。