??個人博客：www.hellocode.top
??Java知識導航：Java-Navigate
??CSDN：HelloCode.
??知乎：HelloCode
??掘金：HelloCode
?如有問題，歡迎指正，一起學習~~
快速排序（Quick Sort）是一種高效的排序算法，是對冒泡排序的優(yōu)化。它采用分治法（Divide and Conquer）的思想，將待排序序列不斷分割成較小的子序列，然后對每個子序列進行排序，最后合并得到有序的序列?？焖倥判蛟诖蠖鄶登闆r下具有優(yōu)異的性能，是許多常見排序算法中最快的之一。
基本思想
這里的動畫用大佬五分鐘學算法的圖，很清晰
- 選擇一個基準元素（pivot）作為參考點。
- 將所有比基準元素小的元素移到基準元素的左邊，將所有比基準元素大的元素移到基準元素的右邊。此過程稱為分區(qū)（partitioning）。
- 對基準元素左右兩邊的子序列遞歸地進行相同的快速排序，直到子序列的大小為1或0，表示子序列已經有序。
如上圖所示，快速排序的基本思想就是選取一個基準數，將基準數小的都放在左邊，大的都放在右邊，也就是每次循環(huán)都會確定出基準數應該在的正確位置。
代碼實現
對應在代碼層面，需要使用到遞歸法來實現，對于快速排序來說，遞歸相對還是很容易想到的
/**
* @author HelloCode
* @blog https://www.hellocode.top
* @date 2023年08月08日 21:14
*/
public class QuickSort {
public static void quickSort(int[] arr) {
// 特殊情況處理
if (arr == null || arr.length == 0 || arr.length == 1) {
return;
}
// 遞歸入口
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int left, int right) {
// 遞歸出口
if (left > right) {
return;
}
// 初始化雙指針
int i = left, j = right;
// 選取基準數
int base = arr[left];
while (i != j) {
// （注意?。。。。挠疫呴_始
// 找比基準數小的
while (i < j && arr[j] >= base) {
j--;
}
// 從左邊找比基準數大的
while (i < j && arr[i] <= base) {
i++;
}
// 交換i j
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 基準數歸位(此時i == j)
arr[left] = arr[i];
arr[i] = base;
// 開始左右兩邊分別快排
sort(arr, left, i - 1);
sort(arr, i + 1, right);
}
}
這里先移動j還是先移動i主要是需要看基準數選取的位置，如果選最左邊的數，就需要先移動j（確保i == j 時對應的值是小于基準數的，再把基準數和該數交換，符合排序規(guī)則）
如果選取的基準數是最右邊，則先移動i指針（確保 i == j 時對應的值是大于基準數的）
測試：
/**
* @author HelloCode
* @blog https://www.hellocode.top
* @date 2023年08月08日 21:14
*/
public class Test {
public static void main(String[] args) {
int[] arr = {21, 13, 4, 10, 7, 65, 32, 15, 32, 19, 33, 65, 89, 72, 12};
System.out.println("排序前：" + Arrays.toString(arr));
QuickSort.quickSort(arr);
System.out.println("排序后：" + Arrays.toString(arr));
}
}
優(yōu)化
快排的優(yōu)化主要需要關注基準數的選取，如果待排序數組整體偏降序，此時還選最左側的為基準數的話，效率就相對慢一些，所以選取一個好的基準數可以讓快排的效率更加穩(wěn)定~
主要的方法有以下幾種：
- 隨機選擇基準元素：選擇隨機的基準元素可以降低最壞情況的概率，進而提高算法性能。
- 三數取中法：在選取基準元素時，不是簡單地選取第一個或最后一個元素，而是選擇中間元素、第一個元素和最后一個元素中的中位數作為基準元素，也可以降低最壞情況的概率。
這里基準數的選取可以很巧妙，還有很多種其他方法，都可以降低最壞情況的發(fā)生，本文以三數取中法為例：
/**
* @author HelloCode
* @blog https://www.hellocode.top
* @date 2023年08月08日 21:14
*/
public class QuickSort {
public static void quickSort(int[] arr) {
// 特殊情況處理
if (arr == null || arr.length == 0 || arr.length == 1) {
return;
}
// 遞歸入口
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int left, int right) {
// 遞歸出口
if (left > right) {
return;
}
// 初始化雙指針
int i = left, j = right;
// 選取基準數
getBase(arr, left, right);
int base = arr[left];
while (i != j) {
// （注意！?。。。挠疫呴_始
// 找比基準數小的
while (i < j && arr[j] >= base) {
j--;
}
// 從左邊找比基準數大的
while (i < j && arr[i] <= base) {
i++;
}
// 交換i j
if (i < j) {
swap(arr, i, j);
}
}
// 基準數歸位(此時i == j)
arr[left] = arr[i];
arr[i] = base;
// 開始左右兩邊分別快排
sort(arr, left, i - 1);
sort(arr, i + 1, right);
}
// 取三點中間值（最終會移動到left位置，這樣可以不改變原有代碼）
private static void getBase(int[] arr, int left, int right) {
// 這里可以防止溢出且使用 >> 效率相對能高一些
// 等價于 (left + right) / 2
int mid = left + ((right - left) >> 1);
// 確保第一個元素最小
if (arr[left] > arr[right]) {
swap(arr, left, right);
}
// 確保最后一個元素最大
if (arr[mid] > arr[right]) {
swap(arr, mid, right);
}
// 確定mid就是中間值，交換到最左邊
if (arr[left] < arr[mid]) {
swap(arr, left, mid);
}
System.out.println("基準數為：" + arr[left]);
}
// 交換數組兩下標元素位置
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
測試：文章來源：http://www.zghlxwxcb.cn/news/detail-642592.html
/**
* @author HelloCode
* @blog https://www.hellocode.top
* @date 2023年08月07日 21:02
*/
public class Test {
public static void main(String[] args) {
int[] arr = {21, 13, 4, 10, 7, 65, 32, 15, 32, 19};
System.out.println("排序前：" + Arrays.toString(arr));
BubbleSort.bubbleSortOptimized1(arr);
System.out.println("排序后：" + Arrays.toString(arr));
}
}
排序前：[21, 13, 4, 10, 7, 65, 32, 15, 32, 19, 33, 65, 89, 72, 12]
基準數為：15
基準數為：7
基準數為：4
基準數為：12
基準數為：10
基準數為：13
基準數為：32
基準數為：21
基準數為：19
基準數為：32
基準數為：65
基準數為：33
基準數為：65
基準數為：72
基準數為：89
排序后：[4, 7, 10, 12, 13, 15, 19, 21, 32, 32, 33, 65, 65, 72, 89]
總結
優(yōu)點
- 高效性：快速排序是一種高效的排序算法，在大多數實際情況下，它的性能通常比其他常見排序算法（如冒泡排序、插入排序）更好。
- 原地排序：快速排序是原地排序算法，不需要額外的輔助空間，只需在原始數組上進行交換操作。
缺點
- 最壞情況下的性能：當待排序序列已經基本有序或完全逆序時，快速排序的時間復雜度退化為 O(n^2)，導致性能下降。這是因為基準元素的選擇可能導致分區(qū)不平衡，使得分區(qū)操作不再能有效地減少問題規(guī)模。
- 不穩(wěn)定性：快速排序是一種不穩(wěn)定的排序算法，意味著相等元素的相對順序在排序后可能發(fā)生變化。這在某些情況下可能導致問題，特別是對于復雜對象的排序，需要額外的處理來保持穩(wěn)定性。
復雜度
- 時間復雜度：快速排序的平均時間復雜度為O(n log n)，最壞情況下為O(n^2)。
- 空間復雜度：快速排序是原地排序算法，空間復雜度為O(log n)。
適用于處理大規(guī)模數據集的排序，尤其在平均情況下，快速排序的性能較優(yōu)。但在處理已經有序或近乎有序的數據集時，快速排序的性能可能會下降，這時候其他穩(wěn)定的排序算法可能更合適。文章來源地址http://www.zghlxwxcb.cn/news/detail-642592.html
到了這里，關于【數據結構與算法】十大經典排序算法-快速排序的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
