Java 数组排序完全教程

数组排序是 Java 编程中最基础也最常用的操作之一。本教程将从多个角度系统讲解 Java 中数组排序的实现方法,涵盖内置 API、经典算法手写实现以及实用技巧。

一、准备工作:认识 Java 数组

在开始排序之前,先明确数组的基本特性:

• 数组是定长的,创建后长度不可变
• 数组元素类型必须一致
• 索引从 0 开始,范围 0 ~ length-1

int[] arr = {5, 2, 8, 1, 9, 3};

二、使用 Arrays.sort() —— 最推荐的方式

Java 标准库提供了 java.util.Arrays 工具类,其中 sort() 是最常用的排序方法。它底层使用双轴快速排序(Dual-Pivot Quicksort),性能优秀。

2.1 基本类型数组排序(升序)

import java.util.Arrays;

public class SortDemo1 {
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9, 3};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        // 输出: [1, 2, 3, 5, 8, 9]
    }
}

2.2 部分区间排序

Arrays.sort(arr, fromIndex, toIndex) 可以对指定范围排序(左闭右开):

int[] arr = {9, 5, 2, 8, 1, 7};
Arrays.sort(arr, 1, 4); // 只排序索引 1、2、3 的元素
System.out.println(Arrays.toString(arr));
// 输出: [9, 1, 2, 5, 8, 7]

2.3 对象数组排序

对象数组调用 sort() 时,元素必须实现 Comparable 接口,或传入 Comparator:

String[] names = {"Tom", "Alice", "Bob", "David"};
Arrays.sort(names);
System.out.println(Arrays.toString(names));
// 输出: [Alice, Bob, David, Tom]

2.4 降序排序

注意: Arrays.sort() 对基本类型数组不支持直接降序。常用解决方案有三种:

方案一:先升序,再反转

int[] arr = {5, 2, 8, 1, 9, 3};
Arrays.sort(arr);
for (int i = 0, j = arr.length - 1; i < j; i++, j--) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
System.out.println(Arrays.toString(arr));
// 输出: [9, 8, 5, 3, 2, 1]

方案二:使用包装类 + Comparator

Integer[] arr = {5, 2, 8, 1, 9, 3};
Arrays.sort(arr, (a, b) -> b - a); // 降序
System.out.println(Arrays.toString(arr));
// 输出: [9, 8, 5, 3, 2, 1]

方案三:自定义 Comparator(推荐,避免溢出)

Integer[] arr = {5, 2, 8, 1, 9, 3};
Arrays.sort(arr, Comparator.reverseOrder());

⚠️ 提示:方案二中 b - a 在数值极大或极小时可能溢出,建议用 Integer.compare(b, a) 或 Comparator.reverseOrder()。

三、手写经典排序算法

虽然实际开发中几乎都用 Arrays.sort(),但掌握经典算法对理解原理和应对面试非常重要。下面给出几种常见算法的完整实现。

3.1 冒泡排序(Bubble Sort)

思路: 相邻元素两两比较,大的往后"冒泡"。每一轮确定一个最大值。

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break; // 优化:某轮无交换说明已有序
    }
}

• 时间复杂度:O(n²),最好 O(n)(已排序)
• 空间复杂度:O(1)
• 稳定排序

3.2 选择排序(Selection Sort)

思路: 每轮从未排序区选出最小值,放到已排序区末尾。

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

• 时间复杂度:O(n²)(无论数据如何)
• 空间复杂度:O(1)
• 不稳定排序

3.3 插入排序(Insertion Sort)

思路: 将每个元素插入到前面已排序部分的合适位置。

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

• 时间复杂度:O(n²),最好 O(n)
• 空间复杂度:O(1)
• 稳定排序,适合小规模或基本有序的数据

3.4 快速排序(Quick Sort)

思路: 选一个基准值(pivot),把数组分成小于和大于基准的两部分,递归处理。

public static void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    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]; // 取最后一个元素为基准
    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;
}

调用:

int[] arr = {5, 2, 8, 1, 9, 3};
quickSort(arr, 0, arr.length - 1);

• 平均时间复杂度:O(n log n);最坏 O(n²)(已排序且取端点为基准)
• 空间复杂度:O(log n)(递归栈)
• 不稳定排序

3.5 归并排序(Merge Sort)

思路: 分治法,把数组不断二分,再合并两个有序子数组。

public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    System.arraycopy(temp, 0, arr, left, temp.length);
}

• 时间复杂度:O(n log n)(稳定)
• 空间复杂度:O(n)
• 稳定排序

四、对象数组的自定义排序

实际业务中,常需按对象某个字段排序。假设有 Student 类:

class Student {
    String name;
    int score;
    Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
    @Override
    public String toString() {
        return name + ":" + score;
    }
}

4.1 用 Comparator 按分数降序

Student[] students = {
    new Student("Tom", 88),
    new Student("Alice", 95),
    new Student("Bob", 76)
};

Arrays.sort(students, (a, b) -> Integer.compare(b.score, a.score));
System.out.println(Arrays.toString(students));
// 输出: [Alice:95, Tom:88, Bob:76]

4.2 多级排序

先按分数降序,分数相同按名字升序:

Arrays.sort(students,
    Comparator.comparingInt(Student::getScore).reversed()
              .thenComparing(Student::getName));

说明:Student 需提供 getter 方法,或直接用字段访问器(需 public)。

4.3 实现 Comparable 接口

若排序规则是类固有的,可让类实现 Comparable:

class Student implements Comparable<Student> {
    String name;
    int score;
    // 构造器略
    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.score, other.score); // 按分数升序
    }
}

// 直接排序
Arrays.sort(students);

五、排序算法对比总结

六、实用技巧与注意事项

1. 优先使用 Arrays.sort():JDK 实现经过高度优化,比手写更快更稳。

2. 基本类型 vs 包装类型:

   • int[] 用 Arrays.sort() 是双轴快排,不支持 Comparator
   • Integer[] 用 Arrays.sort() 是 TimSort,支持 Comparator

3. Comparator 避免用减法:

   // 不推荐
   (a, b) -> a - b
   // 推荐
   Comparator.comparingInt(x -> x) 或 Integer.compare(a, b)
   

4. 部分排序用区间参数:

   Arrays.sort(arr, 0, k); // 只关心前 k 个
   

5. 找 Top K 问题:无需全排序,可用 PriorityQueue:

   // 找出最大的 k 个
   PriorityQueue<Integer> pq = new PriorityQueue<>();
   for (int num : arr) {
       pq.offer(num);
       if (pq.size() > k) pq.poll();
   }
   

6. 字符串数组排序:默认按字典序(区分大小写)。若要不区分大小写:

   Arrays.sort(names, String.CASE_INSENSITIVE_ORDER);
   

7. 排序后数组是原数组被修改,如需保留原数组请先 clone():

   int[] sorted = arr.clone();
   Arrays.sort(sorted);
   

七、完整示例

import java.util.Arrays;
import java.util.Comparator;

public class ArraySortExample {
    public static void main(String[] args) {
        // 1. 基本类型升序
        int[] nums = {5, 2, 8, 1, 9, 3};
        Arrays.sort(nums);
        System.out.println("升序: " + Arrays.toString(nums));

        // 2. 降序(包装类 + Comparator)
        Integer[] boxes = {5, 2, 8, 1, 9, 3};
        Arrays.sort(boxes, Comparator.reverseOrder());
        System.out.println("降序: " + Arrays.toString(boxes));

        // 3. 自定义对象排序
        Student[] students = {
            new Student("Tom", 88),
            new Student("Alice", 95),
            new Student("Bob", 76)
        };
        Arrays.sort(students, Comparator.comparingInt(Student::getScore).reversed());
        System.out.println("学生按分数: " + Arrays.toString(students));
    }
}

class Student {
    private String name;
    private int score;
    Student(String name, int score) { this.name = name; this.score = score; }
    public String getName() { return name; }
    public int getScore() { return score; }
    @Override
    public String toString() { return name + ":" + score; }
}

结语

在 Java 中实现数组排序,核心要点如下:

• 日常开发首选 Arrays.sort(),省时高效;
• 需要降序时,基本类型先升序再反转,或改用包装类型 + Comparator;
• 对象排序用 Comparator 灵活控制,多级排序用 thenComparing;
• 算法原理要理解冒泡、选择、插入、快排、归并的时间/空间/稳定性差异;
• 记住 Comparator 不要用减法,防止溢出。

掌握以上内容,你就能够应对绝大多数 Java 数组排序场景。