HOWTO · Java

在 Java 中不使用 sort() 方法对数组进行排序

了解如何在不使用 sort() 方法的情况下在 Java 中对数组进行排序

本页内容

在 Java 中,无需调用 Arrays.sort(),只要比较数组元素并自行调整它们的位置,就能对数组排序。学习排序原理,或作业要求手动实现时,这种做法很有帮助。Java 的 Arrays.toString() 可以显示数组,但不会对数组排序。

下面的示例都按升序排列整数数组。冒泡排序、选择排序和插入排序比较直观;归并排序和快速排序则展示了递归分治方法。每段代码都是完整的 Java 程序。随附的运行证据显示,五个示例的结果相同:[11, 12, 22, 25, 34, 64, 90]。

在 Java 中不使用 Arrays.sort() 对数组排序

排序算法会改变数组元素的位置,直到它们符合所需顺序。若要按整数升序排列,基本做法是比较数值,并将较小值移到较大值之前。下面的算法以不同方式实现这一规则。除了归并排序的实现会在合并时使用临时数组,其余算法都会直接修改输入数组。

例如,数组初始值为 {64, 34, 25, 12, 22, 11, 90},目标是将其排成 {11, 12, 22, 25, 34, 64, 90}。每种实现都刻意不调用 Arrays.sort();Arrays.toString() 仅用于格式化数组,以便显示。

冒泡排序

冒泡排序会反复扫描相邻元素对。如果左侧的值大于右侧的值,就交换两者。每完成一轮扫描,未排序部分中的最大值就会移到末尾。如果某一轮没有发生交换,swapped 标志会让循环提前结束。此算法最坏情况下的时间复杂度为 O(n²),因此这个实现更适合小型输入或演示用途。

每段代码都声明了一个名为 Main 的类,因此请一次保存并运行一个示例,并将文件命名为 Main.java。运行此示例:

本节中的代码以及显示的标签或输出仍为英文。

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(values);
    System.out.println(Arrays.toString(values));
  }

  static void bubbleSort(int[] values) {
    for (int end = values.length - 1; end > 0; end--) {
      boolean swapped = false;
      for (int i = 0; i < end; i++) {
        if (values[i] > values[i + 1]) {
          int temp = values[i];
          values[i] = values[i + 1];
          values[i + 1] = temp;
          swapped = true;
        }
      }
      if (!swapped) {
        break;
      }
    }
  }
}
[11, 12, 22, 25, 34, 64, 90]

选择排序

选择排序在概念上将数组分为已排序的前缀和剩余的未排序元素。每一轮都会扫描未排序部分以找到最小值,再将它与未排序部分的第一个位置交换。例如,第一轮找到 11 并将它移到索引 0;下一轮找到 12 并将它移到索引 1。无论数组最初的顺序如何,它都要进行 O(n²) 次比较,但交换次数只有线性数量级。

本节中的代码以及显示的标签或输出仍为英文。

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {64, 34, 25, 12, 22, 11, 90};
    selectionSort(values);
    System.out.println(Arrays.toString(values));
  }

  static void selectionSort(int[] values) {
    for (int i = 0; i < values.length - 1; i++) {
      int minIndex = i;
      for (int j = i + 1; j < values.length; j++) {
        if (values[j] < values[minIndex]) {
          minIndex = j;
        }
      }
      int temp = values[i];
      values[i] = values[minIndex];
      values[minIndex] = temp;
    }
  }
}
[11, 12, 22, 25, 34, 64, 90]

插入排序

插入排序会从左向右逐步扩大已排序前缀。它先将下一个值保存为 key,再把前缀中比它大的值向右移动一位,最后将 key 放入空出的位置。每轮开始时,i 之前的所有元素都已排好序。这个算法容易跟踪;对于较小或几乎有序的数组,它也可能很有效。它最坏情况下的时间复杂度为 O(n²)。

