排序优化
Varsion

选择合适的排序算法

如果对小规模数据进行排序,可以选择时间复杂度是 O(n2) 的算法

如果对大规模数据进行排序,时间复杂度是 O(nlogn) 的算法更加高效。

为了兼顾任意规模数据的排序,一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。

优化快速排序

最理想的分区点是:被分区点分开的两个分区中,数据的数量差不多。

  1. 三数取中法

从区间的首、尾、中间,分别取出一个数,然后对比大小,取这 3 个数的中间值作为分区点。这样每间隔某个固定的长度,取数据出来比较,将中间值作为分区点的分区算法,肯定要比单纯取某一个数据更好。但是,如果要排序的数组比较大,那“三数取中”可能就不够了,可能要“五数取中”或者“十数取中”。

  1. 随机法

随机法就是每次从要排序的区间中,随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好,但是从概率的角度来看,也不大可能会出现每次分区点都选得很差的情况,所以平均情况下,这样选的分区点是比较好的。时间复杂度退化为最糟糕的 O(n²) 的情况,出现的可能性不大。

快速排序是用递归来实现的。同时,递归要警惕堆栈溢出。为了避免快速排序里,递归过深而堆栈过小,导致堆栈溢出,有两种解决办法:

第一种是限制递归深度。一旦递归过深,超过了事先设定的阈值,就停止递归。

第二种是通过在堆上模拟实现一个函数调用栈,手动模拟递归压栈、出栈的过程,这样就没有了系统栈大小的限制。


  • Post title:排序优化
  • Post author:Varsion
  • Create time:2020-08-09 16:10:30
  • Post link:https://blog.varsion.cn/post/7418344d.html
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
Comments