跳到主要内容

Java程序实现快速排序算法

要理解这个示例，你应该具备以下 Java 编程主题的知识：

Java 中的快速排序​

快速排序算法基于分而治之的方法，通过选择一个基准元素将数组划分为子数组。

在划分数组时，应该这样定位基准元素：使得小于基准的元素放在左边，大于基准的元素放在右边。

对左右子数组重复相同的过程。最后，将排序好的元素组合成一个排序数组。

要了解更多，请访问 快速排序算法。

示例：Java 程序实现快速排序算法​

import java.util.Arrays;

class Quicksort {

  // 查找分区位置的方法
  static int partition(int array[], int low, int high) {

    // 选择最右边的元素作为基准
    int pivot = array[high];

    // 指向大于基准的元素的指针
    int i = (low - 1);

    // 遍历所有元素
    // 将每个元素与基准进行比较
    for (int j = low; j < high; j++) {
      if (array[j] <= pivot) {

        // 找到比基准小的元素
        // 与指针 i 指向的较大元素交换
        i++;

        // 交换 i 和 j 的元素
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }

    }

    // 将基准元素与指针 i 指向的较大元素交换
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;

    // 返回分区完成的位置
    return (i + 1);
  }

  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);
    }
  }
}

// 主类
class Main {
  public static void main(String args[]) {

    int[] data = { 8, 7, 2, 1, 0, 9, 6 };
    System.out.println("未排序的数组");
    System.out.println(Arrays.toString(data));

    int size = data.length;

    // 对数组 data 调用 quicksort()
    Quicksort.quickSort(data, 0, size - 1);

    System.out.println("按升序排序的数组 ");
    System.out.println(Arrays.toString(data));
  }
}

输出

未排序的数组
[8, 7, 2, 1, 0, 9, 6]
按升序排序的数组
[0, 1, 2, 6, 7, 8, 9]

这里，数组的元素按升序排序。如果我们想按降序排序元素，可以在 for 循环中更改代码为：

// 小于号改为大于号
if (array[j] >= pivot) {
最后于 更新