1、简易桶排序 O(N+M)
// 待排序的数组 var arr = [8, 5,5,3,2] // 排序后的数组 var arr2 = [] // 桶容器，它的容量是由待排序数组中的最大值＋１决定的 var book = new Array(Math.max.apply(null, arr) + 1); // 初始化桶(m) for (var i = 0; i < book.length; i++) { book[i] = 0 } // 往桶中插入flag(n) arr.forEach(function (e, i) { book[e]++ }) // 循环桶并且查看flag。打印出桶的当前索引并且放入arr2中(m) book.forEach(function (e, index) { // 循环桶的flag数量，并且将当前桶的索引放入数组中（n） for (var i = 0; i < +e; i++) { arr2.push(index) } }) // 输出排序后的数组 console.log(arr2) /* 该排序方法名为：简易桶排序 时间复杂度的计算公式： O(m+n+m+n) = O(2*(m+m)) 时间复杂度可以忽略较小的常熟 O(m+n) 通常大写更有逼格 O（M+N） */
这是一个非常快的排序算法。桶排序从 1956 年就开始被使用，该算法的基本思想是由
E.J.Issac 和 R.C.Singleton提出来的。之前我说过，其实这并不是真正的桶排序算法，真正的
桶排序算法要比这个更加复杂。但是考虑到此处是算法讲解的第一篇，我想还是越简单易懂
越好，真正的桶排序留在以后再聊吧。需要说明一点的是：我们目前学习的简化版桶排序算
法，其本质上还不能算是一个真正意义上的排序算法。
2、冒泡排序 O(N^2 )
// 待排序的数组 var arr = [8, 5,5,3,2] // 最外部的循环其实没什么参与什么作为。 // 至于为什么要-1 其实很容易理解。因为最后一次的时候是不需要与自己比较的。所以绕过了 // 当然你减不减好像也没什么区别。只是减少次数来优化罢了 for (var i = 0;i < arr.length - 1; i++) { // 重点想清楚这里为什么要-i。其实也很简单，每一次轮回，都会把最大（小）数塞到最后。 // 所以下次就不必去比较最后一位了。同理，你减不减都无所谓。只是优化而已。但这个优化的幅度比较大 for (var j = 0; j < arr.length - i; j++) { // 这里的比大小判断决定排序是倒序还是正序 if (arr[j] > arr[j+1]) { // 以下代码只是普通的交换变量逻辑。没什么好说的。 // 如果真要说的话，只能说无论临时变量存储的是j的值还是j + 1的值都是可以的 var temp = arr[j + 1] arr[j + 1] = arr[j] arr[j] = temp
// [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]] // ES6d的语法，可直接代替上面3行代码 } } } console.log(arr) /* 该排序法名为：冒泡排序法 思路而言几乎没有难点，人人都能理解。但真要动手写的时候，却总有写不出或者想不出的情况。 原因就在于没有多写，写完也要看看套路。 双重循环，以及那些可有可无的-1 和 -i 以及注意外层的循环没有参与计算的作为。只有内存的j循环进行了比较或交换而已 */
冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是 O(N 2 )。这是
一个非常高的时间复杂度。冒泡排序早在 1956 年就有人开始研究，之后有很多人都尝试过
对冒泡排序进行改进，但结果却令人失望。如 Donald E. Knuth（中文名为高德纳，1974 年
图灵奖获得者）所说： “冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实
之外，似乎没有什么值得推荐的。 ”
快速排序法 O(NlogN)
// 待排序的数组 var a = [8, 5,5,3,2, 11,35,23,9] function quicksort (left_index, right_index) { // 异常情况 if (left_index > right_index) return; // 基准数，其实就是把数组中最左边的数拿来判断没什么 var temp = a[left_index];
var i = left_index; var j = right_index; // 一直循环，直到它们碰面 while (i != j) { // j哨兵由右往左前行，为了寻找比基准数小的值 while (a[j] >= temp && i < j) j--; // i哨兵由左往右前行，为了寻找比基准数大的值 while (a[i] <= temp && i < j) i++; // 这里重要的两点是： // 1、必须是右往左先走。 // 2、i必须小于j。如果他们碰面的话（i===j）按照游戏规则必须停止前行。 if (i < j) { var t = a[i]; a[i] = a[j]; a[j] = t; } } // 交换基准数和碰面的位置的数值 a[left_index] = a[i]; // 其实这里a[i]或者a[j]都可以。 反正就是要和基准数交换位置。这也是本排序最关键的地方 a[i] = temp; // 递归继续同样的游戏规则,下面还是一样，用i和j都可以，反正他们碰面了位置是一样的 quicksort(left_index, i - 1); quicksort(i+1, right_index); } quicksort(0, a.length - 1) console.log(a)
快速排序由 C. A. R. Hoare（东尼·霍尔，Charles Antony Richard Hoare）在 1960 年提出，
之后又有许多人做了进一步的优化。如果你对快速排序感兴趣，可以去看看东尼·霍尔
1962 年在 Computer Journal 发表的论文“Quicksort”以及《算法导论》的第七章。快速排序
算法仅仅是东尼·霍尔在计算机领域才能的第一次显露，后来他受到了老板的赏识和重用，
公司希望他为新机器设计一种新的高级语言。你要知道当时还没有 PASCAL 或者 C 语言这
些高级的东东。后来东尼·霍尔参加了由 Edsger Wybe Dijkstra（1972 年图灵奖得主，这个
大神我们后面还会遇到的，到时候再细聊）举办的 ALGOL 60 培训班，他觉得自己与其没有
把握地去设计一种新的语言，还不如对现有的 ALGOL 60 进行改进，使之能在公司的新机器
上使用。于是他便设计了 ALGOL 60 的一个子集版本。这个版本在执行效率和可靠性上都在
当时 ALGOL 60 的各种版本中首屈一指，因此东尼·霍尔受到了国际学术界的重视。后来他
在 ALGOL X 的设计中还发明了大家熟知的 case 语句，也被各种高级语言广泛采用，比如
PASCAL、C、Java 语言等等。当然，东尼·霍尔在计算机领域的贡献还有很多很多，他在
1980 年获得了图灵奖。