普通快排

簡介

快速排序是一種高效的排序算法，利用分治的思想進行排序。它的基本原理是在待排序的n個數據中任取一個數據為分區標準，把所有小于該排序碼的數據移到左邊，把所有大于該排序碼的數據移到右邊，中間放所選記錄，稱之為一趟排序。然后，對前后兩個子序列重復上述過程，直到所有記錄都排好序。通俗點說，大致過程是對于一個無序序列，找到一個"哨兵數"，將序列中所有比哨兵數小的數字都移在哨兵數的左邊，所有比哨兵數大的數字都移在哨兵數的右邊；然后分別對哨兵數左邊和右邊再使用同樣的方法找到新的哨兵數，并再次進行分類，直到集合不可分割為止。

過程

實現快速排序的過程大致如下：

1. 從數組的中間位置開始，取出一個數字作為臨時變量；
2. 然后再從數組的右邊開始遍歷，尋找一個值比臨時變量小的數，挖出這個數來，對上一個坑進行填坑；
3. 然后從數組前面遍歷，尋找一個比臨時變量大的數，填上面的坑。

以上是快速排序的基本步驟，需要注意的是，在實際的編程實現中，還需要處理一些特殊情況，例如當待排序數組為空或只有一個元素時。

public class QuickSort {  public static void quickSort(int[] arr, int left, int right) {  if (left < right) {  int pivotIndex = partition(arr, left, right);  quickSort(arr, left, pivotIndex - 1);  quickSort(arr, pivotIndex + 1, right);  }  }  private static int partition(int[] arr, int left, int right) {  int pivot = arr[right]; // 選擇最右邊的數作為哨兵數  int i = left - 1; // i指向比哨兵數小的數所在的位置  for (int j = left; j < right; j++) {  if (arr[j] <= pivot) {  i++;  swap(arr, i, j); // 將比哨兵數小的數移到左邊  }  }  swap(arr, i + 1, right); // 將哨兵數移到正確的位置上  return i + 1; // 返回哨兵數的位置  }  private static void swap(int[] arr, int i, int j) {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  
}

?運行結果

int[] arr = {9, 2, 7, 5, 1};  
QuickSort.quickSort(arr, 0, arr.length - 1);  
System.out.println(Arrays.toString(arr)); // 輸出 [1, 2, 5, 7, 9]

省下一個變量空間的快排

步驟

這個實現的基本步驟是：

1. 選擇一個"哨兵數"（這里選擇的是數組的第一個元素），并將數組分為兩部分，一部分是小于哨兵數的元素，另一部分是大于哨兵數的元素。這個操作由partition函數完成。
2. 對小于哨兵數的元素和大于哨兵數的元素分別進行遞歸排序。也就是說，對這兩部分再分別調用quickSort函數進行排序。

在partition函數中，核心的思路是利用兩個指針，一個從數組的右邊開始向左移動，另一個從數組的左邊開始向右移動。當左邊的指針找到的數小于等于哨兵數，而右邊的指針找到的數大于哨兵數時，交換這兩個數。這樣，經過一段時間后，左邊的指針就會碰到第一個小于哨兵數的數，右邊的指針就會碰到第一個大于哨兵數的數。這個時候，將哨兵數放到這兩個數的中間位置。這樣，就完成了一趟排序。

詳細講解

讓我來為你講解一下這段Java代碼實現的快速排序算法。

首先，我們定義了一個名為quickSort的靜態方法，它接受一個整數數組arr以及兩個索引low和high作為參數。這個方法用于對數組的一部分進行排序，其中low是起始索引，而high是結束索引。

在quickSort方法中，我們首先檢查low是否小于high。如果不是，說明數組已經排好序了，我們直接返回。

接下來，我們調用partition方法來對數組進行分區。這個方法會選擇一個"哨兵數"，然后將數組分為兩部分：一部分是小于哨兵數的元素，另一部分是大于哨兵數的元素。這個過程是通過交換元素的位置來實現的。

然后，我們對小于哨兵數的元素和大于哨兵數的元素分別遞歸調用quickSort方法進行排序。這樣，我們就可以保證在每一層遞歸中，都比上一層的排序更加精確。

接下來，我們來看看partition方法的實現。在這個方法中，我們選擇數組的最后一個元素作為哨兵數。然后，我們使用兩個指針，一個從數組的左邊開始向右移動，另一個從數組的右邊開始向左移動。當左邊的指針找到的數小于等于哨兵數，而右邊的指針找到的數大于哨兵數時，交換這兩個數。這樣，經過一段時間后，左邊的指針就會碰到第一個小于哨兵數的數，右邊的指針就會碰到第一個大于哨兵數的數。這個時候，將哨兵數放到這兩個數的中間位置。這樣，就完成了一趟排序。

最后，返回的是排好序的數組。你可以使用循環遍歷輸出數組中的每個元素來查看排序結果。

?

package com.learn;public class QuickSort {public static void main(String[] args) {int[] arr = {3, 8, 2, 5, 1, 4, 7, 6};quickSort(arr, 0, arr.length - 1);for (int i : arr) {System.out.print(i + " ");}}public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high);quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex + 1, high);}}public static int partition(int[] arr, int low, int high) {int pivot = arr[low];//會有優化while (low < high) {while (low < high && arr[high] >= pivot) {high--;}arr[low] = arr[high];while (low < high && arr[low] <= pivot) {low++;}arr[high] = arr[low];}arr[low] = pivot;return low;}
}

?

?

?