Java 排序算法实现与复杂度分析

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) { StackRange 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)不稳定通用场景、性能要求高使用建议归并排序适合需要稳定排序且内存充足的大数据场景冒泡排序适合教学演示或数据量极小的场景快速排序适合大多数通用排序场景性能优秀快速排序非递归版本适合避免递归栈溢出的场景