经过持续的迭代更新,十大排序算法的内容和配套的可视化基本上都完成了,发布在我的网站 labuladong.online「数据结构及排序」章节的最后一章「十大排序算法原理及实现」:
自认为,我讲排序算法的特色在于能够讲清楚每个算法是怎么来的,为什么要这么做,这样做有什么优越之处,解决了前面的算法的什么痛点。
且所有排序算法均配备可视化面板,下面会简单截图展示几个。
比方说我首先把选择排序、冒泡排序、插入排序、希尔排序归为一类,因为它们都是从最简单的选择排序演变出来的,逐步改善选择排序的稳定性、运行效率,以及对于特殊情况(初始数组的有序度)的适应性。
选择排序的可视化,sortedIndex
维护有序边界,minIndex
寻找最小值:
我会把快速排序和归并排序归为一类,因为它们都需要二叉树的递归思想,分别属于二叉树前序遍历和后序遍历的应用。
归并排序的可视化,递归树为一棵二叉树,先排序左右两部分数组,最后进行合并:
接下来,堆排序单独分为一类,因为这种排序算法的思路完全基于二叉堆结构,其关键在于利用 sink, swim
方法在数组上原地建堆,原地删除元素。
堆排序的可视化,将待排序数组转化成完全二叉树,然后原地建立二叉堆,最后进行排序:
最后,计数排序、桶排序、基数排序归为一类,因为它们和前面的排序算法有本质的区别,它们不依赖元素的大小比较(非比较排序),而是依赖一个外部的有序参照系(比如数组索引),来完成排序。那么这样做有什么优势,有什么局限性,我都会进行讲解。
桶排序的可视化,将数组元素分配到多个桶中,对每个桶分别排序,最后合并所有有序桶:
总之,这几篇文章相当于是把我自己当时学习这些算法时思考的问题以及探索过程都记录下来了,应该能帮助大家学习排序算法以及背后的思想。
其他的就不举例了,大家可以自己去网站学习,或自行修改运行这些算法的代码进行可视化。
我还在持续地将可视化面板融入到已有的算法教程中,辅助大家学习理解。
最后,今天是 1024,《labuladong算法笔记》纸质书限时半价,先到先得!有阅读纸质书需求的读者赶紧入手: