简单的快速排序

快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法（Divide and Conquer），即把一个大问题分解成若干个小问题来解决，最终将小问题的结果合并得到原问题的解。在这个过程中，快速排序通过选取一个“基准”元素，将数组分成两部分，一部分的所有元素都小于基准，另一部分的所有元素都大于基准，然后对这两部分再进行同样的操作，直到所有元素都在正确的位置上。 在Java中实现快速排序，我们需要定义一个方法来执行这个过程。下面是一个简化的快速排序算法的Java实现： ```java public class QuickSort { 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); } } private static int partition(int[] arr, int low, int high) { // 选择最后一个元素作为基准 int pivot = arr[high]; // i是小于基准的元素的指针 int i = low - 1; for (int j = low; j < high; j++) { // 如果当前元素小于或等于基准 if (arr[j] <= pivot) { i++; // 交换元素 int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // 将基准放到正确的位置 int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; } public static void main(String[] args) { int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6}; quickSort(arr, 0, arr.length - 1); System.out.println("Sorted array:"); for (int num : arr) { System.out.print(num + " "); } } } ``` 在这个实现中，`quickSort`方法是主排序函数，它接受一个整型数组和两个索引，分别表示数组的起始和结束位置。`partition`方法负责将数组分为两部分，并返回基准元素的新位置。`main`方法展示了如何调用快速排序并打印排序后的结果。 快速排序的平均时间复杂度为O(n log n)，在最坏情况下（例如输入数组已排序或逆序）为O(n^2)，但这种情况很少出现。由于快速排序的常数因子较小，实际运行速度通常快于其他O(n log n)的排序算法，如归并排序。此外，快速排序在原地排序，不需要额外的存储空间，这也是其优势之一。 在实际应用中，快速排序通常与其他算法结合，比如在数据量小到一定程度时改用插入排序，以减少递归调用和提高效率。另外，对于具有大量重复元素的数组，可以使用三向切分的快速排序版本，以进一步优化性能。