您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# Java排序算法的分类与介绍
排序算法是计算机科学中最基础且重要的算法之一，Java作为广泛使用的编程语言，其内置及常见的排序算法值得系统梳理。本文将Java排序算法分为**比较排序**和**非比较排序**两大类，详解8种经典算法的原理、实现及复杂度，并附完整代码示例。
## 一、排序算法分类概览
### 1.1 比较排序（Comparison Sort）
通过比较元素间大小决定顺序，时间复杂度下限为O(nlogn)：
- **基本排序**：冒泡、选择、插入
- **高效排序**：快速排序、归并排序、堆排序
- **混合排序**：TimSort（Java默认排序算法）
### 1.2 非比较排序（Non-comparison Sort）
利用元素特定属性（如数值范围）进行排序，可突破O(nlogn)限制：
- 计数排序
- 桶排序
- 基数排序
## 二、比较排序算法详解
### 2.1 冒泡排序（Bubble Sort）
**原理**：重复比较相邻元素，将较大元素逐步"冒泡"到右侧。
```java
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换相邻元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
复杂度分析： - 时间复杂度：O(n²)（最坏/平均） - 空间复杂度：O(1) - 稳定性：稳定
原理：每次选择未排序部分的最小元素放到已排序序列末尾。
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换找到的最小元素
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
复杂度分析： - 时间复杂度：O(n²) - 空间复杂度：O(1) - 稳定性：不稳定（相同元素可能被交换）
原理：将未排序元素逐个插入到已排序序列的适当位置。
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) - 稳定性：稳定
原理：分治法思想，选取基准元素将数组分为两部分递归排序。
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 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;
}
复杂度分析： - 时间复杂度：平均O(nlogn)，最坏O(n²)（已排序数组） - 空间复杂度：O(logn)（递归栈） - 稳定性：不稳定
原理：分治法将数组分成两半分别排序，再合并两个有序数组。
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 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) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = 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(nlogn)（所有情况） - 空间复杂度：O(n)（临时数组） - 稳定性：稳定
原理：利用堆数据结构（完全二叉树）进行选择排序。
public static void heapSort(int[] arr) {
// 构建最大堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
heapify(arr, arr.length, i);
}
// 逐个提取堆顶元素
for (int i = arr.length - 1; i > 0; i--) {
// 交换堆顶和末尾元素
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 调整剩余堆
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
复杂度分析： - 时间复杂度：O(nlogn) - 空间复杂度：O(1) - 稳定性：不稳定
原理：统计每个元素的出现次数，按统计结果输出。
public static void countingSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
int[] count = new int[max + 1];
// 统计频率
for (int num : arr) {
count[num]++;
}
// 计算前缀和
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// 输出排序结果
int[] output = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
System.arraycopy(output, 0, arr, 0, arr.length);
}
适用场景：整数排序且范围不大（k ≈ n） - 时间复杂度：O(n + k) - 空间复杂度：O(n + k) - 稳定性：稳定
原理：将数据分到有限数量的桶里，每个桶再单独排序。
public static void bucketSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int bucketSize = 5; // 自定义桶数量
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < bucketSize; i++) {
buckets.add(new ArrayList<>());
}
// 元素分配到桶
for (int num : arr) {
int index = (num - min) * (bucketSize - 1) / (max - min);
buckets.get(index).add(num);
}
// 每个桶排序
int index = 0;
for (List<Integer> bucket : buckets) {
Collections.sort(bucket);
for (int num : bucket) {
arr[index++] = num;
}
}
}
适用场景：数据均匀分布 - 时间复杂度：平均O(n + n²/k + k)，最坏O(n²) - 空间复杂度：O(n + k) - 稳定性：取决于桶内排序算法
原理：按位数从低到高依次排序（LSD）或从高到低（MSD）。
public static void radixSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}
private static void countingSortByDigit(int[] arr, int exp) {
int[] output = new int[arr.length];
int[] count = new int[10];
// 统计当前位数出现次数
for (int num : arr) {
count[(num / exp) % 10]++;
}
// 计算前缀和
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 输出排序结果
for (int i = arr.length - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
System.arraycopy(output, 0, arr, 0, arr.length);
}
适用场景：整数或字符串排序 - 时间复杂度：O(d(n + k))（d为最大位数） - 空间复杂度：O(n + k) - 稳定性：稳定
Java的Arrays.sort()根据不同场景选择算法：
1. 基本类型数组：双轴快速排序（Dual-Pivot QuickSort）
2. 对象数组：TimSort（归并排序+插入排序优化）
// 示例用法
int[] arr = {5, 2, 9, 1, 5};
Arrays.sort(arr); // 快速排序
List<Integer> list = Arrays.asList(5, 2, 9);
Collections.sort(list); // TimSort
| 场景 | 推荐算法 | 理由 |
|---|---|---|
| 小规模数据 | 插入排序 | 常数项小 |
| 基本类型数组 | 快速排序 | 平均性能好 |
| 需要稳定性 | 归并排序 | 稳定且O(nlogn) |
| 数据范围有限 | 计数排序 | O(n)时间复杂度 |
| 海量数据外部排序 | 归并排序 | 适合磁盘I/O特性 |
理解各排序算法的特性和适用场景，才能在开发中做出最优选择。 “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。