java中常见的几种排序算法

手动实现的排序算法（共 10 种常见）

这些是你在学习数据结构与算法时会接触到的经典排序方法。虽然不推荐用于生产环境，但面试常考，必须掌握。

✅ 1. 冒泡排序（Bubble Sort）

• 原理：重复遍历数组，相邻元素比较，大的“冒泡”到后面。
• 时间复杂度：O(n²)
• 稳定性：✅ 稳定

public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

---

✅ 2. 选择排序（Selection Sort）

• 原理：每次找最小元素，放到已排序部分末尾。
• 时间复杂度：O(n²)
• 稳定性：❌ 不稳定

public static void selectionSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {int minIdx = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIdx]) {minIdx = j;}}swap(arr, i, minIdx);}
}

---

✅ 3. 插入排序（Insertion Sort）

• 原理：像打扑克牌，每次将新元素插入到已排序部分的正确位置。
• 时间复杂度：O(n²)，但对小数组或部分有序数组很快
• 稳定性：✅ 稳定

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;}
}

---

✅ 4. 快速排序（Quick Sort）

• 原理：分治法，选一个“基准”，小的放左，大的放右，递归排序。
• 时间复杂度：平均 O(n log n)，最坏 O(n²)
• 稳定性：❌ 不稳定（但可改造为稳定）

public static 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);}
}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++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;
}

---

✅ 5. 归并排序（Merge Sort）

• 原理：分治 + 合并，递归拆分，再合并有序数组。
• 时间复杂度：O(n log n)（始终稳定）
• 稳定性：✅ 稳定
• Java 内部 TimSort 的基础

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 l, int m, int r) {// 合并两个有序子数组int[] temp = new int[r - l + 1];int i = l, j = m + 1, k = 0;while (i <= m && j <= r) {temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];}while (i <= m) temp[k++] = arr[i++];while (j <= r) temp[k++] = arr[j++];System.arraycopy(temp, 0, arr, l, temp.length);
}

---

✅ 6. 堆排序（Heap Sort）

• 原理：利用大顶堆，每次取最大值放到末尾。
• 时间复杂度：O(n log n)
• 稳定性：❌ 不稳定

public static void heapSort(int[] arr) {int n = arr.length;// 构建大顶堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 逐个提取元素for (int i = n - 1; i > 0; i--) {swap(arr, 0, i);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) {swap(arr, i, largest);heapify(arr, n, largest);}
}

---

✅ 7. 希尔排序（Shell Sort）

• 原理：插入排序的改进版，先按 gap 分组排序，逐步缩小 gap。
• 时间复杂度：O(n log n) ~ O(n²)，取决于 gap 序列
• 稳定性：❌ 不稳定

---

✅ 8. 计数排序（Counting Sort）

• 原理：适用于小范围整数，统计每个数出现次数。
• 时间复杂度：O(n + k)，k 是数据范围
• 稳定性：✅ 稳定

---

✅ 9. 桶排序（Bucket Sort）

• 原理：将数据分到多个“桶”，每个桶内排序，再合并。
• 时间复杂度：平均 O(n)，前提是数据均匀分布
• 稳定性：✅ 稳定（如果桶内排序稳定）

---

✅ 10. 基数排序（Radix Sort）

• 原理：按位排序（个位、十位、百位…），使用计数排序作为子过程。
• 时间复杂度：O(d * (n + k))，d 是位数
• 稳定性：✅ 稳定

---

📊 排序算法对比表

算法	时间复杂度（平均）	最坏	空间	稳定性	适用场景
冒泡排序	O(n²)	O(n²)	O(1)	✅	学习、小数据
选择排序	O(n²)	O(n²)	O(1)	❌	学习
插入排序	O(n²)	O(n²)	O(1)	✅	小数组、几乎有序
快速排序	O(n log n)	O(n²)	O(log n)	❌	通用（Java 基本类型）
归并排序	O(n log n)	O(n log n)	O(n)	✅	稳定排序、外部排序
堆排序	O(n log n)	O(n log n)	O(1)	❌	堆结构学习
计数排序	O(n + k)	O(n + k)	O(k)	✅	小范围整数
桶排序	O(n)	O(n²)	O(n)	✅	数据均匀分布
基数排序	O(d·(n+k))	O(d·(n+k))	O(n+k)	✅	字符串、整数

---

✅ 总结：Java 中的排序方法有几种？

分类	数量	说明
内置排序方法	4 种	Arrays.sort(), Collections.sort(), List.sort(), Stream.sorted()
手动实现算法	10 种	冒泡、选择、插入、快排、归并、堆、希尔、计数、桶、基数

✅ 所以严格来说，Java 中常见的排序方法有 14 种以上。

---

🎯 使用建议

场景	推荐方法
生产环境排序	Arrays.sort() / List.sort()
面试手写排序	快排、归并、冒泡（至少掌握 3 种）
小数组优化	插入排序（JDK 内部也用）
稳定排序需求	归并、TimSort