Java 資料結構 - 快速排序

快速排序是一種高效的排序演算法，它基於將資料陣列劃分成更小的陣列。一個大的陣列被劃分成兩個陣列，其中一個數組包含小於指定值（例如，樞軸）的值，基於該值進行劃分，另一個數組包含大於樞軸值的值。

快速排序劃分一個數組，然後遞迴呼叫自身兩次來排序兩個生成的子陣列。對於大型資料集，該演算法非常高效，因為它的平均和最壞情況複雜度為 Ο(n2)，其中 n 是專案的數量。

演算法

基於我們對快速排序中劃分的理解，我們現在將嘗試編寫它的演算法，如下所示：

Step 1: Choose the highest index value has pivot.
Step 2: Take two variables to point left and right of the list excluding pivot.
Step 3: left points to the low index.
Step 4: right points to the high.
Step 5: while value at left is less than pivot move right.
Step 6: while value at right is greater than pivot move left.
Step 7: if both step 5 and step 6 does not match swap left and right.
Step 8: if left ≥ right, the point where they met is new pivot.

快速排序演算法

使用樞軸演算法遞迴地，我們最終得到儘可能小的分割槽。然後對每個分割槽進行快速排序處理。我們定義快速排序的遞迴演算法如下：

Step 1: Make the right-most index value pivot.
Step 2: partition the array using pivot value.
Step 3: quicksort left partition recursively.
Step 4: quicksort right partition recursively.

示例

import java.util.Arrays;

public class QuickSortExample {
   int[] intArray = {4,6,3,2,1,9,7};
   
   void swap(int num1, int num2) {
      int temp = intArray[num1];
      intArray[num1] = intArray[num2];
      intArray[num2] = temp;
   }
   int partition(int left, int right, int pivot) {
      int leftPointer = left -1;
      int rightPointer = right;

      while(true) {
         while(intArray[++leftPointer] < pivot) {
            // do nothing
         }
         while(rightPointer > 0 && intArray[--rightPointer] > pivot) {
            // do nothing
         }
         
         if(leftPointer >= rightPointer) {
            break;
         } else {
            swap(leftPointer,rightPointer);
         }
      }
      swap(leftPointer,right);
      
      // System.out.println("Updated Array: "); 
      return leftPointer;
   }
   void quickSort(int left, int right) {
      if(right-left <= 0) {
         return;   
      } else {
         int pivot = intArray[right];
         int partitionPoint = partition(left, right, pivot);
         quickSort(left,partitionPoint-1);
         quickSort(partitionPoint+1,right);
      }        
   }
   public static void main(String[] args) { 
      QuickSortExample sort = new QuickSortExample();
      int max = sort.intArray.length;
      System.out.println("Contents of the array :");
      System.out.println(Arrays.toString(sort.intArray));
      
      sort.quickSort(0, max-1);
      System.out.println("Contents of the array after sorting :");
      System.out.println(Arrays.toString(sort.intArray));
   }
}

輸出

Contents of the array :
[4, 6, 3, 2, 1, 9, 7]
Contents of the array after sorting :
[1, 2, 3, 4, 6, 7, 9]