时间复杂度为O(nlogn)的排序算法

左手的ㄟ右手 2023-09-25 19:21 160阅读 0赞

四种复杂度满足该值的算法

    1. 希尔排序
    • 1.1 分组
    • 1.2 组内排序
    • 1.3 总结
    1. 堆排序
    • 2.1 建堆
    • 2.2 把堆首（最大值）和堆尾互换
    • 2.3 重新构建堆
    • 2.4 重复步骤
    • 2.5 动画演示
    1. 快速排序
    • 动画演示
    1. 归并排序
    • 博客链接
    1. 稳定性
    • 5.1 稳定性的定义
    • 5.2 四种算法的稳定性

1. 希尔排序

1.1 分组

分组前：
在这里插入图片描述
分组后：
在这里插入图片描述
分组结果：
在这里插入图片描述

1.2 组内排序

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

1.3 总结

在这里插入图片描述
希尔排序本质上是插入排序的优化，先对间隔较大的元素进行插入排序，完成宏观调控，然后逐步缩小间隔，最后一轮一定是间隔为 1 的排序，也就是插入排序。

2. 堆排序

2.1 建堆

堆分为大顶堆和小顶堆，大顶堆中最大的元素在堆顶，小顶堆中最小的元素在堆顶。

2.2 把堆首（最大值）和堆尾互换

2.3 重新构建堆

把堆的尺寸缩小1，并重新构建堆，目的是把新的数组顶端数据调整到相应的位置。

2.4 重复步骤

重复步骤2、3直到堆的尺寸为1。

2.5 动画演示

讲解视频：堆排序动画演示

3. 快速排序

动画演示

讲解视频：快速排序（双指针法）动画演示

4. 归并排序

博客链接

讲解博客：归并排序算法

5. 稳定性

5.1 稳定性的定义

待排序的序列中有两元素相等，排序之后它们的先后顺序不变。

5.2 四种算法的稳定性

稳定：归并排序
不稳定：希尔排序、堆排序、快速排序

参考资料：时间复杂度O(nlogn)的排序算法

发表评论

表情：
评论列表 （有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读