1. 归并排序 (Merge Sort)
核心思想：分治策略，将数组递归地分成两半，分别排序后再合并。
特点：
- 空间复杂度：O(N) - 需要额外数组存储合并结果
- 时间复杂度：O(NlogN) - 稳定高效
- 稳定性：稳定 - 相等元素相对位置不变
// 归并排序 // 空间复杂度 O(N) // 时间复杂度 O(NlogN) // 稳定 private static void mergeSort(int[] arr) { mergeSort(arr, 0, arr.length - 1); } private static void mergeSort(int[] arr, int left, int right) { if (left >= right) { return; } 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[] result = new int[right - left + 1]; int resultSize = 0; int cur1 = left; int cur2 = mid + 1; while (cur1 <= mid && cur2 <= right) { if (arr[cur1] < arr[cur2]) { result[resultSize++] = arr[cur1++]; } else { result[resultSize++] = arr[cur2++]; } } while (cur1 <= mid) { result[resultSize++] = arr[cur1++]; } while (cur2 <= right) { result[resultSize++] = arr[cur2++]; } for (int i = 0; i < result.length; i++) { arr[left + i] = result[i]; } }2. 冒泡排序 (Bubble Sort)
核心思想：重复遍历数组，比较相邻元素，将较大元素逐步"冒泡"到数组末尾。
特点：
- 空间复杂度：O(1) - 原地排序
- 时间复杂度：O(N²) - 效率较低
- 稳定性：稳定 - 相等元素相对位置不变
// 冒泡排序 // 空间复杂度 O(1) // 时间复杂度 O(N^2) // 稳定 private static void bubbleSort(int[] arr) { for (int bound = 0; bound < arr.length - 1; bound++) { for (int cur = arr.length - 1; cur > bound; cur--) { if (arr[cur - 1] > arr[cur]) { int temp = arr[cur - 1]; arr[cur - 1] = arr[cur]; arr[cur] = temp; } } } }3. 快速排序 (Quick Sort)
核心思想：分治策略，选取基准元素，将数组分为小于基准和大于基准的两部分，递归排序。
特点：
- 空间复杂度：最坏 O(N)，平均 O(logN) - 递归栈空间
- 时间复杂度：最坏 O(N²)，平均 O(NlogN)
- 稳定性：不稳定 - 相等元素可能交换位置
// 快速排序 // 空间复杂度 最坏 O(N)，平均 O(logN) // 时间复杂度 最坏 O(N^2)，平均 O(NlogN) // 不稳定 private static void quickSort(int[] arr) { quickSort(arr, 0, arr.length - 1); } private static void quickSort(int[] arr, int left, int right) { if (left >= right) { return; } int index = partition(arr, left, right); quickSort(arr, left, index - 1); quickSort(arr, index + 1, right); } private static int partition(int[] arr, int left, int right) { int value = arr[right]; int l = left; int r = right; while (l < r) { while (l < r && arr[l] <= value) { l++; } while (l < r && arr[r] >= value) { r--; } swap(arr, l, r); } swap(arr, l, right); return l; } private static void swap(int[] arr, int l, int r) { int temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; }4. 快速排序非递归版本
核心思想：使用栈模拟递归过程，避免递归调用栈的开销。
// 快速排序（非递归版本） static class Range { public int left; public int right; public Range(int left, int right) { this.left = left; this.right = right; } } static void quickSortByLoop(int[] arr) { Stack<Range> stack = new Stack<>(); stack.push(new Range(0, arr.length - 1)); while (!stack.isEmpty()) { Range range = stack.pop(); if (range.left >= range.right) { continue; } int index = partition(arr, range.left, range.right); stack.push(new Range(range.left, index - 1)); stack.push(new Range(index + 1, range.right)); } }5. 算法对比总结
| 排序算法 | 空间复杂度 | 时间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|
| 归并排序 | O(N) | O(NlogN) | 稳定 | 大数据量、需要稳定排序 |
| 冒泡排序 | O(1) | O(N²) | 稳定 | 教学演示、小数据量 |
| 快速排序 | 平均 O(logN) | 平均 O(NlogN) | 不稳定 | 通用场景、性能要求高 |
使用建议：
- 归并排序适合需要稳定排序且内存充足的大数据场景
- 冒泡排序适合教学演示或数据量极小的场景
- 快速排序适合大多数通用排序场景，性能优秀
- 快速排序非递归版本适合避免递归栈溢出的场景
