JavaScript中常见排序算法详解

领域里最基础的知识点 排序算法总结起好了领域里最基础的知识点 排序算法总结起好了JavaScript中常见排序算法详解有句话怎么说来着：雷锋推倒雷峰塔， JavaimplementsJavaScript.当年，想凭借抱Java大腿火一把而不惜把自己名字给改了的 JavaScript（原名LiveScript），如今早已光芒万丈。 nodeJS的出现更是让JavaScript可以前后端通吃。虽然Java依然制霸企业级软件开发领域（ C/C++的大神们不要打我。。。），但在Web的江湖，JavaScript可谓风头无两，坐上了头把交椅。然而，在传统的计算机算法和数据结构领域，大多数专业教材和书籍的默认语言都是Java或者C/C++。这给最近想恶补算法和数据结构知识的我造成了一定困扰，因为我想寻找一本以 JavaScript为默认语言的算法书籍。当我了解到0'REILLY家的动物丛书系列里有一本叫做《数据结构与算法JavaScript描述》时，便兴奋的花了两天时间把这本书从头到尾读了一遍。它是一本很好的针对前端开发者们的入门算法书籍，可是，它有一个很大的缺陷，就是里面有很多明显的小错误，明显到就连我这种半路出家的程序猿都能一眼看出来。还有一个问题是，很多重要的算法和数据结构知识并没有在这本书里被提到。这些问题对于作为一个晚期强迫症患者的我来说简直不能忍。于是乎，一言不合我就决定自己找资料总结算法。那么，我就从算法我相信以下的代码里一定会有某些 bug或错误或语法不规范等问题是我自己无法发现的，所以敬请各位大神能够指出错误，因为只有在不断改错的道路上我才能取得长久的进步。十大经典算法一张图概括:审£序尊法'平旳时闻赴帝喪空闻电廉笈排序方就聲泡排序O(ns)O(n)O(n=)0(1)In-place穩定迄择排序0(同O(n50(na)0(1)In-place不穩定插、排序O(na)O(n)OM0(1)In-place稳宅0(nlogn)0(nlog2n)O(nlog2n)0(1)In—place不稳定怛幷排序0(nlogn)0(ntogr)0(nlogn)0(n)OuHplace税定快連排序0(nlogn)0(nlogr)OW)Oflogn)In-place不稳定堆排序0(nlogn)0(nlogr)O(nlogn)0(1)In-place不穩定计取排序0(n+k)0(n+k)Ofri+h)O(k)Out-place桶排茅0(n+k)0{n+h)O(R)0(n+k)Out-place穗定島數岀E序0(nxk)0{nxh)0(nXfe)0(n+fe)Out-place穗定名词解释：n:数据规模k:“桶”的个数In-place:占用常数内存，不占用额外内存Out-place:占用额外内存稳定性:排序后2个相等键值的顺序和排序之前它们的顺序相同JavaScriptJavaScript冒泡排序作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。。。冒泡排序还有一种优化算法，就是立一个flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作，用000什么时候最快当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊。000）什么时候最慢当输入的数据是反序时（写一个 for循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗。00）冒泡排序动图演示JavaScript 代码实现functionbubbleSort(arr){varlen=arr.length;for(vari=0;i<len;i++){for(varj=0;j<len-1-i;j++){if(arr[j]>arr[j+1]){ //相邻元素两两对比vartemp=arr[j+1]; // 元素交换arr[j+1]=arr[j];arr[j]=temp;TOC\o"1-5"\h\z}}}returnarr;}选择排序表现最稳定的排序算法之一，因为无论什么数据进去都是 0(n2)的时间复杂度。。。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。选择排序动图演示JavaScript 代码实现functionselectionSort(arr){varlen=arr.length;varminlndex,temp;for(vari=0;i<len-1;i++){minlndex=i;for(varj=i+1;j<len;j++){if(arr[j]<arr[minlndex]){ //寻找最小的数minlndex=j; 〃将最小数的索引保存TOC\o"1-5"\h\z}}temp=arr[i];arr[i]=arr[minIndex];arr[minlndex] =temp;}returnarr;}插入排序插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。 当然,如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌，那估计这辈子你对插入排序的算法都不会产生任何兴趣了。。。插入排序和冒泡排序一样，也有一种优化算法，叫做 拆半插入。对于这种算法，得了懒癌的我就套用教科书上的一句经典的话吧：感兴趣的同学可以在课后自行研究。。。插入排序动图演示JavaScript 代码实现JavaScriptfunctioninsertionSort(arr){varlen=arr.length;varprelndex,current;for(vari=1;i<len;i++){prelndex=i-1;current=arr[i];while(preIndex>=0&&arr[preIndex]>current){arr[preIndex+1]=arr[preIndex];preIndex--;TOC\o"1-5"\h\z}arr[preIndex+1]=current;}returnarr;}希尔排序希尔排序是插入排序的一种更高效率的实现它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者RobertSedgewick 提出的。在这里，我就使用了这种方法。JavaScript代码实现JavaScriptfunctionshellSort(arr){varlen=arr.length,temp,gap=1;while(gap<len/3){ //动态定义间隔序列gap=gap*3+1;}for(gap;gap>0;gap=Math.floor(gap/3)){for(vari=gap;i<len;i++){temp=arr[i];for(varj=i-gap;j>=0&&arr[j]>temp;j-=gap){arr[j+gap]=arr[j];TOC\o"1-5"\h\z}arr[j+gap]=temp;}}returnarr;}归并排序作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法:•自上而下的递归(所有递归的方法都可以用迭代重写，所以就有了第种方法)*自下而上的迭代在《数据结构与算法JavaScript描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：However,itisnotpossibletodosoinJavaScript,astherecursiongoestoodeepfortheIanguagetohandie.然而，在JavaScript中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。说实话，我不太理解这句话。意思是 JavaScript编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是0(nlogn)的时间复杂度。代价是需要额外的内存空间。归并排序动图演示归并排序JavaScript代码实现:JavaScriptif(len<2){returnarr;TOC\o"1-5"\h\z}varmiddle=Math.floor(len /2),left=arr.slice(0,middle),right=arr.slice(middle);returnmerge(mergeSort(left),mergeSort(right));}11functionmerge(left,right){varresult=[];15while(left.length&&right.length){if(left[0]<=right[0]){result.push(left.shift());}else{result.push(right.shift());}}23while(left.length)result.push(left.shift());26while(right.length)result.push(right.shift());29returnresult;}快速排序快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然WorstCase的时间复杂度达到了 0(n2)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 0(nlogn)的排序算法表现要更好， 可是这是为什么呢，我也不知道。。。好在我的强迫症又犯了，查了N多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：快速排序的最坏运行情况是 O(n2),比如说顺序数列的快排。但它的平摊期望时间是O(nlogn)，且O(nlogn)记号中隐含的常数因子很小， 比复杂度稳定等于O(nlogn)的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。快速排序动图演示快速排序JavaScript代码实现：JavaScript3functionquickSort(arr,left,right){varlen=arr.length,partitionlndex,left=typeofleft!='number'?0:left,right=typeofright!='number'?len-1:right;6if(left<right){partitionlndex=partition(arr,left,right);quickSort(arr,left,partitionlndex-1);quickSort(arr,partitionlndex+1,right);}returnarr;}14functionpartition(arr,left,right){ //分区操作varpivot=left, //设定基准值(pivot)index=pivot+1;for(vari=index;i<=right;i++){if(arr[i]<arr[pivot]){swap(arr,i,index);index++;TOC\o"1-5"\h\z}}swap(arr,pivot,index-1);returnindex-1;}

27functionswap(arr,i,j){vartemp=arr[i];arr[i]=arr[j];arr[j]=temp;}堆排序堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列2•小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列堆排序动图演示ProgramisnowresetHEAPSORTPQ0O堆排序JavaScript代码实现:tpeestReProgramisnowresetHEAPSORTPQ0O堆排序JavaScript代码实现:tpeestReJavaScriptvarlen;//因为声明的多个函数都需要数据长度，所以把JavaScript2functionbuildMaxHeap(arr){ 〃建立大顶堆len=arr.length;for(vari=Math.floor(len/2);i>=0;i--){heapify(arr,i);}}9functionheapify(arr,i){ //堆调整varleft=2*i+1,right=2*i+2,largest=i;14if(left<len&&arr[left]>arr[largest]){largest=left;}18if(right<len&&arr[right]>arr[largest]){largest=right;}22if(largest!=i){swap(arr,i,largest);heapify(arr,largest);}}28functionswap(arr,i,j){vartemp=arr[i];arr[i]=arr[j];arr[j]=temp;}34functionheapSort(arr){buildMaxHeap(arr);37for(vari=arr.length-1;i>0;i--){len设置成为全局变量len设置成为全局变量len--;heapify(arr,0);}returnarr;}计数排序计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。计数排序动图演示计数排序JavaScript代码实现:JavaScriptfunctioncountingSort(arr,maxValue){varbucket=newArray(maxValue+1),sortedIndex=0;arrLen=arr.length,bucketLen=maxValue+1;6for(vari=0;i<arrLen;i++){TOC\o"1-5"\h\zif(!bucket[arr[i]]) {bucket[arr[i]]=0;}bucket[arr[i]]++;}13for(varj=0;j<bucketLen;j++){while(bucket[j]>0){arr[sorted In dex++] = j;bucket。]--;}}20returnarr;}桶排序桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：在额外空间充足的情况下，尽量增大桶的数量使用的映射函数能够将输入的 N个数据均匀的分配到K个桶中同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。什么时候最快当输入的数据可以均匀的分配到每一个桶中什么时候最慢当输入的数据被分配到了同一个桶中桶排序JavaScript 代码实现：JavaScriptfunctionbucketSort(arr,bucketsize){if(arr.length===0){returnarr;}5vari;varminValue=arr[O];varmaxValue=arr[0];for(i=1;i<arr.length;i++){if(arr[i]<minValue){minValue=arr[i]; //输入数据的最小值}elseif(arr[i]>maxValue){maxValue=arr[i]; //输入数据的最大值}}16〃桶的初始化varDEFAULT_BUCKET_SIZE=5; //设置桶的默认数量为5bucketSize=bucketSize||DEFAULT_BUCKET_SIZE;varbucketCount=Math.floor((maxValue-minValue)/bucketSize)+1;varbuckets=newArray(bucketCount);for(i=0;i<buckets.length;i++){buckets[i]=[];}25〃利用映射函数将数据分配到各个桶中for(i=0;i<arr.length;i++){buckets[Math.floor((arr[i]-minValue)/bucketSize)].push(arr[i]);}30arr.length=0;for(i=0;i<buckets.length;i++){insertionSort(buckets[i])