H5W3
当前位置:H5W3 > 其他技术问题 > 正文

六种知名排序实现原理

常见排序算法

选择

如果对小规模数据进行排序,可以选择时间复杂度是 O(n2) 的算法;如果对大规模数据进行排序,时间复杂度是 O(nlogn) 的算法更加高效。所以,为了兼顾任意规模数据的排序,一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。时间复杂度是 O(nlogn) 的排序算法不止一个,我们已经讲过的有归并排序、快速排序,后面讲堆的时候我们还会讲到堆排序。堆排序和快速排序都有比较多的应用,比如 Java 语言采用堆排序实现排序函数,C 语言使用快速排序实现排序函数。

归并排序为什么使用情况不多

优点:

快排在最坏情况下的时间复杂度是 O(n2),而归并排序可以做到平均情况、最坏情况下的时间复杂度都是 O(nlogn)

缺点:

归并排序并不是原地排序算法,空间复杂度是 O(n)。所以,粗略点、夸张点讲,如果要排序 100MB 的数据,除了数据本身占用的内存之外,排序算法还要额外再占用 100MB 的内存空间,空间耗费就翻倍了。

优化快速排序

快速排序在最坏情况下的时间复杂度是O(n^2)。

出现O(n^2)原因: 分区点选的不合理

如何选分区:

三数取中法

降低取的分区点不合理的概率,夺取几次取中间值,数组较大时可能要考虑“五数取中”或者“十数取中”

随机法

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

递归警惕堆栈溢出

  • 第一种是限制递归深度。一旦递归过深,超过了我们事先设定的阈值,就停止递归。
  • 第二种是通过在堆上模拟实现一个函数调用栈,手动模拟递归压栈、出栈的过程,这样就没有了系统栈大小的限制。

举例分析排序函数

C 语言中的qsort()

  • qsort() 会优先使用归并排序来排序输入数据
  • 要排序的数据量比较大的时候,qsort() 会改为用快速排序算法来排序
  • qsort() 并不仅仅用到了归并排序和快速排序,它还用到了插入排序。在快速排序的过程中,当要排序的区间中,元素的个数小于等于 4 时,qsort() 就退化为插入排序,不再继续用递归来做快速排序,因为我们前面也讲过,在小规模数据面前,O(n2) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长

JS 中的Array.sort()

主要采用TimSort算法

  • 元素个数 < 32, 采用二分查找插入排序(Binary Sort)
  • 元素个数 >= 32, 采用归并排序,归并的核心是分区(Run)
  • 找连续升或降的序列作为分区,分区最终被调整为升序后压入栈
  • 如果分区长度太小,通过二分插入排序扩充分区长度到分区最小阙值
  • 每次压入栈,都要检查栈内已存在的分区是否满足合并条件,满足则进行合并
  • 最终栈内的分区被全部合并,得到一个排序好的数组

Timsort的合并算法非常巧妙:

  • 找出左分区最后一个元素(最大)及在右分区的位置
  • 找出右分区第一个元素(最小)及在左分区的位置
  • 仅对这两个位置之间的元素进行合并,之外的元素本身就是有序的

golang标准库中的Sort()

快排 + 希尔排序 + 插排

数据量大于12时用快排(pivot的选择做了很多工作),小于等于12时用6作为gap做一次希尔排序,然后走一遍普通的插排(插排对有序度高的序列效率高)

java 1.8 中的排序

在元素小于47的时候用插入排序,大于47小于286用双轴快排,大于286用timsort归并排序,并在timesort中记录数据的连续的有序段的的位置,若有序段太多,也就是说数据近乎乱序,则用双轴快排,当然快排的递归调用的过程中,若排序的子数组数据数量小,用插入排序。

.NET中的Array排序

  • 三个以内的,直接比较,交换进行实现
  • 大于3个小于16个的,用的是插入排序进行的实现
  • 对于大于16,并且深度限制是0的,用的是堆排序实现的
  • 对于大于15,并且深度限制不是0的,使用的是快速排序;然后快速排序分区使用的也是三数取中法

Google v8中对QuickSort的实现

  • 数据规模在10以内的话使用快排;
  • 数据规模在10到1000之间时选择中点作为pivot进行快排;
  • 数据规模在1000以上时,每隔200到215个数选一个数,将选出来的数排序,选择中间值作为pivot进行快排;

而且还有几个细节:

1 是折半的时候用的是位运算;

2 是每一次遍历都会分成小于pivot,等于pivot,大于pivot的三个区间;

3 是小于pivot和大于pivot这两个区间中数据规模比较小的会递归执行QuickSort,数据规模大的会先通过while循环减小数据规模。

本文地址:H5W3 » 六种知名排序实现原理

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址