有一句话：雷锋打倒了雷锋塔，Java实现了JavaScript。当时想用JavaScript（以前叫LiveScript）改名跟Java一起流行。),已经在闪闪发亮。NodeJS的出现，让JavaScript包揽了前后端全部。虽然Java在企业级软件开发领域依然独领风骚（C/C++高手别打我。。。），但是在Web的江湖上，JavaScript可以说是大放异彩了，它已经占据了榜首。然而，在传统的计算机算法和数据结构领域，大多数专业教材和书籍的默认语言是Java或C/C++。这给最近想补充算法和数据结构知识的我带来了一些困扰，因为我想找一本默认语言是JavaScript的算法书。当得知O'REILLY的动物系列丛书里有一本书叫《数据结构与算法JavaScript描述》时，我激动不已，花了两天时间从头到尾看完了这本书。是一本非常好的前端开发入门算法书，但是它有一个很大的缺陷，就是里面有很多明显的小错误，明显到连我这样的半路出家都能一眼看出来.想办法。还有一个问题就是很多重要的算法和数据结构知识在这本书里都没有提到。这些问题对于身为强迫症晚期患者的我来说简直难以忍受。于是乎，一不同意就决定找资料总结一下算法。那么，我就从算法领域最基础的知识点——排序算法说起。我相信下面的代码中一定有一些我自己无法发现的BUG或错误或语法不规范，希望大家指出错误，因为只有在不断纠错的道路上，我才能获得长久的成功进步。十大经典算法图：名词解释：n：数据大小k：“桶”个数In-place：占用常量内存，不占用额外内存Out-place：占用额外内存的顺序相等的键值与排序前的顺序相同冒泡排序作为最简单的排序算法之一，冒泡排序给我的感觉就像单词书上出现的Abandon一样，每次都是第一页第一，所以最熟悉的。..冒泡排序还有一个优化算法，就是设置一个flag。当序列遍历过程中没有交换元素时，证明序列已经有序。但是这种改进对提高性能没有多大作用。..Whenisthefastestwheninputdataalreadypositiveorder（已经是正序了，我需要你的话冒泡排序有什么用...）当输入数据是倒序的时候Whenistheslowest（写一个是不够for循环倒序输出数据，干嘛用你的冒泡排序，我有空吗...）冒泡排序动画演示JavaScript代码实现函数bubbleSort(arr){varlen=arr.length;for(vari=0;iarr[j+1]){//两个相邻元素两次比较vartemp=arr[j+1];//元素交换arr[j+1]=arr[j];arr[j]=temp;}}}returnarr;}选择排序是最稳定的排序算法之一，因为没有无论输入什么数据，它的时间复杂度都是O(n2)。..所以在使用的时候，数据量越小越好。唯一的好处可能就是不占用额外的内存空间。选择排序动画演示JavaScript代码实现函数selectionSort(arr){varlen=arr.length;varminIndex,temp;for(vari=0;i=0&&arr[preIndex]>current){arr[preIndex+1]=arr[preIndex];preIndex--;}arr[preIndex+1]=current;}returnarr;}希尔排序希尔排序是插入效率更高排序的实现。它与插入排序的不同之处在于它首先比较距离较远的元素。希尔排序的核心在于区间序列的设置。间隔序列可以预先设置，也可以动态定义间隔序列。《算法（第4版》的合著者RobertSedgewick提出了动态定义区间序列的算法。在这里，我使用这种方法。JavaScript代码实现函数shellSort(arr){varlen=arr.length,temp,gap=1;while(gap0;gap=Math.floor(gap/3)){for(vari=gap;i=0&&arr[j]>temp;j-=gap){arr[j+gap]=arr[j];}arr[j+gap]=temp;}}returnarr;}归并排序作为典型的分治算法应用，归并排序有两种实现方式：自顶向下递归（所有的递归方法都可以用迭代重写，所以才有了第二种方式）自底向上迭代在《数据结构与算法JavaScript描述》中，作者给出了自底向上的迭代方式。但是对于递归的方法，笔者认为：但是在JavaScript中是做不到的，因为递归太深，语言无法处理。但是，这种方法在JavaScript中是行不通的，因为这种算法的递归深度对它来说太深了。说实话，我不是很理解这句话。是不是JavaScript编译器内存太小，递归太深容易造成内存溢出？也希望有大神指教。和选择排序一样，归并排序的性能不受输入数据的影响，但是性能比选择排序好很多，因为它总是O(nlogn)的时间复杂度。代价是需要额外的内存空间。归并排序动画演示归并排序JavaScript代码实现：functionmergeSort(arr){//采用自上而下的递归方法varlen=arr.length;if(len<2){returnarr;}varmiddle=Math.floor(len/2),left=arr.slice(0,middle),right=arr.slice(middle);returnmerge(mergeSort(left),mergeSort(right));}functionmerge(left,right){varresult=[];while(left.length&&right.length){if(left[0]<=right[0]){result.push(left.shift());}else{result.push(right.shift());}}while(left.length)result.push(left.shift());while(right.length)result.push(right.shift());returnresult;}快速排序快速排序是另一种分治思想在排序算法中的典型应用.从本质上讲，快速排序应该看作是一种基于冒泡排序的递归分治法。快速排序的名字简单粗暴，因为一听名字就知道它存在的意义，快速高效！它是处理大数据最快的排序算法之一。WorstCase的时间复杂度虽然达到了O(n2)，但是已经很优秀了。在大多数情况下，它们的性能优于平均时间复杂度为O(nlogn)的排序算法，但为什么呢？，我也不知道。..幸运的是，我的强迫症又发作了。查了N多资料，终于在《算法艺术与信息学竞赛》上找到了一个满意的答案：快速排序的最坏情况是O(n2)，比如对序号进行快速排序。但其摊销期望时间为O(nlogn)，O(nlogn)表示法中隐含的常数因子很小，远小于复杂度稳定等于O(nlog)的归并排序n).因此，对于绝大多数顺序较弱的随机数序列，快速排序总是优于归并排序。快速排序动画演示快速排序JavaScript代码实现：functionquickSort(arr,left,right){varlen=arr.length,partitionIndex,left=typeofleft!='number'?0:left,right=typeofright!='number'?len-1:right;if(left=0;i--){heapify(arr,i);}}functionheapify(arr,i){//堆调整varleft=2*i+1,right=2*i+2,largest=i;if(leftarr[largest]){largest=left;}if(rightarr[largest]){largest=对；}if（最大！=i）{swap（arr，i，最大）；heapify（arr，最大）；}}functionswap（arr，i，j）{vartemp=arr[i]；arr[i]=arr[j];arr[j]=temp;}functionheapSort(arr){buildMaxHeap(arr);for(vari=arr.length-1;i>0;i--){swap(arr,0,i);len--;heapify(arr,0);}returnarr;}计数排序计数排序的核心是将输入的数据值转换为key，存放在附加的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入数据必须是一定范围内的整数。计数排序动画demo计数排序JavaScript代码实现：functioncountingSort(arr,maxValue){varbucket=newArray(maxValue+1),sortedIndex=0;arrLen=arr.length,bucketLen=maxValue+1;for(vari=0;i0){arr[sortedIndex++]=j;bucket[j]--;}}returnarr;}桶排序桶排序是计数排序的升级版。它利用了函数的映射关系，而高效的关键就在于这个映射函数的确定。为了让桶排序更高效，我们需要做两件事：在额外空间足够的情况下，用于增加桶数的映射函数可以将输入的N个数据均匀分布到K个桶中。同时，对于桶中元素的排序，比较排序算法的选择对性能的影响非常重要。当输入数据可以均匀分配到每个桶时什么时候最快当输入数据分配到同一个桶时最慢Bucket排序JavaScript代码实现：functionbucketSort(arr,bucketSize){if(arr.length===0){returnarr;}vari;varminValue=arr[0];varmaxValue=arr[0];for(i=1;imaxValue){maxValue=arr[i];//输入数据的最大值}}//桶初始化varDEFAULT_BUCKET_SIZE=5;//设置桶的默认数量为5bucketSize=bucketSize||DEFAULT_BUCKET_SIZE;varbucketCount=Math.floor((maxValue-minValue)/bucketSize)+1;varbuckets=newArray(bucketCount);for(i=0;i
