JS 家的排序算法 - 前端
引子
有句话如何说来着：
雷锋推倒雷峰塔，Java implements JavaScript.
那年，想凭借抱Java大腿火一把而不吝把本人名字给改了的JavaScript（原名LiveScript），如今早已光泽万丈。node JS的显现更是让JavaScript可之前后端通吃。虽然Java仍然制霸公司级软件开发领域（C/C + +的大神们不要打我。。。），但在Web的江湖，JavaScript可谓风头无两，坐上了头把交椅。
然而，在传统的运算机算法和数据构造领域，大多数专业教材和书籍的默许说话都是Java或者C/C+ +。这给比来想恶补算法和数据构造知识的我造成了必然困扰，由于我想寻觅一本以JavaScript为默许说话的算法书籍。当我理解到O’REILLY家的动物丛书系列里有一本叫做《数据构造与算法JavaScript描写》时，便兴奋的花了两天时间把这本书从头到尾读了一遍。它是一本很好的针对前端开发者们的入门算法书籍，可是，它有一个很大的缺陷，就是里面有许多明显的小错误，明显到就连我这种半路出家的程序猿都能一眼看出来。还有一个问题是，许多重要的算法和数据构造知识并没有在这本书里被提到。这些问题关于作为一个晚期强迫症患者的我来说几乎不克不及忍。于是乎，一言不合我就决议本人寻材料总结算法。那么，我就从算法领域里最根基的知识点——排序算法总结起好了。
我信赖以下的代码里必然会有某些bug或错误或语法不标准等问题是我本人没法发明的，所以敬请各位大神能够指出错误，由于只要在不竭改错的道路上我才能取得长久的进步。
十大经典算法排序总结对照
一张图概括：
主流排序算法概览
名词说明：
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存
不乱性：排序后2个相等键值的次序和排序此前它们的次序雷同
冒泡排序（Bubble Sort）
冒泡排序须知：
作为最简便的排序算法之一，冒泡排序给我的感受就像Abandon在单词书里显现的感受一样，每次都在第一页第一位，所以最熟知。。。冒泡排序还有一种优化算法，就是立一个flag，当在一趟序列遍历中元素没有发生交流，则证明该序列已经有序。但这种改善关于晋升机能来说并没有什么太大作用。。。
什么时候最快（Best Cases）：
当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊。。。。）
什么时候最慢（Worst Cases）：
当输入的数据是反序时（写一个for轮回反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗。。。）
冒泡排序动图演示：
Bubble Sort 动图演示 算法可视化来源：http://visualgo.net/
冒泡排序JavaScript代码实现：
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i arr[j+1]) { //相邻元素两两对照
var temp = arr[j+1]; //元素交流
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}选中排序（Selection Sort）
选中排序须知：
展现最不乱的排序算法之一，由于不管什么数据进去都是O(n2)的时间复杂度。。。所以用到它的时候，数据规模越小越好。独一的好处大概就是不占用额外的内存空间了吧。
选中排序动图演示：
Selection Sort 动图演示 算法可视化来源：http://visualgo.net/
选中排序JavaScript代码实现：
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i插入排序（Insertion Sort）
插入排序须知：
插入排序的代码实现虽然没有冒泡排序和选中排序那么简便粗暴，但它的道理应当是最容易懂得的了，由于只要打过扑克牌的人都应当能够秒懂。当然，假如你说你打扑克牌摸牌的时候从来不按牌的大小整理牌，那估量这辈子你对插入排序的算法都不会发生任何乐趣了。。。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。关于这种算法，得了懒癌的我就套用教科书上的一句经典的话吧：感乐趣的同学可以在课后自行研讨。。。
插入排序动图演示：
Insertion Sort 动图演示 算法可视化来源：http://visualgo.net/
插入排序JavaScript代码实现：
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i = 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}希尔排序（Shell Sort）
希尔排序须知：
希尔排序是插入排序的一种更高效力的实现。它与插入排序的不一样之处在于，它会优先比力间隔较远的元素。希尔排序的中心在于间隔序列的设定。既可以提早设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。在这里，我就使用了这种办法。
希尔排序JavaScript代码实现：
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap 0; gap = Math.floor(gap/3)) {
for (var i = gap; i = 0 && arr[j] > temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}归并排序（Merge Sort）
归并排序须知：
作为一种典型的分而治之思想的算法利用，归并排序的实现由两种办法：
- 自上而下的递归（所有递归的办法都可以用迭代重写，所以就有了第2种办法）
- 自下而上的迭代
在《数据构造与算法JavaScript描写》中，作者给出了自下而上的迭代办法。但是关于递归法，作者却认为：
However, it is not possible to do so in JavaScript, as the recursion goes too deep
for the language to handle.
然而,在 JavaScript 中这种方式不太可行,由于这个算法的递归深度对它来讲太深了。
说实话，我不太懂得这句话。意思是JavaScript编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。
和选中排序一样，归并排序的机能不受输入数据的影响，但展现比选中排序好的多，由于始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
归并排序动图演示：
Merge Sort 动图演示 算法可视化来源：http://visualgo.net/
归并排序JavaScript代码实现：
function mergeSort(arr) { //采纳自上而下的递归办法
var len = arr.length;
if(len =>快速排序（Quick Sort）
快速排序须知：
又是一种分而治之思想在排序算法上的典型利用。本质上来看，快速排序应当算是在冒泡排序根基上的递归分治法。
快速排序的名字起的是简便粗暴，由于一听到这个名字你就知道它存在的意义，就是快，并且效力高! 它是处置大数据最快的排序算法之一了。虽然Worst Case的时间复杂度到达了O(n2)，但是人家就是优异，在大多数状况下都比均匀时间复杂度为O(n log n) 的排序算法展现要更好，可是这是为什么呢，我也不知道。。。好在我的强迫症又犯了，查了N多材料终于在《算法艺术与信息学比赛》上寻到了中意的答案：
快速排序的最坏运转状况是O(n2)，比方说次序数列的快排。但它的平摊盼望时间是O(n log n) ，且O(n log n)记号中隐含的常数因子很小，比复杂度不乱等于O(n log n)的归并排序要小许多。所以，对绝大多数次序性较弱的随机数列而言，快速排序总是优于归并排序。
快速排序动图演示：
Quick Sort 动图演示 算法可视化来源：http://visualgo.net/
快速排序JavaScript代码实现：
function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;
if (left =>堆排序（Heap Sort）
堆排序须知：
堆排序可以说是一种利用堆的概念来排序的选中排序。分为两种办法：
- 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序摆列
- 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于落序摆列
堆排序动图演示：
Heap Sort 动图演示 算法可视化来源：http://www.ee.ryerson.ca/~courses/coe428/sorting/heapsort.html
堆排序JavaScript代码实现：
var len; //由于声明的多个函数都需要数据长度，所以把len设定成为全局变量
function buildMaxHeap(arr) { //创立大顶堆
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { //堆调整
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if (left arr[largest]) {
largest = left;
}
if (right arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (var i = arr.length-1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}计数排序（Counting Sort）
计数排序须知：
计数排序的中心在于将输入的数据值转化为键储备在额外开拓的数组空间中。
作为一种线性时间复杂度的排序，计数排序要求输入的数据必需是有肯定范畴的整数。
计数排序动图演示：
Counting Sort 动图演示 算法可视化来源：http://visualgo.net/
计数排序JavaScript代码实现：
function countingSort(arr, maxValue) {
var bucket = new Array(maxValue+1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}桶排序（Bucket Sort）
桶排序须知：
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数确实定。
为了使桶排序愈加高效，我们需要做到这两点：
- 在额外空间充沛的状况下，尽量增大桶的数目
- 使用的映射函数能够将输入的N个数据平均的分配到K个桶中
同时，关于桶中元素的排序，选中何种比力排序算法关于机能的影响至关重要。
什么时候最快（Best Cases）：
当输入的数据可以平均的分配到每一个桶中
什么时候最慢（Worst Cases）：
当输入的数据被分配到了统一个桶中
桶排序JavaScript代码实现：
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i maxValue) {
maxValue = arr[i]; //输入数据的最大值
}
}
//桶的初始化
var DEFAULT_BUCKET_SIZE = 5; //设定桶的默许数目为5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var buckets = new Array(bucketCount);
for (i = 0; i基数排序（Radix Sort）
基数排序须知：
基数排序有两种办法：
- MSD 从高位开端停止排序
- LSD 从低位开端停止排序
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用办法上有明显差别：
基数排序：按照键值的每位数字来分配桶
计数排序：每个桶只储备简单键值
桶排序：每个桶储备必然范畴的数值
LSD基数排序动图演示：
Radix Sort 动图演示 算法可视化来源：http://visualgo.net/
基数排序JavaScript代码实现：
//LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i写在最后
排序算法实在是博大精深，还有hin多hin多我没有总结到或者我本人还没弄清楚的算法，仅仅是总结这十种排序算法都把我写哭了。。。
因此，今后假如我把握了更多的排序姿势，我必然还会回来的！
引荐教程：《javascript根基教程》
以上就是JS 家的排序算法 - 前端的具体内容，更多请关注百分百源码网其它相关文章！
