排序算法（高级）

#算法 #排序

目录

• 1. 堆排序
• 2. 桶排序
• 3. 计数排序：整数数组
• 4. 基数排序
• 5. 对比

1. 堆排序

建堆操作 和 元素出堆操作 实现堆排序

1. 输入数组并建立小顶堆，此时最小元素位于堆顶。
2. 不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。

是非稳定

2. 桶排序

• 桶排序适用于处理体量很大的数据
• 注意下图中颜色
• 非原地排序：需要借助 k 个桶和总共 n 个元素的额外空间
• 桶排序是否稳定取决于排序桶内元素的算法是否稳定

3. 计数排序：整数数组

• 只针对非负整数
• 非原地的
• 稳定的？看具体实现，如果倒序遍历 nums 可以避免改变相等元素之间的相对位置

4. 基数排序

5. 对比