一篇搞懂 Java 常用排序算法：从原理到实现
·
排序算法是计算机科学的基础，也是日常开发中频繁用到的核心技能。本文将结合完整的 Java 实现代码，详细讲解插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序和计数排序这 8 种常用排序算法，从核心思想、实现细节到性能特点进行全方位解析，帮助你彻底掌握排序算法的精髓。
一、排序算法基础概念
在正式讲解算法前，先明确几个核心概念，方便后续对比分析：
- 稳定性：排序后，相同值元素的相对位置是否保持不变（如 [2,1,1,3] 排序后，两个 1 的顺序是否和原数组一致）。
- 时间复杂度：算法执行时间随数据规模增长的变化趋势，通常分析最坏情况和平均情况。
- 空间复杂度：算法执行过程中额外占用的存储空间（不包含原数组的存储）。
- 原地排序：是否仅通过少量额外空间（通常 O (1)）完成排序，无需依赖额外数组或数据结构。
二、详细算法解析与实现
本文所有代码均封装在Sort类中，包含完整的排序方法和辅助函数（如swap交换元素），可直接复制到 IDE 中运行测试。
1. 插入排序（Insertion Sort）
核心思想
类比 “整理扑克牌”：从第二个元素开始，将当前元素插入到前面已排好序的序列中，直到整个数组有序。
实现代码
public void insertionSort(int[] arr) {
// 从第2个元素（索引1）开始遍历
for (int i = 1; i < arr.length; i++) {
// 向前比较，将arr[i]插入到正确位置
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1); // 比前一个元素小则交换
}
}
}
}
// 辅助函数：交换数组中两个元素
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
性能分析
- 时间复杂度：O (n²)（最坏 / 平均情况），O (n)（最好情况，数组已有序）。
- 空间复杂度：O (1)（原地排序）。
- 稳定性：稳定（仅交换相邻元素，相同值不会改变相对位置）。
- 适用场景：小规模数据或接近有序的数据（如数据库查询结果的局部排序）。
2. 希尔排序（Shell Sort）
核心思想
插入排序的 “优化版”：通过分组插入排序减少比较和交换次数。先将数组按 “间隔 gap” 分成多个子数组，对每个子数组做插入排序；逐渐缩小 gap（通常每次除以 2），直到 gap=1，此时数组已接近有序，最后做一次插入排序即可。
实现代码
public void ShellSort(int[] arr) {
int gap = arr.length; // 初始间隔为数组长度
while (gap > 1) {
gap /= 2; // 间隔每次减半
// 对每个分组进行插入排序
for (int i = gap; i < arr.length; i++) {
int temp = arr[i]; // 暂存当前元素
int j = i - gap; // 向前找同组的前一个元素
// 同组内向前比较，比temp大则后移
while (j >= 0 && arr[j] > temp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = temp; // 插入temp到正确位置
}
}
}
性能分析
- 时间复杂度：取决于 gap 序列，平均 O (n^1.3)，最坏 O (n²)（gap=1 时退化为插入排序）。
- 空间复杂度：O (1)（原地排序）。
- 稳定性：不稳定（分组交换可能打破相同值的相对位置）。
- 适用场景：中等规模数据，比插入排序效率更高，是插入排序的重要优化。
3. 选择排序（Selection Sort）
核心思想
“每次选最小的”：从待排序序列中找到最小元素，放到已排序序列的末尾；重复此过程，直到数组有序。本文实现了基础版和优化版（双向选择）。
实现代码
基础版：每次选最小元素
public void selectionSort(int[] arr) {
// 已排序序列的末尾索引（i从0开始）
for (int i = 0; i < arr.length; i++) {
int minIndex = i; // 记录最小元素的索引
// 遍历待排序序列，找最小元素
for (int j = i + 1; j < arr.length; j++) {
if (arr[index] > arr[j]) {
minIndex = j;
}
}
swap(arr, i, minIndex); // 将最小元素放到已排序序列末尾
}
}
优化版：双向选择（同时找最小和最大）
public void newselectionSort(int[] arr) {
int left = 0; // 已排序序列左边界
int right = arr.length - 1; // 已排序序列右边界
while (left < right) {
int maxIndex = left; // 最大元素索引
int minIndex = left; // 最小元素索引
// 遍历当前待排序区间[left, right]
for (int i = left + 1; i <= right; i++) {
if (arr[i] < arr[minIndex]) minIndex = i;
if (arr[i] > arr[maxIndex]) maxIndex = i;
}
// 最小元素放到左边界
swap(arr, left, minIndex);
// 注意：若最大元素在左边界，交换后最大元素已到minIndex位置
if (maxIndex == left) maxIndex = minIndex;
// 最大元素放到右边界
swap(arr, maxIndex, right);
left++;
right--;
}
}
性能分析
- 时间复杂度：O (n²)（最坏 / 平均 / 最好情况，均需遍历找最值）。
- 空间复杂度：O (1)（原地排序）。
- 稳定性：不稳定（如 [3, 2, 2]，第一次选最小元素 2 交换后，两个 2 的相对位置改变）。
- 适用场景：数据规模小，或需要 “减少交换次数” 的场景（选择排序交换次数仅 O (n)）。
4. 堆排序（Heap Sort）
核心思想
利用大根堆的特性（根元素是最大值）：
- 构建大根堆（将数组调整为大根堆结构）；
- 每次将根元素（最大值）与堆的最后一个元素交换，然后缩小堆的范围，对新根元素做 “向下调整”，维持大根堆特性；
- 重复步骤 2，直到堆为空，数组即有序。
实现代码
public void heapSort(int[] arr) {
// 1. 构建大根堆：从最后一个非叶子节点开始向下调整
for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
siftDown(arr, i, arr.length);
}
// 2. 逐步提取最大值，调整堆
int end = arr.length - 1;
while (end > 0) {
swap(arr, 0, end); // 根（最大值）与最后一个元素交换
siftDown(arr, 0, end); // 对新根向下调整，堆范围缩小为[0, end-1]
end--;
}
}
// 辅助函数：向下调整（维持大根堆）
private void siftDown(int[] arr, int parent, int end) {
int child = 2 * parent + 1; // 左孩子索引
while (child < end) {
// 若右孩子存在且比左孩子大，选择右孩子
if (child + 1 < end && arr[child] < arr[child + 1]) {
child++;
}
// 若孩子比父节点大，交换并继续向下调整
if (arr[child] > arr[parent]) {
swap(arr, child, parent);
parent = child;
child = 2 * parent + 1;
} else {
break; // 父节点比孩子大，调整完成
}
}
}
性能分析
- 时间复杂度：O (n log n)（建堆 O (n)，调整堆 O (n log n)，整体 O (n log n)）。
- 空间复杂度：O (1)（原地排序）。
- 稳定性：不稳定（交换根与末尾元素可能打破相同值的相对位置）。
- 适用场景：需要 O (n log n) 时间复杂度且不允许额外空间的场景（如大数据量的内存排序）。
5. 冒泡排序（Bubble Sort）
核心思想
“两两比较，大的往后冒”：每次遍历数组，相邻元素两两比较，若前大后小则交换；每轮遍历后，最大元素会 “冒” 到数组末尾。通过标志位优化，可在数组已有序时提前退出。
实现代码
public void bubbleSort(int[] arr) {
// 外层循环：控制需要遍历的轮数（最多n-1轮）
for (int i = 0; i < arr.length - 1; i++) {
boolean isSorted = false; // 标志位：是否已有序
// 内层循环：遍历未排序区间（每轮后末尾i个元素已有序）
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
isSorted = true; // 发生交换，说明数组未完全有序
}
}
if (!isSorted) break; // 未发生交换，数组已有序，提前退出
}
}
性能分析
- 时间复杂度：O (n²)（最坏 / 平均情况），O (n)（最好情况，数组已有序，标志位触发提前退出）。
- 空间复杂度：O (1)（原地排序）。
- 稳定性：稳定（仅交换相邻元素，相同值不交换）。
- 适用场景：教学场景（理解排序思想）或极小规模数据，实际开发中很少使用（效率低）。
6. 快速排序（Quick Sort）
核心思想
“分治法” 的经典实现：
- 选一个 “基准值”（pivot）；
- 分区（partition）：将数组分为两部分，左部分元素都小于基准值，右部分都大于基准值，基准值放在最终位置；
- 递归对左右两部分重复步骤 1-2，直到子数组长度为 1（天然有序）。
本文实现了递归版（含优化）和非递归版（栈实现），并提供 3 种分区方式：双指针法、挖坑法、Hoare 法。
实现代码
1. 递归版（含优化）
// 对外接口：触发快速排序
public void quickSort(int[] arr) {
quick(arr, 0, arr.length - 1);
}
// 递归核心方法
private void quick(int[] arr, int left, int right) {
if (left >= right) return; // 子数组长度<=1，直接返回
// 优化1：小规模子数组（长度<=5）用插入排序（减少递归开销）
if (right - left <= 5) {
InsertSortRange(arr, left, right);
return;
}
// 优化2：三数取中（选left、mid、right的中间值作为基准，避免有序数组退化）
// int midIndex = getMiddleNumber(arr, left, right);
// swap(arr, left, midIndex); // 将基准值放到left位置
// 分区：获取基准值的最终位置
int pivot = partitionPointer(arr, left, right); // 双指针法分区
// int pivot = partition(arr, left, right); // 挖坑法分区
// int pivot = partitionHoare(arr, left, right); // Hoare法分区
// 递归排序左分区和右分区
quick(arr, left, pivot - 1);
quick(arr, pivot + 1, right);
}
// 辅助1：小规模子数组的插入排序
private void InsertSortRange(int[] arr, int start, int end) {
for (int i = start + 1; i <= end; i++) {
for (int j = i; j > start; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
}
}
}
}
// 辅助2：三数取中（获取基准值索引）
private int getMiddleNumber(int[] arr, int left, int right) {
int mid = (left + right) / 2;
// 比较left、mid、right，返回中间值的索引
if (arr[left] < arr[right]) {
if (arr[mid] > arr[right]) return right;
else if (arr[mid] < arr[left]) return left;
else return mid;
} else {
if (arr[mid] < arr[right]) return right;
else if (arr[mid] > arr[left]) return left;
else return mid;
}
}
2. 三种分区方式
// 分区1：双指针法（推荐，易理解、效率高）
private int partitionPointer(int[] arr, int left, int right) {
int pivotVal = arr[left]; // 基准值（left位置）
int pre = left; // 已处理区间的右边界（小于基准值的最后一个元素）
int cur = left + 1; // 当前遍历元素
while (cur <= right) {
// 若当前元素小于基准值，pre后移并交换（确保pre左侧都是小于基准值的元素）
if (arr[cur] < pivotVal && arr[++pre] != arr[cur]) {
swap(arr, pre, cur);
}
cur++;
}
swap(arr, pre, left); // 将基准值放到pre位置（最终位置）
return pre;
}
// 分区2：挖坑法
private int partition(int[] arr, int left, int right) {
int pivotVal = arr[left]; // 基准值，left位置形成“坑”
while (left < right) {
// 从右向左找小于基准值的元素，填入左坑
while (left < right && arr[right] >= pivotVal) {
right--;
}
arr[left] = arr[right]; // 右元素填入左坑，right位置形成新坑
// 从左向右找大于基准值的元素，填入右坑
while (left < right && arr[left] <= pivotVal) {
left++;
}
arr[right] = arr[left]; // 左元素填入右坑，left位置形成新坑
}
arr[left] = pivotVal; // 基准值填入最后一个坑
return left;
}
// 分区3：Hoare法（快速排序原始分区方式）
private int partitionHoare(int[] arr, int left, int right) {
int pivotVal = arr[left]; // 基准值
int pivotIndex = left; // 基准值原始索引
while (left < right) {
// 从右向左找小于基准值的元素
while (left < right && arr[right] >= pivotVal) {
right--;
}
// 从左向右找大于基准值的元素
while (left < right && arr[left] <= pivotVal) {
left++;
}
swap(arr, left, right); // 交换两个元素
}
swap(arr, pivotIndex, left); // 将基准值放到最终位置
return left;
}
3. 非递归版（栈实现，避免递归栈溢出）
// 非递归版：用栈存储待排序区间的左右边界
public void quickNor(int[] arr, int start, int end) {
Deque<Integer> stack = new LinkedList<>();
// 初始将整个数组区间压栈
quickNumPush(arr, start, end, stack);
while (!stack.isEmpty()) {
// 弹出右边界和左边界（栈是LIFO，先压左再压右，弹出时先右后左）
end = stack.pop();
start = stack.pop();
// 分区并压入新的待排序区间
quickNumPush(arr, start, end, stack);
}
}
// 辅助：分区并将非空区间
更多推荐
31
0- 0
已为社区贡献3条内容
所有评论(0)