首页
学习
活动
专区
工具
TVP
发布

使用 Go 实现快速排序

原文作者:smallnest

快速排序(quick sort)号称是二十世纪最伟大的十大算法之一(The Best of the 20th Century: Editors Name Top 10 Algorithms), 但是快速排序也是最不容易实现的排序算法之一 。虽然它的原理非常的简单,但实现起来很容易出错。 也曾因为快排导致腥风血雨甚至网站攻击事件。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

分治法:将问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

利用分治法可将快速排序的分为三步:

在数据集之中,选择一个元素作为”基准”(pivot)。

所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。这个操作称为分区 (partition) 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。

对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

快速排序平均时间复杂度为,最坏情况为,不稳定排序。

快速排序一般实现为原地排序(in-place),因为非原地排序会设计到大量的容器创建和对象复制。

本文实现了两种快速排序,一种是单线程的快速排序,一种是一定数量的goroutine并行的快速排序。

同时也增加了标准库排序算法和timsort算法的比较。

下面是算法实现:

版权申明:内容来源网络,版权归原创者所有。除非无法确认,我们都会标明作者及出处,如有侵权烦请告知,我们会立即删除并表示歉意。谢谢。

Golang语言社区

游戏服务器架构丨分布式技术丨大数据丨游戏算法学习

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180808B1RVAR00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券