跳转至

我看排序算法???

ChangeLog
20200331:
    - 创建Page,初版内容

TL;DR / 摘要

一些个人对排序算法的小记,并不是完全的教科书般的文章,只是篇随手笔记。

排序算法的一些特性/分类???

  • 稳定性
    • 如果一个排序算法在排序前后保证相等元素之间的相对位置,那么它就是稳定的, 反之则是不稳定的排序算法。
  • 比较排序/非比较排序
    • 非比较排序算法不通过比较2个元素之间的大小来进行排序,而比较排序的上限O(nlogn)。
  • 原地(in-place)
    • 不需要额外的辅助储存空间就可以完成排序
  • 内部排序/外部排序
    • 在排序过程中有无借助外部存储器(硬盘等)

排序算法的复杂性???

CheatSheet???

+----------------+----------+----------+----------+----------+--------+
|                | Best     | Average  | Worst    | Space    | Stable |
+----------------+----------+----------+----------+----------+--------+
| Bubble Sort    | O(n)     | O(n^2)   | O(n^2)   | O(1)     | Yes    |
+----------------+----------+----------+----------+----------+--------+
| Selection Sort | O(n^2)   | O(n^2)   | O(n^2)   | O(1)     | No     |
+----------------+----------+----------+----------+----------+--------+
| Insertion Sort | O(n)     | O(n^2)   | O(n^2)   | O(1)     | Yes    |
+----------------+----------+----------+----------+----------+--------+
| Quick Sort     | O(nlogn) | O(nlogn) | O(n^2)   | O(logn)  | No     |
+----------------+----------+----------+----------+----------+--------+
| Heap Sort      | O(nlogn) | O(nlogn) | O(nlogn) | O(1)     | No     |
+----------------+----------+----------+----------+----------+--------+
| Merge Sort     | O(nlogn) | O(nlogn) | O(nlogn) | O(n)     | Yes    |
+----------------+----------+----------+----------+----------+--------+
| Radix Sort     | -        | O(n*k/d) | O(n*k/d) | O(n*2^d) | Yes    |
+----------------+----------+----------+----------+----------+--------+
| Tim Sort       | O(n)     | O(nlogn) | O(nlogn) | O(n)     | Yes    |
+----------------+----------+----------+----------+----------+--------+
| Intro Sort     | O(nlogn) | O(nlogn) | O(nlogn) | O(logn)  | No     |
+----------------+----------+----------+----------+----------+--------+
n: data size
k: key size
d: digit size

计算复杂度???

  • 最好情况
  • 最坏情况
  • 一般情况

通常我们关心最坏情况和一般情况,而不会关心最好情况,因为最好情况下的性能没有什么意义。

另外一点值得注意的是计算复杂度经常使用大O表示法 来表示,但是我们也需要注意到被大O表示法所忽略的系数、低阶项这些,这些在n较小时会占到很重要的地位, 这也是一些混合排序算法在n较小时切换为像插入排序这些O(n^2)的看起来并不高效的算法,因为这些算法 在n较小时运行的反而比快速排序等要快。

空间复杂性???

在排序过程中使用的额外空间大小。

冒泡排序(Bubble Sort)???

冒泡排序是我认为的最简单的排序算法了,很容易实现,直接2层循环嵌套,然后交换元素就可以了。

冒泡排序是稳定的、原地的比较排序算法。

冒泡排序的优化???

  1. 使用一个flag来指示在某趟内层循环中有无发生元素交换,如果没有元素进行交换,那就说明排序完成, 可以提前结束排序
  2. 在外层循环的刚才中,内层循环的上下限可以缩短更多

冒泡排序的变种 - 梳排序(Comb Sort)???

梳排序和冒泡排序的关系就像是希尔排序和插入排序的关系。梳排序通过前面大gap的冒泡排序,来将元素 快速地移动到他们正确位置的附近,然后少量的普通冒牌排序就可以完成全部的排序了。

是非稳定的排序算法,但是我个人测试使用运行速度还比较快,但是随着n的增加,还是比不上快速排序这些。

选择排序(Selection Sort)???

选择排序是最直接的排序算法思想,每次选择合适的元素放入合适的位置。

可以实现top-k这样的功能,求最大或最小的k个元素。

选择排序是不稳定的(在最朴素的实现中)!这个我一开始是没有注意到的,不过想想,找到了合适的 元素和与当前元素的合适位置上的元素进行交换是,这个交换就有可能会破坏相等元素间的相对关系。

选择排序的写入次数是比较少的,不过并不是更少的,有个 Cycle Sort 它的写入次数可以做到n或者 小于n。

