排序算法概述

Java中实现排序可以通过多种方式，包括内置方法、自定义算法或使用第三方库。常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。

使用Arrays.sort()方法

对于数组排序，Java提供了Arrays.sort()方法，支持对基本类型和对象数组排序。基本类型数组使用快速排序，对象数组使用归并排序。

import java.util.Arrays;int[] arr = {5, 2, 9, 1, 5};
Arrays.sort(arr); // 升序排序
System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 5, 5, 9]

使用Collections.sort()方法

对List集合排序可以使用Collections.sort()方法，默认按自然顺序升序排列。支持自定义Comparator实现复杂排序逻辑。

import java.util.Collections;
import java.util.ArrayList;
import java.util.List;List<Integer> list = new ArrayList<>(List.of(5, 2, 9, 1, 5));
Collections.sort(list); // 升序排序
System.out.println(list); // 输出 [1, 2, 5, 5, 9]

自定义Comparator

需要降序或按特定字段排序时，可通过实现Comparator接口自定义排序规则。

Collections.sort(list, (a, b) -> b - a); // 降序排序
System.out.println(list); // 输出 [9, 5, 5, 2, 1]

实现快速排序算法

快速排序是一种分治算法，平均时间复杂度为O(n log n)。以下是递归实现的示例：

void quickSort(int[] arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}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++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;
}void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

Java 8 Stream排序

利用Stream API可以简洁地实现排序，支持链式操作和并行处理。

List<Integer> sortedList = list.stream().sorted() // 自然排序.collect(Collectors.toList());List<Integer> reverseList = list.stream().sorted(Comparator.reverseOrder()) // 降序排序.collect(Collectors.toList());

性能比较

• 小数据量：插入排序或冒泡排序可能更简单。
• 大数据量：快速排序、归并排序或堆排序更高效。
• 稳定性要求：归并排序是稳定排序，相同元素相对位置不变。