目录一、排序基础这些概念你必须知道1.1 什么是排序1.2 稳定性一个容易被忽视的重要概念1.3 内部排序 vs 外部排序二、插入排序扑克牌的智慧2.1 直接插入排序2.2 希尔排序缩小增量排序三、选择排序每次选一个最值3.1 直接选择排序3.2 堆排序四、交换排序相邻元素互换4.1 冒泡排序4.2 快速排序重点方式一Hoare版方式二挖坑法方式三前后指针法快速排序的优化快速排序的非递归实现五、归并排序分而治之的典范5.1 基本思想5.2 归并排序的非递归实现5.3 海量数据的外部排序六、非基于比较的排序了解6.1 计数排序七、七大排序算法对比总结如何选择合适的排序算法八、常见面试题精讲九、总结与学习建议9.1 核心要点回顾9.2 学习建议写在前面本文基于《排序》课程内容整理结合个人学习笔记和实践经验编写。旨在帮助读者系统掌握七大基于比较的排序算法。如需深入学习建议配合官方教材和LeetCode题目进行练习。一、排序基础这些概念你必须知道1.1 什么是排序排序是将一组数据按照特定规则通常是升序或降序重新排列的过程。看似简单但不同的排序算法在不同的场景下性能差异巨大——有的适合小数据量有的适合大数据量有的稳定有的不稳定。1.2 稳定性一个容易被忽视的重要概念稳定性指的是当待排序序列中存在多个相同关键字时排序后这些元素的相对次序保持不变。举个例子假设我们有两条记录5a和5b下标a表示在原序列中排在前面原序列9, 5a, 2, 7, 3, 6, 4, 5b, 8, 0稳定排序的结果0, 2, 3, 4, 5a, 5b, 6, 7, 8, 95a仍然在5b前面不稳定排序的结果0, 2, 3, 4, 5b, 5a, 6, 7, 8, 95b跑到5a前面了什么时候需要稳定排序​ 比如按成绩排名成绩相同的人按学号排序。如果第一轮按成绩排序时不稳定第二轮再按学号排序时成绩的排序就可能被打乱。1.3 内部排序 vs 外部排序内部排序数据全部在内存中完成排序外部排序数据量大到无法一次性装入内存需要在内外存之间来回移动数据我们这篇文章讨论的主要是内部排序。二、插入排序扑克牌的智慧2.1 直接插入排序思想就像你打扑克牌时整理手牌一样——每次摸到一张新牌把它插入到手中已排好序的牌中的合适位置。public void insertSort(int[] array) { // 从第二个元素开始第一个元素视为已排序 for (int i 1; i array.length; i) { int tmp array[i]; // 待插入的元素 int j i - 1; // 从后往前找插入位置 for (; j 0 array[j] tmp; j--) { array[j 1] array[j]; // 元素后移 } array[j 1] tmp; // 插入 } }性能分析最好情况已有序O(n)只需遍历一遍最坏情况逆序O(n²)空间复杂度O(1)稳定性稳定特点数据越接近有序效率越高。2.2 希尔排序缩小增量排序希尔排序是插入排序的改进版。它先将整个序列分成若干组对每组进行插入排序然后逐步缩小分组最后对整个序列进行一次插入排序。public void shellSort(int[] array) { int gap array.length; while (gap 1) { gap / 2; // 缩小增量 // 对每个分组进行插入排序 for (int i gap; i array.length; i) { int tmp array[i]; int j i - gap; for (; j 0 array[j] tmp; j - gap) { array[j gap] array[j]; } array[j gap] tmp; } } }为什么希尔排序更快因为经过前几轮的预排序整个数组已经变得基本有序。最后一轮插入排序时数据移动的次数大大减少。性能分析时间复杂度大约 O(n^1.3) ~ O(n^1.5)具体与增量序列的选择有关空间复杂度O(1)稳定性不稳定分组时可能破坏相对顺序三、选择排序每次选一个最值3.1 直接选择排序思想每一轮从未排序的部分中选出最小的元素放到已排序部分的末尾。public void selectSort(int[] array) { for (int i 0; i array.length - 1; i) { int minIndex i; // 找到未排序部分的最小值下标 for (int j i 1; j array.length; j) { if (array[j] array[minIndex]) { minIndex j; } } // 交换 if (minIndex ! i) { int tmp array[i]; array[i] array[minIndex]; array[minIndex] tmp; } } }性能分析时间复杂度O(n²)无论数据有序与否都一样空间复杂度O(1)稳定性不稳定3.2 堆排序我们在之前的文章中已经详细介绍过堆。堆排序是利用堆这种数据结构进行的选择排序。思路升序排序 → 建大根堆每次将堆顶最大值与末尾元素交换对剩余元素重新调整为堆public void heapSort(int[] array) { // 1. 建大根堆 for (int parent (array.length - 1 - 1) / 2; parent 0; parent--) { shiftDown(array, array.length, parent); } // 2. 排序 int end array.length - 1; while (end 0) { // 堆顶与末尾交换 int tmp array[0]; array[0] array[end]; array[end] tmp; // 调整剩余元素 shiftDown(array, end, 0); end--; } } private void shiftDown(int[] array, int size, int parent) { int child 2 * parent 1; while (child size) { if (child 1 size array[child 1] array[child]) { child 1; } if (array[parent] array[child]) { break; } int tmp array[parent]; array[parent] array[child]; array[child] tmp; parent child; child 2 * parent 1; } }性能分析时间复杂度O(n log n)空间复杂度O(1)稳定性不稳定四、交换排序相邻元素互换4.1 冒泡排序思想相邻元素两两比较大的往后冒泡。public void bubbleSort(int[] array) { for (int i 0; i array.length - 1; i) { boolean swapped false; // 优化检测是否发生交换 for (int j 0; j array.length - 1 - i; j) { if (array[j] array[j 1]) { int tmp array[j]; array[j] array[j 1]; array[j 1] tmp; swapped true; } } if (!swapped) { break; // 没有交换说明已经有序 } } }性能分析最好情况已有序O(n)最坏情况O(n²)空间复杂度O(1)稳定性稳定4.2 快速排序重点快速排序是实际应用中使用最广泛的排序算法之一。它的核心思想是分治从序列中选一个基准值pivot将序列分成两部分左边都比基准小右边都比基准大递归地对左右两部分进行同样的操作方式一Hoare版public void quickSort(int[] array, int left, int right) { if (left right) { return; } int pivotIndex partitionHoare(array, left, right); quickSort(array, left, pivotIndex - 1); quickSort(array, pivotIndex 1, right); } private int partitionHoare(int[] array, int left, int right) { int pivot array[left]; int i left; int j right; while (i j) { // 从右往左找比pivot小的 while (i j array[j] pivot) { j--; } // 从左往右找比pivot大的 while (i j array[i] pivot) { i; } // 交换 swap(array, i, j); } // 将pivot放到正确位置 swap(array, i, left); return i; }方式二挖坑法private int partitionDig(int[] array, int left, int right) { int pivot array[left]; int i left; int j right; while (i j) { while (i j array[j] pivot) { j--; } array[i] array[j]; // 填坑 while (i j array[i] pivot) { i; } array[j] array[i]; // 填坑 } array[i] pivot; // 最后填入pivot return i; }方式三前后指针法private int partitionPointer(int[] array, int left, int right) { int prev left; int cur left 1; while (cur right) { if (array[cur] array[left] array[prev] ! array[cur]) { swap(array, cur, prev); } cur; } swap(array, prev, left); return prev; }快速排序的优化问题当数组基本有序时如果每次都选第一个元素作为pivot会导致分区极度不平衡退化为O(n²)。优化方案一三数取中法private int getMiddle(int[] array, int left, int right) { int mid (left right) / 2; // 找出三个数中中间大小的那个 if (array[left] array[right]) { if (array[mid] array[left]) { return left; } else if (array[mid] array[right]) { return right; } else { return mid; } } else { if (array[mid] array[right]) { return right; } else if (array[mid] array[left]) { return left; } else { return mid; } } }优化方案二小区间使用插入排序当递归到子区间足够小时比如长度小于10改用插入排序减少递归开销。快速排序的非递归实现public void quickSortNonRecursive(int[] array) { StackInteger stack new Stack(); stack.push(0); stack.push(array.length - 1); while (!stack.isEmpty()) { int right stack.pop(); int left stack.pop(); if (left right) { continue; } int pivotIndex partitionHoare(array, left, right); // 先压右半部分再压左半部分 stack.push(pivotIndex 1); stack.push(right); stack.push(left); stack.push(pivotIndex - 1); } }性能分析最好/平均时间复杂度O(n log n)最坏时间复杂度O(n²)数组基本有序且不做优化时空间复杂度O(log n)递归栈深度稳定性不稳定五、归并排序分而治之的典范5.1 基本思想归并排序的核心思想也是分治将序列不断二分直到每个子序列只有一个元素天然有序将两个有序的子序列合并成一个有序序列public void mergeSort(int[] array, int left, int right) { if (left right) { return; } int mid (left right) / 2; mergeSort(array, left, mid); // 排序左半部分 mergeSort(array, mid 1, right); // 排序右半部分 merge(array, left, mid, right); // 合并两个有序部分 } private void merge(int[] array, int left, int mid, int right) { int[] tmp new int[right - left 1]; int i left; // 左半部分指针 int j mid 1; // 右半部分指针 int k 0; // 临时数组指针 while (i mid j right) { if (array[i] array[j]) { tmp[k] array[i]; } else { tmp[k] array[j]; } } // 处理剩余元素 while (i mid) { tmp[k] array[i]; } while (j right) { tmp[k] array[j]; } // 将临时数组复制回原数组 for (int idx 0; idx tmp.length; idx) { array[left idx] tmp[idx]; } }5.2 归并排序的非递归实现public void mergeSortNonRecursive(int[] array) { int gap 1; // 每组元素个数 while (gap array.length) { for (int i 0; i array.length; i 2 * gap) { int left i; int mid Math.min(i gap - 1, array.length - 1); int right Math.min(i 2 * gap - 1, array.length - 1); if (mid right) { merge(array, left, mid, right); } } gap * 2; } }5.3 海量数据的外部排序归并排序的一个重要应用是外部排序。当数据量大到内存装不下时比如100G数据只有1G内存将100G文件切成200份每份512M对每份文件分别进行内部排序任意排序方式均可对这200份有序文件进行多路归并最终得到完整的有序文件性能分析时间复杂度O(n log n)无论数据分布如何空间复杂度O(n)需要临时数组稳定性稳定六、非基于比较的排序了解6.1 计数排序计数排序适用于数据范围集中的场景。它统计每个元素出现的次数然后按顺序输出。public void countingSort(int[] array) { if (array.length 0) return; // 1. 找到最大值和最小值 int min array[0], max array[0]; for (int num : array) { if (num min) min num; if (num max) max num; } // 2. 统计每个元素出现的次数 int range max - min 1; int[] count new int[range]; for (int num : array) { count[num - min]; } // 3. 按顺序输出 int index 0; for (int i 0; i range; i) { while (count[i] 0) { array[index] i min; count[i]--; } } }性能分析时间复杂度O(n range)range是数据范围空间复杂度O(range)稳定性稳定七、七大排序算法对比总结排序算法最好时间最坏时间平均时间空间复杂度稳定性冒泡排序O(n)O(n²)O(n²)O(1)✅ 稳定插入排序O(n)O(n²)O(n²)O(1)✅ 稳定选择排序O(n²)O(n²)O(n²)O(1)❌ 不稳定希尔排序O(n)O(n²)O(n^1.3)O(1)❌ 不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)❌ 不稳定快速排序O(n log n)O(n²)O(n log n)O(log n)❌ 不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)✅ 稳定如何选择合适的排序算法场景推荐算法数据量很小50插入排序简单且对小数据友好数据基本有序插入排序接近O(n)数据量大要求稳定归并排序数据量大不要求稳定快速排序综合性能最优内存紧张堆排序O(1)空间数据范围集中计数排序O(n)八、常见面试题精讲题目1对记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行直接插入排序当把第8个记录45插入到有序表时需要比较几次解答前7个元素排序后为(15, 23, 38, 54, 60, 72, 96)插入45时45 vs 96 → 1次45 vs 72 → 2次45 vs 60 → 3次45 vs 54 → 4次45 vs 38 → 停止共比较5次答案为C。题目2快速排序算法基于什么思想解答分治法Divide and Conquer答案为A。题目3以下排序方式中占用O(n)辅助存储空间的是解答归并排序需要O(n)的临时数组答案为D。九、总结与学习建议9.1 核心要点回顾插入排序扑克牌理牌思想数据越有序越快希尔排序插入排序的优化版分组预排序选择排序每次选最值效率不高但思路简单堆排序利用堆选数O(n log n)且空间O(1)冒泡排序相邻元素交换适合教学快速排序分治思想实际应用最广归并排序分治思想稳定且适合外部排序9.2 学习建议画图理解每种排序都画一遍执行过程手写代码不看参考自己默写一遍对比记忆对比各算法的时间、空间、稳定性刷题巩固在LeetCode上搜索sort标签如果你觉得这篇文章对你有帮助欢迎点赞收藏。后续我们将继续深入Java集合框架的更多内容敬请期待注本文为个人学习总结所有代码示例均为独立编写。建议读者在学习过程中结合官方教材和LeetCode题目进行练习验证。