Java 快速排序算法实现及代码解析

/**

• 快速排序 */ public class QuickSort {

  /**

  • 快速排序算法
  • @param arr 待排序数组
  • @param left 数组左边界
  • @param right 数组右边界 */ public static void quickSort(int[] arr, int left, int right) { if (left < right) { // 分区，获取枢轴下标 int pivotIndex = partition(arr, left, right); // 递归排序左半区 quickSort(arr, left, pivotIndex - 1); // 递归排序右半区 quickSort(arr, pivotIndex + 1, right); } }

  /**

  • 分区函数
  • @param arr 待分区数组
  • @param left 数组左边界
  • @param right 数组右边界
  • @return 分区后枢轴所在下标 */ public static int partition(int[] arr, int left, int right) { // 选取待分区数组的最后一个元素作为枢轴 int pivot = arr[right]; // 定义左右指针 int i = left; int j = right - 1; while (true) { // 左指针向右移动，直到找到大于等于枢轴的元素 while (i < right && arr[i] < pivot) { i++; } // 右指针向左移动，直到找到小于等于枢轴的元素 while (j >= left && arr[j] > pivot) { j--; } // 如果左指针大于等于右指针，退出循环 if (i >= j) { break; } // 交换左右指针所指向的元素 swap(arr, i, j); } // 将枢轴放到正确的位置上 swap(arr, i, right); // 返回枢轴所在下标 return i; }

  /**

  • 交换数组中两个元素的位置
  • @param arr 待交换数组
  • @param i 下标i
  • @param j 下标j */ public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

  public static void main(String[] args) { int[] arr = {5, 7, 1, 3, 9, 2, 8, 4, 6}; quickSort(arr, 0, arr.length - 1); for (int num : arr) { System.out.print(num + " "); } } }