快速排序（QuickSort）是一种高效的比较排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想基于分治策略（divide and conquer）：
选择基准（Pivot）： 快速排序首先选择待排序数组中的一个元素作为基准。这个基准通常是数组中的某个固定位置的元素，也可以是随机选取的一个元素，或者通过某种策略选取以获得更好的平均性能。
分区（Partitioning）： 接下来，算法将数组中的所有其他元素与基准进行比较，将小于基准的元素放在基准的左边，大于基准的元素放在基准的右边。这个过程完成后，基准处于最终排序后它应有的位置，而且左右两侧的元素都比基准更加有序。
递归排序子序列： 然后，对基准左右两侧的子序列分别进行快速排序。即对基准左边的子数组执行快速排序，对基准右边的子数组也执行快速排序。这个过程会一直递归下去，直到子数组只剩下一个元素或者为空，这时认为子数组本身就是有序的。
终止条件： 当递归到达叶子节点，也就是子数组的大小为1或0时，递归结束。
快速排序算法的关键在于其分区过程，它能够保证每次都能缩小问题规模，理论上平均时间复杂度为O(n log n)，在实践中也非常高效。然而，最坏情况下（比如对于已经完全有序或完全逆序的输入），快速排序的时间复杂度会上升至O(n²)，但通过对基准的选择进行优化（如三数取中法、随机化版本），可以在大多数实际场景下避免这种情况的发生。同时，快速排序是非稳定的排序算法，即相等元素的相对顺序可能在排序后改变。
以下是Java实现快速排序算法的一个简单版本：
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// Partition the array by finding the pivot index
int pivotIndex = partition(arr, low, high);
// Recursively sort elements on both sides of the pivot
quickSort(arr, low, pivotIndex - 1); // Before pivot
quickSort(arr, pivotIndex + 1, high); // After pivot
}
}
private static int partition(int[] arr, int low, int high) {
// Choose the last element as pivot
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 or equal to 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;
}
// Driver method to test above
public static void main(String args[]) {
int[] arr = {9, 2, 4, 7, 3, 8, 1, 5, 6};
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("Sorted array: ");
for (int i : arr) {
System.out.print(i + " ");
}
}
}这段代码首先定义了一个quickSort方法，接受数组和两个索引作为参数，分别表示待排序数组和排序范围的起始和结束位置。partition方法负责划分数组，找到基准值的最终位置并将小于基准值的元素移到基准值的左侧。接着，通过递归调用quickSort方法，分别对基准值左右两侧的子数组进行排序。主方法中初始化了一个测试数组并对其实行快速排序，最后输出排序后的数组。
原文链接: https://www.yukx.com/arithmetic/article/details/2471.html 优科学习网快速排序算法-（快排）
