JavaScript 中常见排序算法详解.docx

JavaScript中常见排序算法详解有句话怎么说来着：雷锋推倒雷峰塔，Java implements JavaScript.当年，想凭借抱Java大腿火一把而不惜把自己名字给改了的JavaScript （原 名LiveScript），如今早已光芒万丈。node JS的出现更是让JavaScript可 以前后端通吃。虽然Java依然制霸企业级软件开发领域（C/C + +的大神们 不要打我。），但在Web的江湖，JavaScript可谓风头无两，坐上了 头把交椅。然而，在传统的计算机算法和数据结构领域，大多数专业教材和书籍的默认 语言都是Java或者C/C+ +。这给最近想恶补算法和数据结构知识的我造成 了一定困扰，因为我想寻找一本以JavaScript为默认语言的算法书籍。当我 了解到O REILLY家的动物丛书系列里有一本叫做数据结构与算法 JavaScript描述时，便兴奋的花了两天时间把这本书从头到尾读了一遍。 它是一本很好的针对前端开发者们的入门算法书籍，可是，它有一个很大的 缺陷，就是里面有很多明显的小错误，明显到就连我这种半路出家的程序猿 都能一眼看出来。还有一个问题是，很多重要的算法和数据结构知识并没有 在这本书里被提到。这些问题对于作为一个晚期强迫症患者的我来说简直不 能忍。于是乎，一言不合我就决定自己找资料总结算法。那么，我就从算法 领域里最基础的知识点排序算法总结起好了。我相信以下的代码里一定会有某些bug或错误或语法不规范等问题是我自己 无法发现的，所以敬请各位大神能够指出错误，因为只有在不断改错的道路 上我才能取得长久的进步。十大经典算法一张图概括:排序算法平均时间寡株段盘好情;兄盘坏怖况更间夏希度排卉方式，富泡排序O(n2O(n)O(nz)。Inplace稳定选择排序O(n20（疽）。Inplace不崔定插入排序。行）0(n)0(*)0(1)Inplace柩定南尔排序0(n log n)O(n log2 n)O(n log2 n)。Inplace不巷定怛井排序0(n leg n)0(n tog n)O(n log n)On)Out-place樵定快建排序0(n leg n)0(n tog n)0时)O(log n)Inplace不褪定堆排房0(n log n)0(n log r)O(n log n)。Inplace不崔定计成排序O(n + k)0(n + k)0(n + ftO(k)OuHplace植定桶排序O(n + k)0(n + te)。邪）O(n + 前OuHplace基敷排序0(n x h)0(n x k)0(n x k)0(n + k)OuHplace弟定名词解释：n:数据规模k: 桶”的个数In-place:占用常数内存，不占用额外内存Out-place:占用额外内存稳定性:排序后2个相等键值的顺序和排序之前它们的顺序相同泡泡排序作为最简单的排序算法之一，冒泡排序给我的感觉就像Abandon在单词书 里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还 有一种优化算法，就是立一个flag，当在一趟序列遍历中元素没有发生交换， 则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作 用。什么时候最快 当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用 啊。） 什么时候最慢 当输入的数据是反序时（写一个for循环反序输出数据不就行了，干嘛要用 你冒泡排序呢，我是闲的吗。）泡排序动图演示JavaScript代码实现1 function bubbleSort(arr) (2 var len = arr.length;3 for (var i = 0; i < len; i+) (4 for (var j = 0; j < len - 1 - i; j+) (5 if (arrj > arrj+1) (/相邻元素两两对比6 var temp = arrj+1;/元素交换7 arrj+1 = arrj;8 arrj = temp;9 10 11 12 return arr;13 选择排序表现最稳定的排序算法之一，因为无论什么数据进去都是O(X)的时间复杂 度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占 用额外的内存空间了吧。选择排序动图演示JavaScript代码实日1 function selectionSort(arr) (2 var len = arr.length;3 var minIndex, temp;4 for (var i = 0; i < len - 1; i+) (5 minIndex = i;6 for (var j = i + 1; j < len; j+) (7 if (arrj < arrminIndex) (寻找最小的数8 minIndex = j;将最小数的索引保存9 10 11 temp = arri;12 arri = arrminIndex;13 arrminIndex = temp;14 15 return arr;16插入排序插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原 理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。当然， 如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌，那估计这辈子你 对插入排序的算法都不会产生任何兴趣了。插入排序和冒泡排序一样，也有一种优化算法，叫做拆半幅入。对于这种算 法，得了懒癌的我就套用教科书上的一句经典的话吧：感兴趣的同学可以在 课后自行研究。插入排序动图演示JavaScript代码实日JavaScript1 function insertionSort(arr) (234567891011121314蒂尔排序var len = arr.length;var preindex, current;for (var i = 1; i < len; i+) (preindex = i - 1;current = arri;while(preindex >= 0 && arrpreindex > current) ( arrpreindex+1 = arrpreindex;preindex-;return arr;arrpreindex+1 = current;希尔排序是插入排序的一种更高效率的实现。它与插入排序的不同之处在于， 它会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。既可 以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的 算法是算法（第4版的合著者Robert Sedgewick提出的。在这里，我 就使用了这种方法。JavaScript代码实日JavaScript1 function shellSort(arr) (23456789101112131415161718 归并排序return arr;var len = arr.length,temp,gap = 1;while(gap < len/3) (动态定义间隔序列gap =gap*3+1;for (gap; gap > 0; gap = Math.floor(gap/3) (for (var i = gap; i < len; i+) (temp = arri;for (var j = i-gap; j >= 0 && arrj > temp; j-=gap) ( arrj+gap = arrj;arrj+gap = temp;作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法:自上而下的递归(所有递归的方法都可以用迭代重写，所以就有了第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)的时间复杂度。代价是需要额外的内存 空间。归并排序动图演示归并排序JavaScript代码实JavaScript1 function mergeSort(arr) ( /采用自上而下的递归方法2 var len = arr.length;3 if(len < 2) (4 return arr;5 6 var middle = Math.floor(len/2),7 left = arr.slice(0, middle),8 right = arr.slice(middle);9 return merge(mergeSort(left),mergeSort(right);101112 function merge(left, right)13 14 var result =;151716 while (left.length && right.length) if (left0 <= right0) 18result.push(left.shift();19 else 20 result.push(right.shift();21 22 2324 while (left.length)25 result.push(left.shift();2627 while (right.length)28 result.push(right.shift();2930 return result;31 快速排序快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快 速排序应该算是在冒泡排序基础上的递归分治法。快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意 义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case的时间复杂度达到了 0(沱)，但是人家就是优秀，在大多数情况 下都比平均时间复杂度为0(n log n)的排序算法表现要更好，可是这是为什 么呢，我也不知道。好在我的强迫症又犯了，查了 N多资料终于在算 法艺术与信息学竞赛上找到了满意的答案：快速排序的最坏运行情况是0(沱)，比如说顺序数列的快排。但它的平摊期 望时间是0(n log n),且0(n log n)记号中隐含的常数因子很小，比复杂度 稳定等于0(n log n)的归并排序要小很多。所以，对绝大多数顺序性较弱的 随机数列而言，快速排序总是优于归并排序。快速排序动图演示快速排序JavaScript代码实JavaScript1 function quickSort(arr, left, right) (2 var len = arr.length,3 partitionIndex,4 left = typeof left != 'number' ? 0 : left,5 right = typeof right != 'number' ? len - 1 : right;67 if (left < right) (8 partitionindex = partition(arr, left, right);9 quickSort(arr, left, partitionindex-1);10 quickSort(arr, partitionindex+1, right);11 12 return arr;131415 function partition(arr, left ,right) (/分区操作16 var pivot = left,设定基准值(pivot)17 index = pivot + 1;18 for (var i = index; i <= right; i+) (19 if (arri < arrpivot) (20 swap(arr, i, index);21 index+;22 23 24 swap(arr, pivot, index - 1);25 return index-1;26 2728 function swap(arr, i, j) (29 var temp = arri;30 arri = arrj;31 arrj = temp;32 堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用 于升序排列2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用 于降序排列堆排序动图演示JavaScriptj 7I var len; 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量23 function buildMaxHeap(arr) ( 建立大顶堆4 len = arr.length;5 for (var i = Math.floor(len/2); i >= 0; i-) (6 heapify(arr, i);7 8 910 function heapify(arr, i) (/堆调整II var left = 2 * i + 1,12 right = 2 * i + 2,13 largest = i;1415 if (left < len && arrleft > arrlargest) (16 largest = left;17 1819 if (right < len && arrright > arrlargest) (20 largest = right;21 2223 if (largest != i) (24 swap(arr, i, largest);25 heapify(arr, largest);26 27 2829 function swap(arr, i, j) (30 var temp = arri;31 arri = arrj;32 arrj = temp;33 3435 function heapSort(arr) (36 buildMaxHeap(arr);3738 for (var i = arr.length-1; i > 0; i-) (39 swap(arr, 0, i);)(onwAXUUI CJJUWOSXUqunoo uo 丑 imj IIdMoSUAUfoisBf w-JJU UJBOJ g 寸(z寸 sHU)AJE8q I 寸 了由 。寸2 var bucket = new Array(maxValue+1),3 sortedIndex = 0;4 arrLen = arr.length,5 bucketLen = maxValue +1;67 for (var i = 0; i < arrLen; i+) (8 if (!bucketarri)(9 bucketarri = 0;10 11 bucketarri+;12 1314 for (var j = 0; j < bucketLen; j+) (15 while(bucketj > 0) (16 arrsortedIndex+ = j;17 bucketj-;18 19 2021 return arr;22 桶排序桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：1. 在额外空间充足的情况下，尽量增大桶的数量2. 使用的映射函数能够将输入的N个数据均匀的分配到火个桶中 同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重什么时候最快 当输入的数据可以均匀的分配到每一个桶中什么时候最慢当输入的数据被分配到了同一个桶中桶排序JavaScript代码实JavaScript1 function bucketSort(arr, bucketSize) (2 if (arr.length = 0) (3 return arr;4 56 vari;7 varminValue= arr0;8 varmaxValue= arr0;9 for (i = 1; i < arr.length; i+) (10 if (arri < minValue) (11 minValue = arri;/输入数据的最小值12 else if (arri > maxValue) (13 maxValue = arri;输入数据的最大值14 15 1617 /桶的初始化18 var DEFAULT_BUCKET_SIZE = 5;/设置桶的默认数量为 519 bucketSize = bucketSize | DEFAULT_BUCKET_SIZE;20 var bucketCount = Math.floor(maxValue - minValue) / bucketSize) + 1;21 var buckets = new Array(bucketCount);22 for (i = 0; i < buckets.length; i+) (23 bucketsi=;24 2526 /利用映射函数将数据分配到各个桶中27 for (i = 0; i < arr.length; i+) (28 bucketsMath.floor(arri - minValue) / bucketSize).push(arri);29 3031 arr.length = 0;323334353637383940 基数排序for (i = 0; i < buckets.length; i+) (insertionSort(bucketsi);/对每个桶进行排序，这里使用了插入排序for (var j = 0; j < bucketsi.length; j+) (arr.push(bucketsij);return arr;基数排序有两种方法1. MSD从高位开始进行排序2. LSD从低位开始进行排序基数排序vs计数排序vs桶排序 这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异:基邮府：根据键值的每位数字来分配桶计数SE序：每个桶只存储单一键值桶排府：每个桶存储一定范围的数值LSD基数排序动图演示：r3n nn rn rn rn nn 项叵1 巨百 cm 英zi 4 iijo rn排序 JavaScript 代码实JavaScript1 /LSD Radix Sort2 var counter =;3 function radixSort(arr, maxDigit) (4 var mod = 10;5 var dev = 1;6 for (var i = 0; i < maxDigit; i+, dev *= 10, mod *= 10) (7 for(var j = 0; j < arr.length; j+) (8 var bucket = parseInt(arrj % mod) / dev);9 if(counterbucket=null) (10 counterbucket=;11 12 counterbucket.push(arrj);13 14 var pos= 0;15 for(var j = 0; j < counter.length; j+) (16 var value = null;17 if(counterj!=null) (18 while (value = counterj.shift() != null) (19 arrpos+ = value;2021222324return arr;25