Java 快速排序

快速排序（Quicksort）是一种高效的排序算法，采用分治法（Divide and Conquer）的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。以下是用Java实现的快速排序算法：

public class QuickSort {  // 主方法，用于测试快速排序  public static void main(String[] args) {  int[] array = {10, 7, 8, 9, 1, 5};  int n = array.length;  System.out.println("排序前的数组:");  printArray(array);  quickSort(array, 0, n-1);  System.out.println("排序后的数组:");  printArray(array);  }  // 快速排序方法  public static void quickSort(int[] array, int low, int high) {  if (low < high) {  // 找到分区点  int pi = partition(array, low, high);  // 递归地对左右子数组排序  quickSort(array, low, pi - 1);  quickSort(array, pi + 1, high);  }  }  // 分区方法  public static int partition(int[] array, int low, int high) {  int pivot = array[high];  // 选择最右边的元素作为枢轴  int i = (low - 1);  // i是较小元素的索引  for (int j = low; j < high; j++) {  // 如果当前元素小于或等于枢轴  if (array[j] <= pivot) {  i++;  // 交换array[i]和array[j]  int temp = array[i];  array[i] = array[j];  array[j] = temp;  }  }  // 交换array[i + 1]和array[high] (或枢轴)  int temp = array[i + 1];  array[i + 1] = array[high];  array[high] = temp;  return i + 1;  }  // 打印数组方法  public static void printArray(int[] array) {  int n = array.length;  for (int i = 0; i < n; ++i) {  System.out.print(array[i] + " ");  }  System.out.println();  }  
}

代码解释

1. 主方法 (main):
   • 创建一个数组并输出排序前的数组。
   • 调用 quickSort 方法对数组进行排序。
   • 输出排序后的数组。
2. 快速排序方法 (quickSort):
   • 如果 low 小于 high，则进行排序。
   • 调用 partition 方法获取分区点 pi。
   • 递归地对分区点前后的子数组进行排序。
3. 分区方法 (partition):
   • 选择数组的最后一个元素作为枢轴。
   • 初始化较小元素的索引 i。
   • 遍历数组，如果当前元素小于或等于枢轴，则交换 array[i] 和 array[j]。
   • 遍历完成后，将枢轴放到正确的位置（即 i + 1），并返回该位置。
4. 打印数组方法 (printArray):
   • 遍历数组并打印每个元素。

注意事项

• 枢轴的选择可以优化，例如随机选择枢轴或选择数组的中间元素作为枢轴，以减少最坏情况（例如已经有序的数组）下的性能下降。
• 快速排序的空间复杂度主要是递归调用栈，最坏情况下为 O(n)，但平均情况下较好。
• 快速排序的时间复杂度平均情况下为 O(n log n)，最坏情况下为 O(n^2)。