一看就懂的快速排序
概念
快速排序屬於交換排序，主要步驟是使用基準元素進行比較，把小於基準元素的移動到一邊，大於基準元素的移動到另一邊。從而把數組分成兩部分，然後再從這兩部分中選取出基準元素，重複上面的步驟。過程如下：
紫色：基準元素
綠色：大於基準元素
黃色：小於基準元素
這種思路叫做分治法。
基準元素
基準元素的選取可隨機選取。下面使用中我會使用第一位的元素作為基準元素。
排序過程
排序拆分過程如下圖：
紫色為基準元素，（每一輪都重新選取）
綠色為其他元素
第一輪
第二輪
第三輪
如上圖所示：
若元素個數為n，因為排序過程中需要和全部元素都比較一遍，所以時間複雜度為O(n)，
而平均情況下排序輪次需要logn輪，因此快速排序的平均時間複雜度為O(nlogn)。
排序的實現方法
實現方法有雙邊循環法和單邊循環法
雙邊循環法
首選選取基準元素(pivot)4，並設置指針left和right，指向數組最左和最右兩個元素，如下：
第一次循環，先從right指針指向的數據(rightData)開始和基準元素比較
若 rightData >= pivot，則right指針向左移動，若 rightData < pivot，則right指針不移動，切換到left指針
left指針指向數據(leftData)與基準元素比較，若 leftData < pivot，則left指針向右移動，若 leftData > pivot，交換left和right指向的元素。
第一輪指針移動完后，得到如下結構：
然後 left和right指向的元素進行交換：
第一輪循環結束，重新切換到right指針，重複上述步驟。
第二輪循環后，得：
第三輪循環后，得：
第四輪循環后，得：
判斷到left和right指針指向同一個元素，指針停止移動，使pivot和指針元素進行交換，得：
宣告該輪循環結束，並根據Pivot元素切分為兩部分，這兩部分的數組再根據上述步驟進行操作。
實現代碼
public class DoubleSort {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
//遞歸結束條件
if (startIndex >= endIndex) {
return;
}
// 基準元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根據基準元素，分成兩部分進行遞歸排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
public static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一個元素為基準元素，也可以隨機抽取
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指針所指向的元素
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));
}
}單邊循環法
雙邊循環法從數組的兩邊比較並交換元素，而單邊循環法則從數組的一邊遍歷，一直往後比較和交換，實現起來更加的簡單。
過程如下：
首先也是選取基準元素pivot（可以隨機選擇）
設置一個mark指針指向數組的起始位置，代表小於基準元素的區域邊界（不理解的就把它理解成是等會用來交換元素的就好了）
原始數組如下：
從基準元素下一位開始遍曆數組
如果該元素大於基準元素，繼續往下遍歷
如果該元素小於基準元素，mark指針往右移，因為小於基準元素的區域邊界增大了1（即小於基準元素的多了1位），所以mark就 +1，並且該元素和mark指向元素進行交換。
遍歷到元素3時，因為3 < 4，所以mark右移
然後交換元素
然後就繼續遍歷，根據上面的步驟進行判斷，後面的過程就不寫了。
實現代碼
public class SingleSort {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
//遞歸結束條件
if (startIndex >= endIndex) {
return;
}
// 基準元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根據基準元素，分成兩部分進行遞歸排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
/**
* 分治（單邊循環法）
* @param arr
* @param startIndex
* @param endIndex
* @return
*/
public static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一個元素為基準元素，也可以隨機抽取
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));
}
}總結
本人也是初次接觸算法，慢慢的去理解算法的思路和實現過程后，真是為自己以往寫的算法感到羞愧。該文章也是為了加深自己對快排算法的印象，若文章有不足之處，懇請各位在下方留言補充。感謝各位的閱讀。Thanks(･ω･)ﾉ。
參考資料： 第四章。
個人博客網址： https://colablog.cn/
如果我的文章幫助到您，可以關注我的微信公眾號，第一時間分享文章給您
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】
※想知道網站建置、網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計及後台網頁設計
※不管是台北網頁設計公司、台中網頁設計公司，全省皆有專員為您服務
※Google地圖已可更新顯示潭子電動車充電站設置地點!!
