GitBook《十大经典排序算法》JavaScript 实现
发布于 7 年前 作者 hustcc 7587 次浏览 来自 分享

十大经典排序算法

开源项目地址:https://github.com/hustcc/JS-Sorting-Algorithm by hustcc

GitHook 在线阅读地址:https://sort.hust.cc/

排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括:

十大经典排序算法 概览截图

关于时间复杂度

  1. 平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。
  2. 线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序;
  3. O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。 希尔排序
  4. 线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。

关于稳定性

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。

名词解释

n:数据规模

k:“桶”的个数

In-place:占用常数内存,不占用额外内存

Out-place:占用额外内存

稳定性:排序后2个相等键值的顺序和排序之前它们的顺序相同


GitBook 内容大纲

  1. 冒泡排序
  2. 选择排序
  3. 插入排序
  4. 希尔排序
  5. 归并排序
  6. 快速排序
  7. 堆排序
  8. 计数排序
  9. 桶排序
  10. 基数排序

本书内容来源于:

开源项目地址:https://github.com/hustcc/JS-Sorting-Algorithm by hustcc

GitHook 在线阅读地址:https://sort.hust.cc/

7 回复

做学术研究、算法入门很不错。不过国内90%的程序员1年估计也不会遇到一次用的时候。但是据说bat之类的公司面试特别喜欢面试这类题目。

能简单说一下动图里排序效果展现的实现原理么?一直想做这样一个动画效果。 From Noder

@stonephp 同感,特别是前端,工作中很少会遇到,大公司喜欢面这种题,我有个朋友前段时间面阿里,就死在算法上

@xuguangli 网上有的,找找

刷leetcode时会用到,不考虑时间复杂度某些测试样例会通不过

回到顶部