面试题：排序算法的稳定性？（文末有福利）
回归面试题！
回答重点
-
稳定的排序算法：冒泡排序、插入排序、归并排序、计数排序。
-
不稳定的排序算法：选择排序、快速排序、堆排序、希尔排序。
扩展知识
1）冒泡排序（Bubble Sort）
原理：
冒泡排序是一种简单的排序算法。它通过多次遍历数组，依次比较相邻的两个元素，如果前者比后者大，就交换它们的位置。这样，最大的元素会像气泡一样逐渐"冒泡"到数组的末尾。这个过程会重复多次，直到没有元素需要交换。
时间复杂度：
-
最优时间复杂度：O(n) （当数组已排序时）
-
平均时间复杂度：O(n²)
-
最坏时间复杂度：O(n²)
空间复杂度：
-
O(1) （原地排序）
特点：
-
稳定
-
简单易懂，但效率较低，不适合大数据量的排序。
2）插入排序（Insertion Sort）
原理：
插入排序通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。类似于打牌时整理手中的牌。
时间复杂度：
-
最优时间复杂度：O(n) （当数组已排序时）
-
平均时间复杂度：O(n²)
-
最坏时间复杂度：O(n²)
空间复杂度：
-
O(1) （原地排序）
特点：
-
稳定
-
对于小规模数据或基本有序的数据，效率较高。
3）选择排序（Selection Sort）
原理：
选择排序每次从未排序的序列中找到最小（或最大）的元素，放到已排序序列的末尾，直到所有元素排序完毕。
时间复杂度：
-
最优时间复杂度：O(n²)
-
平均时间复杂度：O(n²)
-
最坏时间复杂度：O(n²)
空间复杂度：
-
O(1) （原地排序）
特点：
-
不稳定
-
简单但效率低，通常不用于大规模数据排序。
4）快速排序（Quick Sort）
原理：
快速排序是一种分治算法。通过选择一个"基准"元素，将数组分为两部分，一部分比基准小，一部分比基准大。然后对这两部分分别进行递归排序。
时间复杂度：
-
最优时间复杂度：O(n log n)
-
平均时间复杂度：O(n log n)
-
最坏时间复杂度：O(n²) （当选的基准值不合适时）
空间复杂度：
-
O(log n) （递归栈的空间）
特点：
-
不稳定
-
是实际应用中最常用的排序算法之一，性能通常较好。
5）归并排序（Merge Sort）
原理：
归并排序是一种典型的分治算法。将数组分成两个子数组，对每个子数组分别排序，然后将排好序的子数组合并。
时间复杂度：
-
最优时间复杂度：O(n log n)
-
平均时间复杂度：O(n log n)
-
最坏时间复杂度：O(n log n)
空间复杂度：
-
O(n) （需要额外的数组存放合并结果）
特点：
-
稳定
-
适合处理大规模数据和链表排序，但空间开销较大。
6）堆排序（Heap Sort）
原理：
堆排序利用堆这种数据结构来排序。先将数组构建成最大堆，然后将堆顶元素（最大值）与堆的最后一个元素交换，减小堆的范围，并重新调整堆，直到排序完成。
时间复杂度：
-
最优时间复杂度：O(n log n)
-
平均时间复杂度：O(n log n)
-
最坏时间复杂度：O(n log n)
空间复杂度：
-
O(1) （原地排序）
特点：
-
不稳定
-
在实际中较少单独使用，常用于一些需要优先队列的场景。
7）希尔排序（Shell Sort）
原理：
希尔排序是插入排序的一种改进版。它通过设置一个初始的步长，将数组按步长分为多个子序列，对每个子序列进行插入排序，然后逐步缩小步长，直到步长为1。
时间复杂度：
-
最优时间复杂度：O(n log n)（根据步长序列的选择）
-
平均时间复杂度：O(n log² n)
-
最坏时间复杂度：O(n log² n)
空间复杂度：
-
O(1) （原地排序）
特点：
-
不稳定
-
相对简单，且在大多数实际情况下效率较高，但最坏情况难以分析。
8）计数排序（Counting Sort）
原理：
计数排序适用于数据范围有限的情况。通过计数数组记录每个元素出现的次数，然后根据计数数组构建排好序的数组。
时间复杂度：
-
最优时间复杂度：O(n + k)
-
平均时间复杂度：O(n + k)
-
最坏时间复杂度：O(n + k) （k为数据范围）
空间复杂度：
-
O(n + k) （需要额外的计数数组）
特点：
-
稳定
-
非比较排序，适用于范围较小的整数排序，空间复杂度较高。
福利：
私聊作者或者添加下方联系领取Java高频面试集pdf