【初阶数据结构与算法】排序算法总结篇(每个小节后面有源码)（直接插入、希尔、选择、堆、冒泡、快速、归并、计数以及非递归快速、归并排序）_快速和希尔
文章目录
- 一、直接插入排序
- 二、希尔排序
- 三、直接选择排序
- 四、堆排序
- 五、冒泡排序
- 六、快速排序
- 七、归并排序
- 八、计数排序
- 九、非递归快速排序
- 十、非递归归并排序
本篇内容将从稳定性与复杂度等角度分析排序算法，列出它们的特点、优点以及缺点，希望大家有所收获，如果想更加细节地学习可以去看我之前写的各种排序算法的文章
一、直接插入排序
-
稳定性分析
（1）稳定性指的是在排序过程中，两个相等的元素在排序后的相对位置不会发生变化，直接插入排序是稳定的排序算法
（2）在排序过程中，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。由于相等元素在插入时不会改变它们在已排序序列中的相对位置（即如果两个相等元素在原序列中相邻，它们在排序后的序列中仍然相邻），因此直接插入排序是稳定的 -
时间复杂度：
（1）最优情况：O(n)（当输入序列已经是有序的情况下，每次插入操作都只需比较一次，无需移动元素）
（2）最劣情况：O(n^2)（当输入序列是逆序的情况下，每次插入操作都需要比较n次，并可能需要移动n-1个元素）
（3）平均情况：O(n^2)（对于随机排列的输入序列，平均需要进行n(n-1)/4次比较和移动操作） -
空间复杂度：O(1)
（1）直接插入排序是原地排序算法，不需要额外的存储空间（除了几个用于循环控制和辅助计算的变量） -
特点
（1）直接插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。其核心思想是逐步将每个待排序的元素插入到已排序序列的适当位置，直到所有元素都排序完毕，这个过程类似于我们日常整理扑克牌或书籍时的插入动作 -
优点
（1）实现简单直观，代码易于编写和理解
（2）对小规模数据或几乎已经有序的数据效率高，性能接近最优
（3）稳定性好，不会改变相等元素的相对位置
（4）原地排序，不需要额外的存储空间 -
缺点
（1）对大规模数据效率低，特别是当数据完全逆序时，时间复杂度达到最坏情况的O(n^2)
（2）需要频繁移动数据元素，特别是在插入位置靠前的情况下，会导致大量的数据移动操作
（3）不适用于数据规模较大且分布不均匀的情况，因为时间复杂度较高且性能不稳定。 -
源码：
//直接插入排序void InsertSort(int* arr, int n){ for (int i = 0; i < n - 1; i++){ int end = i, tmp = arr[end + 1];while (end >= 0){ if (arr[end] > tmp){ arr[end + 1] = arr[end];end--;}else{ break;}}arr[end + 1] = tmp;}}二、希尔排序
-
稳定性分析
（1）希尔排序是不稳定的排序算法
（2）在排序过程中，由于分组和增量递减的特性，相同大小的元素可能会因为分组后的插入排序操作而发生相对位置的改变。特别是当两个相等元素位于不同增量分组时，它们可能经过不同的插入排序路径，最终导致相对位置的变化 -
时间复杂度：
（1）最优情况：依赖于增量序列的选择和数据分布，但一般优于O(n^2)
（2）最劣情况：同样依赖于增量序列的选择，可能退化到O(n^2)，特别是在增量选择不当或数据分布极端的情况
（3）平均情况：通常认为在良好选择的增量序列下，希尔排序的平均时间复杂度介于O(n logn)和O(n^1.5)之间，但具体数值受多种因素影响 -
空间复杂度：O(1)
（1）希尔排序是原地排序算法，不需要额外的存储空间（除了几个用于循环控制和辅助计算的变量） -
特点
希尔排序通过引入增量序列，将数组分成若干个子序列，并对每个子序列进行直接插入排序。随着增量的递减，子序列的长度逐渐增加，直到增量为1时，对整个数组进行一次完整的插入排序。这种分组和增量递减的策略，使得希尔排序在初始阶段能够快速减少数据的无序度，为后续的直接插入排序提供更有利的环境 -
优点
（1）相对于直接插入排序，希尔排序在处理大规模数据时通常具有更高的效率，因为它能够更快地减少数据的无序度
（2）希尔排序的空间复杂度为O(1)，不需要额外的存储空间
（3）实现相对简单，代码易于理解和维护 -
缺点
（1）稳定性差，可能会改变相等元素的相对位置
（2）时间复杂度的具体表现依赖于增量序列的选择，选择不当可能导致性能下降 -
源码：
//希尔排序void ShellSort(int* arr, int n){ int gap = n;while (gap > 1){ gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){ int end = i, tmp = arr[end + gap];while (end >= 0){ if (arr[end] > tmp){ arr[end + gap] = arr[end];end -= gap;}else{ break;}}arr[end + gap] = tmp;}}}三、直接选择排序
-
稳定性分析
（1）稳定性：直接选择排序是不稳定的排序算法
（2）在排序过程中，每次从未排序部分选出最小（或最大）的元素后，都会将其与未排序部分的第一个元素进行交换。这种交换操作可能会破坏相同元素之间的原始顺序，因此直接选择排序不是稳定的排序算法 -
时间复杂度：
（1）最优情况：O(n^2)（无论输入序列如何，都需要进行n-1次选择操作，每次选择都需要遍历剩余未排序部分）
（2）最劣情况：O(n^2)（同最优情况，因为每次选择都需要遍历剩余未排序部分）
（3）平均情况：O(n^2)（同最优和最劣情况，因为直接选择排序的时间复杂度不依赖于输入序列的具体分布） -
空间复杂度：O(1)
（1）直接选择排序是原地排序算法，不需要额外的存储空间（除了几个用于循环控制和辅助计算的变量） -
特点
（1）直接选择排序通过反复从未排序部分选出最小（或最大）的元素，并将其放到已排序部分的末尾（或开头），从而逐步构建出有序序列。其核心思想是每次选择都确保选出的是当前未排序部分的最小（或最大）元素，然后将其放到正确的位置上 -
优点
（1）实现简单直观，代码易于编写和理解
（2）不需要额外的存储空间，空间复杂度为O(1)
（3）对于小规模数据或数据分布较为均匀的情况，性能尚可接受 -
缺点
（1）不稳定性可能导致相同元素的相对位置发生变化，这在某些应用场景中可能是不可接受的
（2）时间复杂度为O(n^2)，在处理大规模数据时效率较低
（3）在选择最小（或最大）元素时，需要遍历整个未排序部分，导致大量的比较操作
（4）对于几乎已经有序的数据，性能没有显著提升，因为每次选择仍然需要遍历剩余未排序部分 -
源码：
//直接选择排序(单向)void SelectSort1(int* arr, int n){ int begin = 0, end = n - 1;while (begin < end){ int mini = begin;for (int i = begin; i <= end; i++){ if (arr[i] < arr[mini])mini = i;}Swap(&arr[begin], &arr[mini]);begin++;}}//直接选择排序(双向)void SelectSort2(int* arr, int n){ int begin = 0, end = n - 1;while (begin < end){ int mini = begin, maxi = begin;for (int i = begin; i <= end; i++){ if (arr[i] < arr[mini])mini = i;if (arr[i] > arr[maxi])maxi = i;}if (maxi == begin)maxi = mini;Swap(&arr[begin], &arr[mini]);Swap(&arr[end], &arr[maxi]);begin++, end--;}}四、堆排序
-
稳定性分析
（1）稳定性：堆排序是不稳定的排序算法
（2）堆排序通过构建最大堆（或最小堆）来选择最大（或最小）元素，并将其放到已排序部分的末尾（或开头）。在这个过程中，如果两个相等元素位于不同子树中，它们可能会因为堆的调整（如堆化过程）和元素交换而发生相对位置的改变。因此，堆排序不能保证相同元素的相对位置在排序前后保持不变 -
时间复杂度：
（1）最优情况：O(n log n)（无论输入序列如何，堆排序都需要构建堆和调整堆，这两个过程的时间复杂度都是O(n log n)）
（2）最劣情况：O(n log n)（同最优情况，因为堆排序的时间复杂度不依赖于输入序列的具体分布）
（3）平均情况：O(n log n)（同最优和最劣情况，堆排序的时间复杂度在最好、最坏和平均情况下都是一致的） -
空间复杂度：O(1)
（1）堆排序是原地排序算法，不需要额外的存储空间（除了几个用于循环控制和辅助计算的变量）。所有操作都在原数组上进行，因此空间复杂度为O(1) -
特点
（1）堆排序是一种基于二叉堆数据结构的排序算法。它利用堆的性质（如最大堆或最小堆）来选择最大（或最小）元素，并逐步构建出有序序列。堆排序通过构建初始堆、不断交换堆顶元素与末尾元素、并调整剩余堆结构的过程来实现排序。
