前言
上篇文章排序算法(二)我们介绍了10种排序算法,今天我们再来介绍一些其他的排序算法。
正文
今天我们介绍7种排序算法,它们如下:
Sort Name | Time(Best) | Time(Average) | Time(Worst) | Memory | Stable |
---|---|---|---|---|---|
BinaryTreeSort | O(n) | O(n * log n) | O(n * log n) | O(n) | Yes |
FlashSort | O(n) | O(n+k) | O(n^2) | O(n+k) | Yes |
PatienceSort | O(n) | O(n * log n) | O(n * log n) | O(n) | No |
StoogeSort | —— | —— | O(n^(log 3 / log 1.5)) | O(n) | Yes |
PancakeSort | O(n) | O(n^2) | O(n^2) | O(n) | No |
InPlaceMergeSort | —— | —— | O(n * (log n)^2) | O(1) | Yes |
StrandSort | O(n) | O(n^2) | O(n^2) | O(n) | Yes |
我们分别来看下。
二叉排序树排序(BinaryTreeSort)
简介及原理
二叉排序树排序(BinaryTreeSort),其原理是利用二叉树的特性,较小值依次比较放在树的左边,较大值依次比较放在树的右边,形成一个数据二叉树,然后将数据从左到右遍历出来即可。
算法描述
- 对于待排序数组array,构建一个二叉树tree,根节点可以取array[0],此时根节点的左右叶子节点为null;
- 对数组里每个元素,放入二叉树tree,如果小于根节点数值,应该放到左边,左边如果没有节点就创建一个并放入,如果有则需要比较其节点值和放入值大小,进而确定要放置的位置;右边同理;
- 进而我们会得到一个二叉树,我们从左向右遍历二叉树,就可以得到有序的数组。
动图演示
代码实现
相关代码如下:
1 | public class BinaryTreeSort { |
其他注意事项
这儿是否可以使用平衡二叉树?
可以,但平衡二叉树可以提高单个数据查找性能,我们这儿需要处理全部数据,同时平衡二叉树插入时涉及到树的旋转变化等,因此使用平衡二叉树的效率不一定比普通二叉树效率高。
某些情况下,使用平衡二叉树递归取值的栈深度会比普通二叉树要低。
该排序算法的时间复杂度:
时间复杂度(最好):O(n)
时间复杂度(平均):O(n * log n)
时间复杂度(最差):O(n * log n)
该排序算法空间复杂度:O(n)
- 该排序算法是稳定排序算法。
闪电排序(FlashSort)
简介及原理
闪电排序(FlashSort)是由Karl-Dietrich Neubert在1997年发展而来的一种排序算法,并且在欧洲理论计算机协会的新闻简报上发表了该算法。
该算法类似于桶排序,主要改进了对使用桶的预测。
我们知道,对于桶排序,我们首先要确定桶的数量,不能太多或者太少。
太多的话,桶中元素少,或者无用桶多,会浪费内存;太少的话,桶中元素多,每个桶中这些元素进行由大到小(或者由小到大)排序时就会比较耗时。(可参考HashMap理解桶排序)
因此桶的数量对排序性能的影响也不能忽视,FlashSort就是可以提前预知桶的大致数量及元素在桶中的位置,使其元素尽量利用每个桶,然后进行排序的。
FlashSort是如何预测的呢?
我们知道,桶排序桶的数量bucketCount一般为 INT[(Amax - Amin)/Asize] +1,对于如下数组[1,152,1000,8763,3,88,1000001,666,9999,100],根据公式可以算出需要的桶的数量为(1000001-1)/10 +1 = 1000001。
显然浪费了大量桶(内存),当然bucketCount也可以设置为数组长度,但是如果有一个长度为100000的数组,数组元素只有[0-9]之间的元素,我们显然设置的bucketCount也会不合适。
你一定会说可以取 INT[(Amax - Amin)/Asize] +1 或者数组长度中的最小值啊,哈哈,当然这么想也正确,但是即使这样,桶排序也不一定会完全把所有的桶充分利用,也会出现空桶的情况,因而造成内存浪费。
FlashSort就可以充分利用桶吗? 是的,其数据的位置主要依赖一个公式,如下:
K(Ai) = 1 + INT[ (m-1)(Ai-Amin)/(Amax-Amin) ]
这个公式可以算出数组的Ai项在桶中的位置。
比如如下数组[6,2,4,1,5,9],m如果取数组长度的话 m=6(也表明桶的数量为m个),我们可以算出:
- K(6) = 1 + 5 * 5/8 = 4
- K(2) = 1 + 5 * 1/8 = 1
- K(4) = 1 + 5 * 3/8 = 2
- K(1) = 1 + 5 * 0/8 = 1
- K(5) = 1 + 5 * 4/8 = 3
- K(9) = 1 + 5 * 8/8 = 6
可以看到极大的利用了桶,在数据量较多的情况下,与桶排序相比效果更明显。
可以看到上面我们m (桶的数量)取的数组长度,这显然不太合理,我们m一般取 0.1n (n代表数组长度),当m<1 时,m=1。这样保证桶尽量少的浪费的前提下,尽可能减少桶的使用数量。
如果数组过大,m过小,会导致每个桶内数据多,排序浪费较多时间;如果数据少,但桶较多,会导致内存浪费。所以对于具体数组,m也可以自己指定,以达到排序效率和空间的优化平衡。
算法描述
- 构建M个桶,M可以取0.1N (N数组长度)或者自定义;
- 根据FlashSort的K(Ai)计算公式,找到每个元素所在的桶,放入元素;
- 对于每个桶中的元素,如果元素个数大于等于2,需要进行内部排序;
- 从小到大(或者大到小)依次取出桶中元素,得到有序数组。
动图演示
代码实现
1 | public class FlashSort { |
其他注意事项
- 可以看到FlashSort只是优化了桶排序的元素存放桶的位置,使其尽量均匀分布于每个桶,而且选择合适的m值(桶数量)也是至关重要的(无论FlashSort或者桶排序);
该算法时间复杂度:
- 时间复杂度(最好):O(n)
- 时间复杂度(平均):O(n+k)
- 时间复杂度(最差):O(n^2)
该算法空间复杂度:O(n+k)
- 该算法为稳定排序算法。
耐心排序(PatienceSort)
简介及原理
耐心排序(PatienceSort)是将数组的元素分类成很多堆再串接回数组的一种排序算法。受到纸牌游戏的启发和命名。
我们在Windows系统上一定玩过纸牌游戏吧,我们知道,无序的纸牌要变为有序,我们需要将无序的纸牌通过操作进行有序分堆,最后在将这些堆纸牌合并生成有序的结果。
我们后面的动图也会模拟纸牌来看下耐心排序的执行过程。
算法描述
- 创建一个堆数组;
- 比较当前指向的元素和每个堆的第一个元素;
- 若当前元素比所有堆的第一个元素大,创建新的堆并加入到堆数组中;
- 如果当前元素比堆内的第一个元素小,就放入该堆头部作为新的第一个元素;
- 分类完后将每个堆有两种处理方式,可以通过合并后使用插入排序形成有序数列,也可以使用优先级队列依次取出元素完成排序。
PS:其实第4步,如果元素找到了多个符合条件的堆,可以放到任意一个堆里作为首元素。
动图演示
代码实现
这里的代码有两个,都比较好理解,第一个是将生成的堆合并,然后使用插入排序处理;第二个是生成堆后,使用优先级队列处理堆中数据。
大家都可以看下。
1 | public class PatienceSort { |
其他注意事项
该算法有一个变体,可以有效地计算给定数据中的最长增长子列和最长递减子列。比如有个数组[7,8,2,3,5,8,6,4,3,1,5,9],我们可以看到最长增长子列为[2,3,5,8],最长递减子列为[8,6,4,3,1]
我们使用耐心排序算法来看下:
算法描述的PS部分:如果元素找到了多个符合条件的堆,可以放到任意一个堆里作为首元素,我们在这儿放到最后一个符合的堆中。
- 根据耐心排序,我们可以把[7,8,2,3,5,8,6,4,3,1,5,9]数组按照上述算法分为如下堆数组: [3,7],[2,8],[5],[1,3,4,6,8],[5],[9]。显而易见最长递减子列为[1,3,4,6,8]的反向序列。
- 我们对于上述所讲的算法,也可以反过来,即比较当前指向的元素和每个堆的第一个元素,如果当前元素大于该堆第一个元素,在进行放入操作,这样可以得到如下堆数组:[8,7],[8,5,3,2],[6],[4],[3],[9,5,1]。显而易见[8,5,3,2]是最长递增子列的反向序列。
该排序算法时间复杂度:
- 时间复杂度(最好):O(n)
- 时间复杂度(平均):O(n * log n)
- 时间复杂度(最差):O(n * log n)
该排序算法空间复杂度:O(n)
- 该排序算法为不稳定排序算法
臭皮匠排序(StoogeSort)
简介及原理
臭皮匠排序(StoogeSort)是一种低效的递归排序算法,是由Howard、Fine等教授提出的所谓“漂亮的”排序算法,代码很漂亮但是很耗时。
臭皮匠排序翻译的由来:因为这个排序和3有很大关系(3个臭皮匠)。
我们来看下算法描述:
算法描述
- 如果最后一个值小于第一个值,则交换这两个数;
- 如果当前集合元素数量大于等于3:
- 使用臭皮匠排序前2/3的元素;
- 使用臭皮匠排序后2/3的元素;
- 再次使用臭皮匠排序前2/3的元素。
动图演示
代码实现
1 | public class StoogeSort { |
其他注意事项
- 该算法是一种低效的递归排序算法,甚至慢于冒泡排序,相比经典排序,臭皮匠排序性能十分差;
该算法的时间复杂度:
时间复杂度(最差):O(n^(log 3 / log 1.5))
该算法的空间复杂度:O(n)
- 该排序算法为稳定排序算法。
煎饼排序(PancakeSort)
简介及原理
煎饼排序(PancakeSort),我们对于排序数组,可以看成一叠大大小小的煎饼,假设我们有一把锅铲,可以每次从任意位置铲起上方全部煎饼并翻面,最终我们可以实现按煎饼大小进行排序的煎饼堆。
比如对于一个数组 [3,1,3,6,8,2,7,1],我们把它看成煎饼堆,则我们使用“锅铲”翻转的过程如下:
- [3,1,3,6,8,2,7,1] 初始化
- [8,6,3,1,3,2,7,1] 先把“大煎饼”8翻转到上面
- [1,7,2,3,1,3,6,8] 再把“大煎饼”8翻转到下面
- [7,1,2,3,1,3,6,8] 再把“第二大煎饼”7翻转到上面
- [6,3,1,3,2,1,7,8] 再把7翻转到下面
- [1,2,3,1,3,6,7,8] 再把6翻转到下面
- [3,2,1,1,3,6,7,8] 再把3翻转到上面
- [1,1,2,3,3,6,7,8] 再把3翻转到下面,完成排序
算法描述
- 对于待排序数组,找到最大值最小值及索引;
- 将最大值翻转到顶部,在翻转到数组底部;
- 此时再从未排序数组里找到最大值及索引,重复1、2过程。
动图演示
代码实现
1 | public class PancakeSort { |
其他注意事项
煎饼排序的一个问题变种为焦煎饼排序,即对于我们的煎饼,每张煎饼都有一面是烤焦的,最终除了按照大小排序以外还要让所有焦面向下;
焦煎饼问题: 比如对于上面的[3,1,3,6,8,2,7,1]数组,它们的右面都是“焦”的,我们按照上面的步骤走,会发现当执行到第4步得到[7,1,2,3,1,3,6,8],其中[7,1][3,1,3,6,8]是焦面向下,[2]是焦面向上的,我们执行第5步把7翻转到底下时,7的焦面就向上了,就不符合要求了,因此这时候我们需要在单独翻转一次“煎饼”7,然后把[7,1,2,3,1,3,6]整个翻转一下。
关于这部分的代码我就略过了,有兴趣的同学可以自己写一下。关于如何表示焦煎饼的正反两面也可以思考下。
煎饼排序的时间复杂度:
- 时间复杂度(最好):O(n)
- 时间复杂度(平均):O(n^2)
- 时间复杂度(最差):O(n^2)
该排序算法的空间复杂度:O(n)
- 该排序算法是一种不稳定排序算法。
原地归并排序(InPlaceMergeSort)
简介及原理
原地归并排序(InPlaceMergeSort)是归并排序(MergeSort)的一个变种。
我们知道,当使用归并排序时,我们需要借助辅助数组。原地归并排序可以使我们不使用辅助数组即可完成目标数组的排序。
算法描述
- 将长度为n的数组分为两个n/2的子序列;
- 对两个子序列分别进行归并排序;
- 将两个排序好的子序列合并成一个最终的排序序列。
动图演示
代码实现
1 | public class InPlaceMergeSort { |
其他注意事项
该排序的时间复杂度与归并排序相当:
时间复杂度(最差):O(n * (log n)^2)
由于未使用辅助数组,因此该排序的空间复杂度为:O(1)
- 该排序为稳定排序算法。
Strand排序(StrandSort)
简介及原理
Strand排序(StrandSort)又称串排序、线排序,其原理主要和子有序数组有关。
这儿的子有序数组是这样定义的:比如一个数组[5,3,7,8,2,1,9],则它的子有序数组为[5,7,8,9],此时原数组变为[3,2,1],其中子有序数组为[3],依次类推……得到最终子有序数组为[5,7,8,9],[3],[2],[1]。
得到子有序数组后将它们合并为新的有序数组。
比如数组[7,9,6,3,2,5,8,1],我们使用Strand排序:
- [7,9,6,3,2,5,8,1] 得到子有序数组和另一个子数组 [7,9][6,3,2,5,8,1];
- [6,3,2,5,8,1] 得到子有序数组和另一个子数组 [6,8][3,2,5,1] ,将[7,9]和[6,8]有序合并得到[6,7,8,9];
- [3,2,5,1] 继续得到 [3,5][2,1], [3,5]与[6,7,8,9]合并得到[3,5,6,7,8,9];
- [2,1]得到[2][1],继续合并得到[1,2,3,5,6,7,8,9];
- [1,2,3,5,6,7,8,9]即为要求的有序数组。
算法描述
- 对于待排序数组,取首元素为基础数;
- 向后寻找子有序数组,原数组变为一个子有序数组和一个新的子数组;
- 对于新的子数组,继续1、2步逻辑,得到新的子子有序数组和另一个新的子子数组;
- 将子有序数组和子子有序数组合并成有序数组,新的子子数组重复上述逻辑。
动图演示
代码实现
这儿我们借助LinkedList实现StrandSort
1 | public class StrandSort { |
其他注意事项
该排序算法的时间复杂度如下:
- 时间复杂度(最好): O(n)
- 时间复杂度(平均): O(n^2)
- 时间复杂度(最差): O(n^2)
该排序算法的空间复杂度为: O(n)
- 该排序算法是稳定排序算法。
总结
今天我们了解了7种排序算法,这7种排序算法还是比较好理解的,我们可以看到,各个排序都有各自的一些优点(某些个例除外),比如有的时间复杂度要低些,但空间复杂度要高些;有的空间复杂度低,但是时间复杂度要高些;还有一些数据量小的情况下,可能经典排序(冒泡、插入、选择)效率要高,因此可以选择一个合适的阈值,当要排序的数组部分数据量小时,我们可以使用它们代替。
比如归并排序,如果数组较小,就没必要继续归并,而采用插入排序可能会提高效率等。
所以后面我们会介绍一些经典的混合排序,还有一些基于某些原理的排序等。