Java常用排序方法详解

在Java编程中，排序是一个非常常见的操作。本文将详细介绍Java中常用的排序方法，包括Arrays.sort和Arrays.parallelSort的区别，以及其他常用的排序算法。

Arrays.sort 与 Arrays.parallelSort 的区别

在Java中，Arrays.sort和Arrays.parallelSort都是用于对数组进行排序的方法。虽然它们的功能相似，但在实现和性能上有一些重要的区别。

Arrays.sort

Arrays.sort 是Java中最常用的排序方法之一。它使用的是双轴快速排序算法（Dual-Pivot Quicksort），该算法在大多数情况下表现良好。以下是Arrays.sort的一些特点：

  • 单线程：Arrays.sort在单个线程中执行排序操作。
  • 适用性广：适用于所有基本类型和对象类型的数组。
  • 稳定性：对于对象数组，Arrays.sort是稳定的排序算法，即不会改变相等元素的相对顺序。

示例代码：

1
2
3
int[] array = {5, 3, 8, 1, 2};
Arrays.sort(array);
System.out.println(Arrays.toString(array)); // 输出: [1, 2, 3, 5, 8]

Arrays.parallelSort

Arrays.parallelSort 是Java 8引入的一种并行排序方法。它使用的是并行归并排序算法（Parallel Merge Sort），通过将数组分成多个子数组并行排序，然后合并结果来提高性能。以下是Arrays.parallelSort的一些特点：

  • 多线程：Arrays.parallelSort利用多线程并行执行排序操作，适合在多核处理器上使用。
  • 适用性广：适用于所有基本类型和对象类型的数组。
  • 性能：在大数组排序时，Arrays.parallelSort通常比Arrays.sort更快，但在小数组上可能没有明显优势。

示例代码：

1
2
3
int[] array = {5, 3, 8, 1, 2};
Arrays.parallelSort(array);
System.out.println(Arrays.toString(array)); // 输出: [1, 2, 3, 5, 8]

选择哪种方法？

  • 小数组：对于小数组，Arrays.sort通常表现更好，因为它的单线程开销较低。
  • 大数组：对于大数组，特别是在多核处理器上，Arrays.parallelSort可能会显著提高排序速度。
  • 稳定性：如果需要稳定排序（例如排序对象数组），可以选择Arrays.sort。

总之，选择哪种排序方法取决于具体的应用场景和性能需求。在大多数情况下，Arrays.sort已经足够高效，但在处理大规模数据时，可以考虑使用Arrays.parallelSort来利用多核处理器的优势。

常用的排序算法

在算法竞赛中，除了Arrays.sort和Arrays.parallelSort，Java还提供了多种常用的排序算法。以下是一些常用的排序算法及其示例代码：

冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法，通过重复遍历要排序的列表，依次比较相邻的元素并交换顺序，直到整个列表有序。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
public static void bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

选择排序 (Selection Sort)

选择排序是一种简单直观的排序算法，每次从未排序部分选择最小（或最大）的元素放到已排序部分的末尾。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void selectionSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        int temp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = temp;
    }
}

插入排序 (Insertion Sort)

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
public static void insertionSort(int[] array) {
    int n = array.length;
    for (int i = 1; i < n; i++) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

归并排序 (Merge Sort)

归并排序是一种分治算法，将数组分成两个子数组分别排序，然后合并两个已排序的子数组。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        merge(array, left, mid, right);
    }
}

private static void merge(int[] array, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] L = new int[n1];
    int[] R = new int[n2];
    for (int i = 0; i < n1; i++) {
        L[i] = array[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = array[mid + 1 + j];
    }
    int i = 0, j = 0;
    int k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            array[k] = L[i];
            i++;
        } else {
            array[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        array[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        array[k] = R[j];
        j++;
        k++;
    }
}

快速排序 (Quick Sort)

快速排序是一种分治算法，通过选择一个基准元素，将数组分成两部分，一部分小于基准元素，另一部分大于基准元素，然后递归地对两部分进行排序。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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);
    }
}

private 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++;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;
    return i + 1;
}

Java中其他常用的排序方法

除了上述排序算法，Java中还提供了其他一些常用的排序方法，以下是一些示例：

Collections.sort

Collections.sort用于对List进行排序，使用的是自然顺序或指定的Comparator。

示例代码：

1
2
3
List<Integer> list = Arrays.asList(5, 3, 8, 1, 2);
Collections.sort(list);
System.out.println(list); // 输出: [1, 2, 3, 5, 8]

Stream.sorted

Stream.sorted用于对流中的元素进行排序，返回一个新的排序后的流。

示例代码：

1
2
3
List<Integer> list = Arrays.asList(5, 3, 8, 1, 2);
List<Integer> sortedList = list.stream().sorted().collect(Collectors.toList());
System.out.println(sortedList); // 输出: [1, 2, 3, 5, 8]

Arrays.sort (指定范围)

Arrays.sort还可以对数组的指定范围进行排序。

示例代码：

1
2
3
int[] array = {5, 3, 8, 1, 2};
Arrays.sort(array, 1, 4);
System.out.println(Arrays.toString(array)); // 输出: [5, 1, 3, 8, 2]

对象排序实现方式

1. 实现Comparable接口

通过实现Comparable接口定义自然排序规则：

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Person implements Comparable<Person> {
    String name;
    int age;
    
    @Override
    public int compareTo(Person o) {
        return this.name.compareTo(o.name); // 按姓名排序
    }
}

// 使用示例
List<Person> people = new ArrayList<>();
people.add(new Person("John", 25));
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 20));
Collections.sort(people);

2. 使用Comparator比较器（推荐）

通过Comparator实现灵活的外部排序规则，无需修改原有类结构：

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Person {
    String name;
    int age;
    
    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

// 按年龄排序
Comparator<Person> ageComparator = new Comparator<>() {
    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.age, p2.age);
    }
};

// 使用示例
List<Person> people = new ArrayList<>();
people.add(new Person("John", 25));
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 20));
Collections.sort(people, ageComparator);

Java 8新特性应用

1. Lambda表达式简化

示例代码：

1
2
3
// 按姓名长度排序
Collections.sort(people, (p1, p2) -> 
    Integer.compare(p1.name.length(), p2.name.length()));

Lambda表达式在编译后会生成私有方法和invokedynamic指令。

2. 方法引用

示例代码：

1
2
// 使用Comparator.comparing
Collections.sort(people, Comparator.comparing(Person::getName));

进阶排序技巧

多条件排序

示例代码：

1
2
3
Comparator<Person> multiComparator = Comparator.comparing(Person::getAge)
                                                .thenComparing(Person::getName);
Collections.sort(people, multiComparator);

逆序排序

示例代码：

1
2
Comparator<Person> reversedComparator = Comparator.comparing(Person::getAge).reversed();
Collections.sort(people, reversedComparator);

性能注意事项

  1. 数组排序使用优化后的快速排序算法。
  2. 对象排序时间复杂度为$O(n \log n)$。
  3. 大数据量推荐使用List的sort()方法：
    1
    people.sort(Comparator.comparing(Person::getAge));

通过了解和掌握这些常用的排序方法，可以在实际开发和算法竞赛中灵活运用，解决各种排序问题。