本节中的代码以及显示的标签或输出仍为英文。

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {64, 34, 25, 12, 22, 11, 90};
    insertionSort(values);
    System.out.println(Arrays.toString(values));
  }

  static void insertionSort(int[] values) {
    for (int i = 1; i < values.length; i++) {
      int key = values[i];
      int j = i - 1;
      while (j >= 0 && values[j] > key) {
        values[j + 1] = values[j];
        j--;
      }
      values[j + 1] = key;
    }
  }
}
[11, 12, 22, 25, 34, 64, 90]

归并排序

归并排序通过递归将数组拆分成两半,直到每个部分只剩一个值,然后再合并这些有序部分。合并时,两个索引分别跟踪两半中下一个尚未使用的值,并先将较小值复制到结果中。若两个值相等,优先选择左侧的值可以保留它们原有的相对顺序。此实现的时间复杂度为 O(n log n),并会在递归过程中分配临时数组,因此需要与输入规模成正比的额外内存。

本节中的代码以及显示的标签或输出仍为英文。

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {64, 34, 25, 12, 22, 11, 90};
    mergeSort(values);
    System.out.println(Arrays.toString(values));
  }

  static void mergeSort(int[] values) {
    if (values.length < 2) {
      return;
    }
    int middle = values.length / 2;
    int[] left = Arrays.copyOfRange(values, 0, middle);
    int[] right = Arrays.copyOfRange(values, middle, values.length);
    mergeSort(left);
    mergeSort(right);
    merge(values, left, right);
  }

  static void merge(int[] values, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        values[k++] = left[i++];
      } else {
        values[k++] = right[j++];
      }
    }
    while (i < left.length) values[k++] = left[i++];
    while (j < right.length) values[k++] = right[j++];
  }
}
[11, 12, 22, 25, 34, 64, 90]

快速排序

快速排序会选取一个基准值,并对当前范围进行分区,使小于基准值的元素排在它之前,其余元素排在它之后。此实现选用最后一个值作为基准。分区方法会返回基准值最终所在的索引,随后递归地对其两侧的范围排序。快速排序通常具有 O(n log n) 的时间复杂度,但这种基准选择在不利输入下可能导致 O(n²) 的时间复杂度,例如输入已经有序时。递归调用还会占用栈空间。

本节中的代码以及显示的标签或输出仍为英文。

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {64, 34, 25, 12, 22, 11, 90};
    quickSort(values, 0, values.length - 1);
    System.out.println(Arrays.toString(values));
  }

  static void quickSort(int[] values, int low, int high) {
    if (low >= high) {
      return;
    }
    int pivotIndex = partition(values, low, high);
    quickSort(values, low, pivotIndex - 1);
    quickSort(values, pivotIndex + 1, high);
  }

  static int partition(int[] values, int low, int high) {
    int pivot = values[high];
    int smallerEnd = low - 1;
    for (int current = low; current < high; current++) {
      if (values[current] < pivot) {
        smallerEnd++;
        int temp = values[smallerEnd];
        values[smallerEnd] = values[current];
        values[current] = temp;
      }
    }
    int pivotIndex = smallerEnd + 1;
    int temp = values[pivotIndex];
    values[pivotIndex] = values[high];
    values[high] = temp;
    return pivotIndex;
  }
}
[11, 12, 22, 25, 34, 64, 90]

选择算法并了解其权衡

学习排序或处理小型数组时,冒泡排序、选择排序和插入排序能清楚展示每次比较和移动,但它们的二次增长使其不适合大型输入。数组较小或已经接近有序时,插入排序是合理的选择。如果需要减少写入次数,选择排序可能有用,因为它每轮最多交换一次;不过,每轮仍会扫描剩余元素。

归并排序的运行时间稳定在 O(n log n),适合需要稳定排序的情况,但此实现会分配临时数组。快速排序通常表现良好,并在原数组内完成排序;然而,这种选取末尾元素为基准的实现最坏情况下具有二次时间复杂度,也会使用递归栈空间。在生产代码中,除非需求明确要求手动实现算法,否则应优先使用 Java 成熟的库排序。普通的基本类型数组排序可使用 Arrays.sort();当任务本身要求了解或实现手动排序方法时,再学习或编写相应实现。