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

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

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

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

# 1. 希尔排序 #

## 1.1 分组 ##

分组前：  
![在这里插入图片描述][53595b0f0a694d8384a49db27d5184ee.png]  
分组后：  
![在这里插入图片描述][a364c04ca0154924bc8e24bce42ea235.png]  
分组结果：  
![在这里插入图片描述][b1316a8bb5c841a7b5759d2a8b86ab2a.png]

## 1.2 组内排序 ##

![在这里插入图片描述][2bb6ac42f6ab4c86a6f480cfd7675f0f.png]  
![在这里插入图片描述][5cbac97980194c859ebc9622d605cd8b.png]  
![在这里插入图片描述][5e3ee10a928046838b52a4b052c00779.png]  
![在这里插入图片描述][4479703db7ca4599820c4daf25805ad2.png]  
![在这里插入图片描述][c639e252a0fb4e27a77e05c3188e3e82.png]

## 1.3 总结 ##

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

# 2. 堆排序 #

## 2.1 建堆 ##

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

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

## 2.3 重新构建堆 ##

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

## 2.4 重复步骤 ##

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

## 2.5 动画演示 ##

讲解视频：[堆排序动画演示][Link 1]

# 3. 快速排序 #

## 动画演示 ##

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

# 4. 归并排序 #

## 博客链接 ##

讲解博客：[归并排序算法][Link 3]

# 5. 稳定性 #

## 5.1 稳定性的定义 ##

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

## 5.2 四种算法的稳定性 ##

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

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

[53595b0f0a694d8384a49db27d5184ee.png]: https://img-blog.csdnimg.cn/53595b0f0a694d8384a49db27d5184ee.png
[a364c04ca0154924bc8e24bce42ea235.png]: https://img-blog.csdnimg.cn/a364c04ca0154924bc8e24bce42ea235.png
[b1316a8bb5c841a7b5759d2a8b86ab2a.png]: https://img-blog.csdnimg.cn/b1316a8bb5c841a7b5759d2a8b86ab2a.png
[2bb6ac42f6ab4c86a6f480cfd7675f0f.png]: https://img-blog.csdnimg.cn/2bb6ac42f6ab4c86a6f480cfd7675f0f.png
[5cbac97980194c859ebc9622d605cd8b.png]: https://img-blog.csdnimg.cn/5cbac97980194c859ebc9622d605cd8b.png
[5e3ee10a928046838b52a4b052c00779.png]: https://img-blog.csdnimg.cn/5e3ee10a928046838b52a4b052c00779.png
[4479703db7ca4599820c4daf25805ad2.png]: https://img-blog.csdnimg.cn/4479703db7ca4599820c4daf25805ad2.png
[c639e252a0fb4e27a77e05c3188e3e82.png]: https://img-blog.csdnimg.cn/c639e252a0fb4e27a77e05c3188e3e82.png
[7f0f8caa954140afa105a58735465808.png]: https://img-blog.csdnimg.cn/7f0f8caa954140afa105a58735465808.png
[Link 1]: https://www.bilibili.com/video/BV1Mr4y1b7HX/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb
[Link 2]: https://www.bilibili.com/video/BV1rW4y1x7Kh/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb
[Link 3]: https://blog.csdn.net/qq_46130027/article/details/129650411
[O_nlogn]: https://blog.csdn.net/qq_43533956/article/details/123978524