选择排序的优化/变种???

  • 在每趟内层循环中不仅找出最大值,同时也找出最小值,这样一趟内层循环就可以确定2个元素。
  • 在选择出合适元素后不使用交换而使用插入,这样就可以使得排序变成稳定,但是如果插入的成本很高( 比如说使用的是数组),这样就会有性能损失,不划算了

其实换个思路想的话,堆排序也是一种选择排序,只不过是堆排序通过维护了一个堆的数据结构,使得选择合适 (最大或最小)的元素的成本很低。

插入排序(Insertion Sort)???

插入排序是很受欢迎的排序算法啊,很多混合排序算法都选择使用插入排序来作为小量数据时的排序算法。

插入排序可以对链表进行排序。

插入排序是在线算法,可以不断地接受新的输入,这个点也是没有我以前没有想过的。

插入排序的优化/变种???

希尔排序(Shell Sort)???

通过前面大gap的插入排序,先使得数组整体基本有序,然后最后的普通插入排序所要做的操作就减少了很多, 就可以快速的完成排序。

希尔排序是不稳定的。

插入排序的优化???

  • 可以使用二分查找的方式来查找元素对应插入的位置,
  • 使用Skip List这个数据结构来储存(Need more research)
    • 类似的有Library Sort
    • 是一种空间换时间

快速排序(Quick Sort)???

使用分治(Divide and Conquer)的思想进行排序,算法整体分为3步:

  1. pivot的选择
  2. partition
  3. 进行递归调用

pivot的选择???

pivot的选择决定了算法的性能,最好的是选到能平分数组的pivot,就能达到最好情形了。选不好就会影响 性能了(如果每次都选到最大/最小的元素,那就是最坏情况了)。

pivot最普通的就是选择第一个,或者最后一个,不过这样选就看运气了,效果一般般。

另外一种方式是在数组的第一个、最后一个和中间一个3个元素中选中间值。

还有多pivot的变种。

partition的实现???

不同的partition的实现会影响效率,当然实现的难度的不一样,在参考链接中有一个讲的很好的。

快速排序的实际应用???

快速排序因为它优秀的性能,是一个很实用的排序算法,有大量的实际应用

快速排序的变种???

  • https://github.com/orlp/pdqsort
  • 随机快排(Randomized Quick Sort)
    • 在排序前先打乱下数组,这样就基本上就能跑到平均情况了。

堆排序(Heap Sort)???

先建立堆,然后在后续的操作中维护堆,达到快速找到最大/最小元素的效果。

堆,可以用来实现优先队列,是一个完全二叉树。

堆排序是不稳定的!

  1. 建立堆(如果是升序排序,就建立大顶堆,因为是从后面开始排的)
  2. 将堆顶的元素(最大值)和数组最后一个元素进行交换
  3. 然后将换到堆顶的元素按照堆的规则重新排下去,恢复堆的秩序,然后重复操作

堆的建立和维和的操作也是要认真思考和考量的。

堆排序因为它最快情况下也有O(nlogn)的性能,所以也有不少使用。

归并排序(Merge Sort)???

归并排序是稳定的,需要O(n)的额外空间,可以进行外部排序。

归并排序可以给链表排序,而且给链表排序就不怎么需要额外空间了。

  • 自顶向下(Top-Down)
    • 4 -> 2,2 -> 1,1,1,1 -> 2,2 -> 4
  • 自底向上(Bottom-Up)
    • 4 -> 1,1,1,1 -> 2,2 -> 4

因为这个切分不需要选择pivot,所以基本上所有情况都差不多吧?

基数排序( Radix Sort)???

基数排序很快,需要一些额外储存空间,但是是真的很快,OJ级别的快,看看参考链接!

稳定排序,非比较排序。

混合排序算法(Hybird Sort)???

取几种排序算法混合起来,取长补短,现在很多软件/库的标准排序算法都是使用了混合排序算法。

Tim Sort???

Tim Sort是Python List的排序算法,是基于Merge Sort和Insertion Sort混合而来的。

基础是Merge Sort,利用了数据本身存在的一些有序性来提高效率。

是稳定的排序算法。

Intro Sort???

先使用Quick Sort来进行排序,在Quick Sort层次过深(有可能陷入最坏情况)时切换为Heap Sort; 而在元素个数小于一定值是切换到Insertion Sort。

是不稳定的排序算法。

我的结论/想法???

排序算法需要解决的问题很简单,但是排序算法却是很复杂的,是需要正确实现和兼顾效率的,所以我认为 平时如果有少量数据需要排序,使用像冒泡排序那种实现简单的算法;如果有必要自己实现排序算法,则要 认真对边界情况进行测试!

References???