机凯种的排序算法评鉴指南

单纯排序的场景并不多,一般只是作为提高效率的手段。Google 每天上亿次访问,若使用线性搜索,所需时间会随着数据量的变大呈几何增长。但是,如果基于特定规则对数据进行排序,就可以方便的进行时间复杂度为 的二进制搜索或快速搜索,减少数据量对检索速度的影响。

咱初识编程那会,也是从所谓 N 大排序算法入门。然而在实际项目中,除了一些处理大量数据的脚本外,几乎没有遇到过手写排序函数的场景。一方面是因为大多数高级语言标准库中提供了通用排序算法,Python 的 sorted() 方法基于 time sort 算法实现,该算法是改进的 merge sort,在小区间使用 insertion sort。C 艹 的标准库也提供了 sort() 方法,基于 quick sortinsertion sort

另一方面,主要应用场景 CURD,比如用户注册,插入用户信息,为了将来检索方便,需要对用户名排序,但这部分的工作被数据库包揽了,才显得整个过程枯燥无味。但是数据来源不是数据库或没有数据库时,还需要自己动手,丰衣足食。

# 大量数据

数据是一次性提交的,此时优先考虑 quick sortmerge sort。两者的平均时间复杂度均为 ,但不是说它们性能相同,时间复杂度是指算法运行时间的增长趋势,只保留了最高次数项。下面简单分析一下两者的实现原理。

# Quick sort

先来看看 quick sort 的实现方法。

  • 选择参考值 pivot,一般是中位数。

  • 将小于 pivot 的部分放在左边,大于 pivot 的部分放在右边,再以 pivot 为界分割两个子数组。

  • 如果子数组包含多于 1 个元素,则对子数组递归应用以上步骤。

上述每轮操作都会分割出两个子数组,然后分别在子数组上递归进行下一轮操作。设原数组包含 n 个元素,分割时 pivot 都位于数组中间,则所需总递归次数 h,可看做不断将数组元素数量除以 2,从 n 个元素除到 1 个元素所需次数,即 。具体到每层递归,交换元素所需的运算次数为 ,由此可估算出平均时间复杂度为

# Merge sort

同样回想下 merge sort 的操作过程。

  • 将未排序的数组对半拆分为 2 个子数组,对子数组重复拆分,直到每个子数组只有一个元素。
  • 按从小到大的顺序递归合并子数组,生成新的已排序子数组,直到只剩下一个数组。

其中,拆分操作需要计算每个子数组的中点,运算次数为 。合并操作对所有子数组排序,每次递归都需要比较 n 个元素,所需运算次数为 。从 1 个元素的子数组合并到 n 个元素的已排序数组,需要的步骤数 h 就是树的高度,参考 quick sort 可得 ,时间复杂度为 。忽略拆分操作,平均时间复杂度为

# 如何选择

在尝试中发现,对于随机数列,quick sort 的平均速度比 merge sort 快,原因很多。算法方面,quick sort 将多个值与单个值进行比较,而 merge sort 每次比较的两项都是不同的,也就是说 quick sort 对内存的读取次数是 merge sort 的一半。运行环境方面,待排序的数据先从 ROM 读取到 RAM,程序访问任何内存地址的时间是常量,较少的访问次数,不仅能减少访问时间,还能提高 CPU 效率。

但是,如果数据量大到内存放不下,直接对硬盘中的数据进行排序,此时 merge sort 要远快于 quick sort。原因是 quick sort 直接在原数据上交换排序,硬盘的随机读写效率远不如内存。merge sort 顺序读写数据,读取速度远大于 CPU 处理速度,对性能影响不大。因此,用 quick sort 排序子数组,在合适阈值之上使用 merge sort 合并会更快。

实际上,就算是同一种算法,编写者不同,运行环境差异都会影响执行速度。如无必要,优先使用库函数提供的方法。

# 增量数据

数据是持续增加的,如数据处理脚本,此时只需要在正确的位置将新增元素添加到链表中。insertion sort 显然最合适。

  • 从未排序区间获取第一个未排序的元素。

  • 把它放在已排序区间的正确位置。

此过程使用双层循环实现,显而易见,平均时间复杂度为 。数据量大时毫无意义,但数据量小时却非常好用,尤其是在排好的数组中新增元素,时间复杂度降到了

# 小结

本文分析算法复杂度的方法,既不科学又不严谨,欢迎打脸。了解不同的排序算法非常有趣,但是在实践中并没有太多用,目前咱 99% 的排序和搜索需求都是由 SQL 的 ORDER BY 语句完成的,现阶段把数据库用好就够了。

# Reference

https://en.wikipedia.org/wiki/Quicksort

https://en.wikipedia.org/wiki/Merge_sort

https://en.wikipedia.org/wiki/Insertion_sort

Analysis of merge sort

© 2014 - 0202 Aimkiray.

Theme by Palette. 在各种〇〇之后并没有炸掉|ω・)ノ