一個快速排序這么多細(xì)節(jié)？
之前一起看了歸并排序和一些利用歸并排序可以解決的經(jīng)典題目，今天我們再來說一下另一個高頻考點，快速排序。甚至比歸并排序考的還勤。你或許已經(jīng)掌握了快速排序，或者看過一些其他文章，不過我相信，讀完這個文章肯定還會有所收獲！
快速排序
今天我們來說一下快速排序，這個排序算法也是面試的高頻考點，原理很簡單，我們一起來扒一下他吧。
我們先來說一下快速排序的基本思想，很容易理解。
1.先從數(shù)組中找一個基準(zhǔn)數(shù)
2.讓其他比它大的元素移動到數(shù)列一邊，比他小的元素移動到數(shù)列另一邊，從而把數(shù)組拆解成兩個部分。
3.再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)。
見下圖
上圖則為一次快排示意圖，下面我們再利用遞歸，分別對左半邊區(qū)間也就是 [3,1,2] 和右半?yún)^(qū)間 [7,6,5,8] 執(zhí)行上訴過程，直至區(qū)間縮小為 1 也就是第三條，則此時所有的數(shù)據(jù)都有序。
簡單來說就是我們利用基準(zhǔn)數(shù)通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比基準(zhǔn)數(shù)小，另一部分記錄的關(guān)鍵字均比基準(zhǔn)數(shù)大，然后分別對這兩部分記錄繼續(xù)進(jìn)行分割，進(jìn)而達(dá)到有序。
我們現(xiàn)在應(yīng)該了解了快速排序的思想，那么大家還記不記得我們之前說過的歸并排序，他們兩個用到的都是分治思想，那他們兩個有什么不同呢？見下圖
注：這里我們以區(qū)間的第一個元素作為基準(zhǔn)數(shù)
雖然歸并排序和快速排序都用到了分治思想，但是歸并排序是自下而上的，先處理子問題，然后再合并，將小集合合成大集合，最后實現(xiàn)排序。
快速排序是由上到下的，先分區(qū)，然后再處理子問題。歸并排序雖然是穩(wěn)定的、時間復(fù)雜度為 O(nlogn) 的排序算法，但是它是非原地排序算法。我們前面講過，歸并之所以是非原地排序算法，主要原因是合并函數(shù)需要利用輔助數(shù)組保存元素。
快速排序通過設(shè)計巧妙的原地分區(qū)函數(shù)，可以實現(xiàn)原地排序，解決了歸并排序占用太多內(nèi)存的問題。
我們根據(jù)思想可知，快速排序算法的核心就是如何利用基準(zhǔn)數(shù)將記錄分區(qū)，這里我們主要介紹兩種容易理解的方法，一種是挖坑填數(shù)，另一種是利用雙指針?biāo)枷脒M(jìn)行元素交換。
下面我們先來介紹下挖坑填數(shù)的分區(qū)方法
基本思想是我們首先以序列的第一個元素為基準(zhǔn)數(shù)，然后將該位置挖坑，下面判斷 nums[hight] 是否大于基準(zhǔn)數(shù)，如果大于，則左移 hight 指針，直至找到一個小于基準(zhǔn)數(shù)的元素，將其填入之前的坑中，則 hight 位置會出現(xiàn)一個新的坑，此時移動 low 指針，找到大于基準(zhǔn)數(shù)的元素，填入新的坑中。不斷迭代直至完成分區(qū)。
大家直接看我們的視頻模擬吧，一目了然。
注：為了便于理解所以采取了挖坑的形式展示
是不是很容易就理解啦，下面我們直接看代碼吧。
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];
}
//基準(zhǔn)數(shù)放到合適的位置
nums[low] = pivot;
return low;
}
}
下面我們來看一下第二種交換方法的思路，原理一致，實現(xiàn)也比較簡單。
見下圖。
其實這種方法，算是對上面方法的挖坑填坑步驟進(jìn)行合并，low 指針找到大于 pivot 的元素，hight 指針找到小于 pivot 的元素，然后兩個元素交換位置，最后再將基準(zhǔn)數(shù)歸位。
兩種方法都很容易理解和實現(xiàn)，即使是完全沒有學(xué)習(xí)過快速排序的同學(xué)，理解了思想之后也能自己動手實現(xiàn)，下面我們繼續(xù)用視頻模擬下這種方法的執(zhí)行過程吧。
兩種方法都很容易實現(xiàn)，對我們非常友好，大家可以自己去 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);
}
//基準(zhǔn)值歸位
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;
}
}
快速排序的時間復(fù)雜度分析
快排也是用遞歸來實現(xiàn)的。所以快速排序的時間性能取決于快速排序的遞歸樹的深度。
如果每次分區(qū)操作，都能正好把數(shù)組分成大小接近相等的兩個小區(qū)間，那么此時的遞歸樹是平衡的，性能也較好，遞歸樹的深度也就和之前歸并排序求解方法一致。
我們每一次分區(qū)需要對數(shù)組掃描一遍，做 n 次比較，所以最優(yōu)情況下，快排的時間復(fù)雜度是 O(nlogn)。
但是大多數(shù)情況下我們不能劃分的很均勻，比如數(shù)組為正序或者逆序時，即 [1,2,3,4] 或 [4,3,2,1] 時，此時為最壞情況，那么此時我們則需要遞歸調(diào)用 n-1 次，此時的時間復(fù)雜度則退化到了 O(n^2)。
快速排序的空間復(fù)雜度分析
快速排序主要時遞歸造成的棧空間的使用，最好情況時其空間復(fù)雜度為O (logn),對應(yīng)遞歸樹的深度。最壞情況時則需要 n-1 次遞歸調(diào)用，此時空間復(fù)雜度為O(n)。
快速排序的穩(wěn)定性分析
快速排序是一種不穩(wěn)定的排序算法，因為其關(guān)鍵字的比較和交換是跳躍進(jìn)行的，見下圖。
此時無論使用哪一種方法，第一次排序后，黃色的 1 都會跑到紅色 1 的前面，所以快速排序是不穩(wěn)定的排序算法。
好啦，快速排序我們掌握的差不多了，下面我們一起來看看如何對其優(yōu)化吧。
快速排序的迭代寫法
該方法實現(xiàn)也是比較簡單的，借助了棧來實現(xiàn)，很容易實現(xiàn)。主要利用了先進(jìn)先出的特性，這里需要注意的就是入棧的順序，這里算是一個小細(xì)節(jié)，需要注意一下，其中分區(qū)函數(shù)和上面一致。大家只需看入棧出棧情況即可。
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;
}
}
快速排序優(yōu)化
三數(shù)取中法
我們在上面的例子中選取的都是 nums[low] 做為我們的基準(zhǔn)值，那么當(dāng)我們遇到特殊情況時呢？見下圖
我們按上面的方法，選取第一個元素做為基準(zhǔn)元素，那么我們執(zhí)行一輪排序后，發(fā)現(xiàn)僅僅是交換了 2 和 7 的位置，這是因為 7 為序列的最大值。
所以我們的 pivot 的選取尤為重要，選取時應(yīng)盡量避免選取序列的最大或最小值做為基準(zhǔn)值。則我們可以利用三數(shù)取中法來選取基準(zhǔn)值。
也就是選取三個元素中的中間值放到 nums[low] 的位置，做為基準(zhǔn)值。這樣就避免了使用最大值或最小值做為基準(zhǔn)值。
所以我們可以加上這幾行代碼實現(xiàn)三數(shù)取中法。
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] 位置做為基準(zhǔn)值，最大值放到 nums[hight],最小值放到 nums[mid],即 [4,2,3] 經(jīng)過上面代碼處理后，則變成了 [3,2,4]。
此時我們選取 3 做為基準(zhǔn)值，這樣也就避免掉了選取最大或最小值做為基準(zhǔn)值的情況。
三數(shù)取中法
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) {
//三數(shù)取中，大家也可以使用其他方法
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;
}
}
和插入排序搭配使用
我們之前說過，插入排序在元素個數(shù)較少時效率是最高的，沒有看過的同學(xué)可以去看一下之前的文章，所以當(dāng)元素數(shù)量較少時，快速排序反而不如插入排序好用。
所以我們可以設(shè)定一個閾值，當(dāng)元素個數(shù)大于閾值時使用快速排序，小于等于該閾值時則使用插入排序。我們設(shè)定閾值為 7 。
三數(shù)取中+插入排序
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) {
//三數(shù)取中，大家也可以使用其他方法
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;
}
}
好啦，我們的插入排序和快速排序的搭配使用就搞定啦。
我們繼續(xù)看下面這種情況
我們對其執(zhí)行一次排序后，則會變成上面這種情況，然后我們繼續(xù)對藍(lán)色基準(zhǔn)值的左區(qū)間和右區(qū)間執(zhí)行相同操作。也就是 [2,3,6,3,1,6] 和 [8,6] 。我們注意觀察一次排序的結(jié)果數(shù)組中是含有很多重復(fù)元素的，我們之前的優(yōu)化方式并不能很好的解決這種情況。
那么我們?yōu)槭裁床荒軐⑾嗤胤诺揭黄鹉?？這樣就能大大減小遞歸調(diào)用時的區(qū)間大小，見下圖。
這樣就減小了我們的左右區(qū)間大小，只需對區(qū)間 [3,1,2,4] 和 [8] 執(zhí)行相同操作即可，我們將數(shù)組切分成了三部分，小于基準(zhǔn)數(shù)的左區(qū)間，大于基準(zhǔn)數(shù)的右區(qū)間，等于基準(zhǔn)數(shù)的中間區(qū)間。
下面我們來看一下如何達(dá)到上面的情況，我們先來進(jìn)行視頻模擬，模擬之后應(yīng)該就能明白啦。
我們來剖析一下視頻，其實原理很簡單，我們利用探路指針也就是 i，遇到比 pivot 大的元素，則和 right 指針進(jìn)行交換，交換后 right 指向的元素肯定比 pivot 大，則 right--，但是，此時我們的 nums[i] 指向的元素并不知道情況，所以我們的 i 指針先不動，繼續(xù)判斷。
如果此時 nums[i] < pivot 則與 left 指針交換，注意此時我們的 left 指向的值肯定是等于 povit的，所以交換后我們要 left++,i++, nums[i] == pivot 時，僅需要 i++ 即可，繼續(xù)判斷下一個元素。我們也可以借助這個思想來解決經(jīng)典的荷蘭國旗問題。
好啦，我們下面直接看代碼吧。
三數(shù)取中+三向切分+插入排序
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;
}
//三數(shù)取中
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;
}
}
好啦，一些常用的優(yōu)化方法都整理出來啦，還有一些其他的優(yōu)化算法九數(shù)取中，優(yōu)化遞歸操作等因為不常用就不在這里進(jìn)行描述啦，
2021-02-02
2021-02-01
2021-01-27
2021-01-25
