快速排序（QuickSort）是一種高效的排序算法，採用分治法的策略將一個數列分為兩個子數列，步驟如下：
從數列中挑出一個元素，稱為「基準」（pivot）。
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割結束之後，對這個基準值的排序就已經完成。
遞迴地（recursive）將小於基準值元素的子數列和大於基準值元素的子數列排序。
下面是使用Java實現的快速排序函式：
java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi is partitioning index, arr[pi] is now at right place
int pi = partition(arr, low, high);
// Recursively sort elements before partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1); // Index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
// Utility function to print array of size n
static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
// Driver code
public static void main(String args[]) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("Sorted array: ");
printArray(arr);
}
}
在上述程式碼中，quickSort 函式接受三個參數：要排序的陣列 arr，陣列的起始位置 low，以及陣列的結束位置 high。partition 函式用於找到分割點並進行元素的交換。
這個實現的核心在於partition方法，它會根據基準值pivot將陣列分割成兩部分，並返回基準值的正確位置，然後quickSort方法會對基準值左側和右側的子陣列遞迴進行排序。
阿摩線上測驗
登入