mysorts

[Golang] 排序

学习各种排序的实验代码，主要参考《算法导论 第3版》，包括:

• 比较排序算法: 插入排序(Insertion Sort)、归并排序(Merge Sort)、堆排序(Heap Sort)、快速排序(Quick Sort)
• 非比较排序算法: 计数排序(Counting Sort)、基数排序(Radix Sort)、桶排序(Bucket Sort)
• 其他算法: 选择第n-th元素(Select n-th Element)、基于Binary Search Tree的排序(Tree Sort)

Tips

• 比较排序算法的最坏情况下界为 O(n*log(n)).
  • 即在最坏情况下, 任何比较排序算法都需要做至少 O(n*log(n)) 次比较.
• 非比较排序算法则不受此O(n*log(n))的限制, 可以在满足一些预设条件的前提下达到线性运行时间.

实验代码

• mysorts
  实现各种排序算法的实验代码的包, 其中比较排序算法主要基于sort.Interface来实现. (可通过命令go test -v -bench=. -benchmem来进行功能测试和Benchmark)
  • insertion_sort.go: O(n^2)
    • 实现《算法导论 第3版》 ch2.1 介绍的插入排序算法, 算法原理为从第2个元素开始遍历整个数组, 对每个元素, 向前进行遍历比较, Less()条件为false则Swap(), 直到Less()条件为true是退出. 由于是in-place实现, 空间复杂度为 O(1).
  • merge_sort.go: O(n*log(n))
    • 实现《算法导论 第3版》 ch2.3 介绍的归并排序算法. 算法原理为分治法(归并排序其实是二分法), 即将问题分解为2个子问题, 求解每个子问题(对于每个子问题可递归地继续分解, 直至不可分割), 然后递归地向上合并子问题的解.
      • aux array based implementation: 书上介绍的方法, 每次merge时需要对每个子问题申请一块辅助的子数组内存来暂存子问题, 空间复杂度为 O(n). 时间复杂度为 O(n*log(n)), 缺点为需要申请额外的空间, 以及无法使用典型的Swap接口来实现排序过程.
      • in-place implementation: 不需要辅助空间的实现, 借鉴了insertion_sort的方法来实现merge时的in-place. 空间复杂度为 O(1). Benchmark 实测的运行时间比aux array based implementation慢很多, 接近insertion_sort(比它稍快).
  • heap_sort.go: O(n*log(n))
    • 实现《算法导论 第3版》 ch6.1~6.4 介绍的堆排序算法. 算法原理为借助Heap(一般是用二叉堆) 的性质, 即root元素总是最大的(maxHeap中; 若是minHeap则反之). 首先构建出maxHeap, 那么root元素一定是数组中的最大值. 将root元素与数组最后元素交换, 再针对新的root节点维护堆的性质则又可以获得剩余堆(除刚刚的最大元素)中的最大值, 如此循环操作直至遍历完整个数组.
  • quick_sort.go: 平均运行时间接近最好运行时间 O(n*log(n)), 最坏情况为 O(n^2).
    • 实现《算法导论 第3版》ch7 介绍的快速排序算法, 包含固定主元(fixed pivot element)和随机主元(randomized pivot element)两种实现. 算法原理依然基于分治法, 即将问题分解为两个子问题分别求解. 而与归并排序不同的是, 在分解问题时总是选择一个pivot element, 将原数组分解为<= pivot lement和>= pivot element这样两个子问题, 并把pivot element放在两个子数组中间, 于是合并操作不需要再做任何事情.
    • 快速排序的运行时间主要取决于分治(partition)的过程, 期望能够将问题分割为两个尽量平衡的子问题(其实只要两个子问题为常数比例即可, 如9:1, 99:1均可达到 O(n*log(n)) ). 当分割的两个子数组其中一个长度为0时, 即最坏的情况 O(n^2).
  • counting_sort.go: O(k+n) 其中k为输入数组的最大元素值(限定输入数组元素值范围为0~k).
    • 实现《算法导论 第3版》ch8.2 介绍的计数排序. 其原理为引入一个以输入数组元素值为索引的辅助数组, 对于任意一个输入数组上的元素x, 直接在辅助数组上计算它前面有多少元素(也即输入数组中有多少元素小于x), 从而x就可以直接放在对应的位置上了. 其计算过程不需要任何的元素比较.
    • 不是比较排序, 所以可以不受比较排序的最坏情况下界 O(n*log(n)) 的限制.
    • 需要注意的是k的值要可控, 即输入数组中的最小值和最大值间的范围不能太大, 否则空间开销太大, 此方法就不适用了.
    • 当 k=O(n) 时, 其运行时间可简化为 O(n).
    • 另外, 当前的实现需要限定输入数组元素值范围为0~k, 实际可以比较容易地改造下以支持负数.
  • radix_sort.go: O(d(k+n)) 其中d为输入数组元素的最大位数, k为每位上的最大值.
    • 实现《算法导论 第3版》ch8.3 介绍的基数排序, 其原理为将输入数组看做一个d列n行的矩阵, 依次地从最低位至最高位对每列进行排序, 最终即可得到排序好的数组. 对于每列的排序需要依赖于稳定的排序算法(典型如counting sort就很适用).
    • 基数排序非常适合用来解决多关键字记录的排序问题, 典型如对于日期的排序(将年、月、日分别看做位).
    • 基数排序虽然看起来是线性排序, 运行低于快速排序等比较排序方法. 但实际使用时由于快速排序的每次循环更快、in-place等因素, 通常快速排序更好.
  • bucket_sort.go: 平均情况下 O(n), 且需假设前提为输入数组服从均匀分布.
    • 实现《算法导论 第3版》ch8.4 介绍的桶排序, 又一种非比较排序的方法. 其原理为将所有的输入元素均匀的放到n个桶中, 然后对每个桶内进行排序, 最后按次序遍历桶放回原数组即可得到排序后的结果. 输入数组服从均匀分布的前提下, 每个桶内的元素个数是接近且均匀的, 于是每个桶内排序(一般采用insertion sort, 当然也可以采用counting sort等方法)就会很快, 从而整体可以做到线性.
  • binary_search_tree_sort.go: 平均情况下 O(n*log(n)) 基于Binary Search Tree 实现的排序.
    • 具体为将输入数组的每个元素都作为key构建Binary Search Tree, 然后中序遍历整棵树, 即可得到按照key升序排序后的结果.
    • 构建树的过程平均情况下运行时间为 O(n*log(n)), 中序遍历的过程运行时间为 O(n), 故总体运行时间为 O(n*log(n)). 但由于Binary Search Tree 通常都通过指针链接的方式实现而并非基于数组等连续存储, 且并非一种in-place的方式, 工程实现时仅就排序而言效率通常不如其他基于数组的排序方式.
  • red_black_tree_sort.go: O(n*log(n)) 基于Red Black Tree 实现的排序.
    • 具体为将输入数组的每个元素都作为key构建Red Black Tree, 然后中序遍历整棵树, 即可得到按照key升序排序后的结果.
    • 构建树的过程平均情况下运行时间为 O(n*log(n)), 中序遍历的过程运行时间为 O(n), 故总体运行时间为 O(n*log(n)). 但由于Red Black Tree 通常都通过指针链接的方式实现而并非基于数组等连续存储, 且并非一种in-place的方式, 工程实现时仅就排序而言效率通常不如其他基于数组的排序方式.
      • 但由于Red Black Tree相对Binary Search Tree的平衡特性, 其实测效率还是要远高于基于 Binary Search Tree 实现的排序.
  • selection_nth_randomized.go, selection_nth.go: 期望运行时间 O(n), 最坏情况下 O(n^2).
    • 实现《算法导论 第3版》ch9.2~9.3 介绍的选择第n-th大的元素的问题, 更多可参考 Selection Algorithm - Wikipedia. 其原理是基于quick sort的partition, 同样采用分治法递归地将数组分割为两个子数组, 与quick sort不同的是, 只需要选取到的pivot element是第n-th元素即可返回, 且递归时两个子数组中只需要处理一个即可. 当取到了第n-th元素时, 即意味着数组中在其前面的都已经小于等于它, 而其后面的都已经大于等于它.
      • RandomizedSelectNth(): 基于quick sort的randomized partition实现, 实现代码非常简单.
      • SelectNth(): ch9.3 介绍的最坏情况为线性时间的算法. 原理是先通过分治的方法找到median, 然后每次都以median来分治子数组迭代. 主要是每次找median的设计比较复杂, 将原输入数组分隔成每5个元素一个子数组, 每个子数组内部排序以得到每个子数组的median, 再把这些median抽取成一个新的数组再迭代寻找median, 直至找到最终的median, 所以这个过程更像是一个稀疏化的过程.
        • 虽然书上介绍此方法是理论上最坏情况为线性时间, 但实现上远比RandomizedSelectNth()复杂. 并且迭代的次数更多, 还需要额外分配不少辅助内存, 实测的运行时间比RandomizedSelectNth()慢很多.
        • 另外, 为什么最坏情况是线性时间的推导部分没太看懂...
      • 猜测一下, std::nth_element 和 std::partial_sort 均应是基于此原理实现的.
        • 看了下VC 2017中这两个函数分别的实现, std::nth_element 确实是基于这个原理实现的, 但std::partial_sort则是基于的HeapSort.

References

• 《算法导论 第3版》
• Package sort
• Package heap
• Divide and Conquer Alogrithm
• Selection Algorithm - Wikipedia
• std::nth_element
• std::partial_sort
• Binary Search Tree
• Tree Traversal