概念
快速排序?qū)儆诮粨Q排序，主要步驟是使用基準(zhǔn)元素進(jìn)行比較许师，把小于基準(zhǔn)元素的移動到一邊微渠，大于基準(zhǔn)元素的移動到另一邊逞盆。從而把數(shù)組分成兩部分，然后再從這兩部分中選取出基準(zhǔn)元素续扔，重復(fù)上面的步驟纱昧。過程如下：
紫色：基準(zhǔn)元素
綠色：大于基準(zhǔn)元素
黃色：小于基準(zhǔn)元素
這種思路叫做分治法识脆。
基準(zhǔn)元素
基準(zhǔn)元素的選取可隨機選取灼捂。下面使用中我會使用第一位的元素作為基準(zhǔn)元素悉稠。
排序過程
排序拆分過程如下圖：
紫色為基準(zhǔn)元素的猛，（每一輪都重新選蓉宰稹）
綠色為其他元素
第一輪
第二輪
第三輪
如上圖所示：
若元素個數(shù)為n，因為排序過程中需要和全部元素都比較一遍躏哩，所以時間復(fù)雜度為O(n)震庭，
而平均情況下排序輪次需要logn輪你雌，因此快速排序的平均時間復(fù)雜度為O(nlogn)拨拓。
排序的實現(xiàn)方法
實現(xiàn)方法有雙邊循環(huán)法和單邊循環(huán)法
雙邊循環(huán)法
首選選取基準(zhǔn)元素(pivot)4渣磷，并設(shè)置指針left和right醋界，指向數(shù)組最左和最右兩個元素提完，如下：
第一次循環(huán)逐样，先從right指針指向的數(shù)據(jù)(rightData)開始和基準(zhǔn)元素比較
若 rightData >= pivot打肝，則right指針向左移動粗梭，若 rightData < pivot断医，則right指針不移動，切換到left指針
left指針指向數(shù)據(jù)(leftData)與基準(zhǔn)元素比較酷宵，若 leftData <= pivot浇垦，則left指針向右移動男韧，若 leftData > pivot默垄，交換left和right指向的元素口锭。
第一輪指針移動完后介杆，得到如下結(jié)構(gòu)：
然后 left和right指向的元素進(jìn)行交換：
第一輪循環(huán)結(jié)束，重新切換到right指針赴背，重復(fù)上述步驟凰荚。
第二輪循環(huán)后便瑟，得：
第三輪循環(huán)后胳徽，得：
第四輪循環(huán)后养盗，得：
判斷到left和right指針指向同一個元素往核，指針停止移動聂儒，使pivot和指針元素進(jìn)行交換衩婚，得：
宣告該輪循環(huán)結(jié)束效斑，并根據(jù)Pivot元素切分為兩部分缓屠，這兩部分的數(shù)組再根據(jù)上述步驟進(jìn)行操作敌完。
實現(xiàn)代碼
public class DoubleSort {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
//遞歸結(jié)束條件
if (startIndex >= endIndex) {
return;
}
// 基準(zhǔn)元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根據(jù)基準(zhǔn)元素，分成兩部分進(jìn)行遞歸排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
public static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一個元素為基準(zhǔn)元素什湘，也可以隨機抽取
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
while (left != right) {
// 控制right指針比較并左移
while (left < right && arr[right] >= pivot) {
right--;
}
// 控制left指針比較并右移
while (left < right && arr[left] <= pivot) {
left++;
}
// 交換left和right指針?biāo)赶虻脑? if (left < right) {
int temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
}
}
arr[startIndex] = arr[left];
arr[left] = pivot;
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));
}
}
單邊循環(huán)法
雙邊循環(huán)法從數(shù)組的兩邊比較并交換元素禽炬，而單邊循環(huán)法則從數(shù)組的一邊遍歷，一直往后比較和交換，實現(xiàn)起來更加的簡單热幔。
過程如下：
首先也是選取基準(zhǔn)元素pivot（可以隨機選擇）
設(shè)置一個mark指針指向數(shù)組的起始位置绎巨，代表小于基準(zhǔn)元素的區(qū)域邊界（不理解的就把它理解成是等會用來交換元素的就好了）
原始數(shù)組如下：
從基準(zhǔn)元素下一位開始遍歷數(shù)組
如果該元素大于基準(zhǔn)元素场勤，繼續(xù)往下遍歷
如果該元素小于基準(zhǔn)元素歼跟，mark指針往右移哈街，因為小于基準(zhǔn)元素的區(qū)域邊界增大了1（即小于基準(zhǔn)元素的多了1位），所以mark就 +1她倘，并且該元素和mark指向元素進(jìn)行交換硬梁。
遍歷到元素3時胞得，因為3 < 4懒震，所以mark右移
然后交換元素
然后就繼續(xù)遍歷个扰，根據(jù)上面的步驟進(jìn)行判斷递宅，后面的過程就不寫了苍狰。
實現(xiàn)代碼
public class SingleSort {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
//遞歸結(jié)束條件
if (startIndex >= endIndex) {
return;
}
// 基準(zhǔn)元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根據(jù)基準(zhǔn)元素淋昭，分成兩部分進(jìn)行遞歸排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
/**
* 分治（單邊循環(huán)法）
* @param arr
* @param startIndex
* @param endIndex
* @return
*/
public static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一個元素為基準(zhǔn)元素翔忽，也可以隨機抽取
int pivot = arr[startIndex];
int mark = startIndex;
for(int i = startIndex + 1; i< arr.length; i++) {
if (pivot < arr[i]) {
continue;
}
mark ++;
int temp = arr[mark];
arr[mark] = arr[i];
arr[i] = temp;
}
arr[startIndex] = arr[mark];
arr[mark] = pivot;
return mark;
}
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));
}
}
總結(jié)
本人也是初次接觸算法，慢慢的去理解算法的思路和實現(xiàn)過程后胡野，真是為自己以往寫的算法感到羞愧。該文章也是為了加深自己對快排算法的印象龙巨，若文章有不足之處旨别，懇請各位在下方留言補充耘眨。感謝各位的閱讀。Thanks?(?ω?)?胆屿。
參考資料：《小灰的算法之旅》 第四章非迹。
個人博客網(wǎng)址： https://colablog.cn/
如果我的文章幫助到您，可以關(guān)注我的微信公眾號憎兽，第一時間分享文章給您
