說在前頭：本人為大二在讀學生，書寫文章的目的是為了對自己掌握的知識和技術進行一定的記錄，同時樂于與大家一起分享，因本人資曆尚淺，能力有限，文章難免存在一些錯漏之處，還請閱讀此文章的大牛們見諒與斧正。若在閱讀時有任何的問題，也可通過評論提出，本人将根據自身能力對問題進行一定的解答。
前言
快速排序（Quicksort）是對冒泡排序算法的一種改進，其算法的時間複雜度為O(Nlog2N)，算法效率較高。但算法不夠穩定，當資料順序較為整齊時，效率将會降低，最壞的情況會達到O(N2)。
01—算法思想
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：設定一個基準的分界值（一般取最後一個或最後一個），通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。（下圖所示是第一輪排序的流程展示圖）
當基準點選用最左側的資料45時，45需要與最右側的資料進行對比，若最右側的資料小于45時，則該資料需要與45發生位置的互換，否則無需做任何操作，如上圖第一行的情況。
當基準點45經過位置的互換來到最右側時，此時需要與最左側未比較過的資料進行比較，若左側的資料大于45則需要與45發生位置的互換，否則無需做任何操作，如上圖第二行。
如此一直往複，直到基準點45的左側所有資料都小于45，右側都大于45時，該輪排序才結束（如上圖最後一行）。此時隻是一輪排序的結束，算法并未結束，因為45左右兩側的資料并未完成排序，我們還需要對左右兩側的數組再次進行快速排序，直到所有的資料都有序為止。
02—具體實作代碼
Fast.java
package com.bosen.fast;
/**
* <p>快速排序</p>
* @author Bosen 2021/5/29 22:26
*/
public class Fast {
/*
* 待排序的數組
*/
private int[] array;
private static int count = 0;
public Fast(int[] array) {
this.array = array;
}
/*
* 執行排序
*/
public void sort() {
display("初始狀态：");
recursiveSort(0, array.length-1);
}
/*
* 使用遞歸的方式
*/
public void recursiveSort(int low, int high) {
if (low >= high) return;
int tempLow = low;
int tempHigh = high;
int standard = array[low]; // 第一個元素為基準點
while (low < high) {
while (low < high && array[high] >= standard) {
high--;
}
swap(low, high);
while (low < high && array[low] <= standard) {
low++;
}
swap(low, high);
}
display("第"+(++count)+"輪排序：");
recursiveSort(tempLow, low-1);
recursiveSort(low+1, tempHigh);
}
/*
* 交換資料位置
*/
public void swap(int low, int high) {
int temp = array[high];
array[high] = array[low];
array[low] = temp;
}
/*
* 列印排序情況
*/
public void display(String msg) {
System.out.print(msg);
for (int i : array) {
System.out.print("\t"+i);
}
System.out.println();
}
}
Test.java
package com.bosen.fast;
public class Test {
public static void main(String[] args) {
int[] array = {45, 12, 23, 34, 78, 21, 98, 11};
Fast fast = new Fast(array);
fast.sort();
}
}
輸出結果：
總結
此篇章節，主要介紹了快速排序算法的算法思想，并通過具體代碼來展現。在下一篇中，我們将來講述希爾排序算法，感興趣的小夥伴們可以先點個關注哦！
👇掃描二維碼關注