02-排序算法 | FHCY-Study

type

status

date

slug

summary

冒泡排序

从头到尾依次比较相邻两个元素；

如果前一个比后一个大，就交换；

每趟排序结束，最大的元素被放在了当前范围的最后；

对剩下的前 n-1 个元素重复此过程，直到排序完成。

选择排序

每轮选择未排序区间中的最小（或最大）元素，放到已排序区间的末尾。

从索引 0 到 n-1 中选出最小值，与第 0 个元素交换

然后从 1 到 n-1 中选最小，与第 1 个元素交换

如此类推，直到第 n-2 轮结束

插入排序

将数组分为“已排序区间”和“未排序区间”，每次从未排序区中取出第一个元素，插入到已排序区的合适位置。

希尔排序

将整个数组按某个间隔（gap）划分为多个子序列，对每个子序列进行插入排序，然后逐步缩小间隔，最终 gap=1 时整体再做一次插入排序。

通过“预排序”，大幅减少了最终插入排序的交换次数。

快速排序

选一个“基准元素”（pivot），将数组划分为两个部分：

左边是所有 小于基准 的元素

右边是所有 大于等于基准 的元素

然后 对左右两部分递归排序

归并排序

一种经典的分治法（Divide and Conquer）排序算法，具有稳定性好、时间复杂度稳定为 等优点，适用于大数据量排序。

递归地将数组分成两部分，分别排序后再合并两个有序数组，直到整个数组有序。

堆排序

堆排序（Heap Sort）是一种利用堆（Heap）数据结构设计的排序算法，核心思想是：构建一个最大堆（或最小堆），不断取出堆顶元素，放到数组末尾，完成排序。时间复杂度：

构建最大堆（升序排序）；

将堆顶元素（最大值）与末尾元素交换；

剩下的元素重新调整为最大堆；

重复步骤 2~3，直到全部排序完成。

计数排序

计数排序（Counting Sort） 是一种非比较型排序算法，适用于数据范围较小、整数且可重复的排序场景。它通过统计每个数出现的次数，再按顺序输出，从而达到排序效果。

数据为 非负整数；

数据范围较小（最大值不宜过大）；

不要求原地排序，但可以实现稳定性。

桶排序

桶排序（Bucket Sort） 是一种非比较型排序算法，通过将输入元素分布到多个“桶”中，再对每个桶分别排序，最后按桶的顺序合并输出结果。

适用于：

✅ 输入数据均匀分布在一定范围内的实数/整数，且数据量大时非常高效。

确定桶的数量；

将每个元素按照其值映射到对应桶；

每个桶内部排序（可用快速排序/插入排序等）；

将所有桶按顺序合并。

基数排序

基数排序（Radix Sort） 是一种 非比较型排序算法，适用于整数或定长字符串排序。它通过对 位（数位） 进行多轮排序（从低位到高位），逐步构建最终有序结果。

对于整数排序：

先按照个位数排序；

再按照十位数排序；

然后是百位、千位，直到最高位排序。

每一轮用稳定排序算法（如计数排序）进行。

算法	平均时间复杂度	最坏情况	稳定性	是否原地
冒泡排序			✅ 稳定	✅ 原地
选择排序			❌ 不稳定	✅ 原地
插入排序			✅ 稳定	✅ 原地
希尔排序			❌ 不稳定	✅ 原地
快速排序			❌ 不稳定	✅ 原地
归并排序			✅ 稳定	❌ 非原地
堆排序			❌ 不稳定	✅ 原地
计数排序			✅ 稳定	❌ 非原地
桶排序			✅ 稳定	❌ 非原地
基数排序			✅ 稳定	❌ 非原地