常用排序算法之JavaScript实现

点击上方 \"程序员小乐\"关注, 星标或置顶一起成长

第一时间与你相约

每日英文

If you wait to do everything until you\'re sure it\'s right, you\'ll probably never do much of anything.

如果你等到每件事都确定是对的才去做，那你也许永远都成不了什么事。

每日掏心话

人其实挺矛盾的。总是希望被理解，又害怕别人看穿。主动，是因为在乎。

来自：ywang1724 | 责编：乐乐

链接：cnblogs.com/ywang1724/p/3946339.html

程序员小乐(ID:study_tech)第 692 次推文 图片来自网络

往日回顾：作为一名黑客，通过技术手段发现女朋友出轨了...

正文

笔试面试经常涉及各种算法，本文简要介绍常用的一些算法，并用JavaScript实现。

1、插入排序

1）算法简介插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。2）算法描述和实现一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；

• 取出下一个元素，在已经排序的元素序列中从后向前扫描；

• 如果该元素（已排序）大于新元素，将该元素移到下一位置；

• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

• 将新元素插入到该位置后；

• 重复步骤2~5。

• JavaScript代码实现：

• functioninsertionSort(array){ if(Object.prototype.toString.call(array).slice(8, -1) === \'Array\'){ for(vari = 1;i < array.length;i++){ varkey = array[i]; varj = i - 1; while(j >= 0 && array[j] > key){ array[j + 1] = array[j]; j--; } array[j + 1] = key; } returnarray; }else{ return\'array is not an Array!\'; }}




• 3）算法分析

• 最佳情况：输入数组按升序排列。T(n) = O(n)

• 最坏情况：输入数组按降序排列。T(n) = O(n2)

• 平均情况：T(n) = O(n2)

二、二分插入排序

1）算法简介二分插入（Binary-insert-sort)排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接插入排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。2）算法描述和实现一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；

• 取出下一个元素，在已经排序的元素序列中二分查找到第一个比它大的数的位置；

• 将新元素插入到该位置后；

• 重复上述两步。

• JavaScript代码实现：

• functionbinaryInsertionSort(array){ if(Object.prototype.toString.call(array).slice(8, -1) === \'Array\'){ for(vari = 1;i < array.length;i++){ varkey = array[i],left = 0,right = i - 1; while(left <= right){ varmiddle = parseInt((left + right) / 2); if(key < array[middle]){ right = middle - 1; }else{ left = middle + 1; } } for(varj = i - 1;j >= left;j--){ array[j + 1] = array[j]; } array[left] = key; } returnarray; }else{ return\'array is not an Array!\'; }}




• 3）算法分析

• 最佳情况：T(n) = O(nlogn)

• 最差情况：T(n) = O(n2)

• 平均情况：T(n) = O(n2)

三、选择排序

1）算法简介选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。2）算法描述和实现n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1..n]，有序区为空；

• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；

• n-1趟结束，数组有序化了。

• JavaScript代码实现：

• functionselectionSort(array){ if(Object.prototype.toString.call(array).slice(8, -1) === \'Array\'){ varlen = array.length,temp; for(vari = 0;i < len - 1;i++){ varmin = array[i]; for(varj = i + 1;j < len;j++){ if(array[j] < min){ temp = min; min = array[j]; array[j] = temp; } } array[i] = min; } returnarray; }else{ return\'array is not an Array!\'; }}




• 3）算法分析

• 最佳情况：T(n) = O(n2)

• 最差情况：T(n) = O(n2)

• 平均情况：T(n) = O(n2)

四、冒泡排序

1）算法简介冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。2）算法描述和实现具体算法描述如下：

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；

• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

• 针对所有的元素重复以上的步骤，除了最后一个；

• 重复步骤1~3，直到排序完成。

• functionbubbleSort(array){ if(Object.prototype.toString.call(array).slice(8, -1) === \'Array\'){ varlen = array.length,temp; for(vari = 0;i < len - 1;i++){ for(varj = len - 1;j >= i;j--){ if(array[j] < array[j - 1]){ temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } } } returnarray; }else{ return\'array is not an Array!\'; }}




• 3）算法分析

• 最佳情况：T(n) = O(n)

• 最差情况：T(n) = O(n2)

• 平均情况：T(n) = O(n2)

五、快速排序

1）算法简介快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。2）算法描述和实现快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；

• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

• //方法一functionquickSort(array,left,right){ if(Object.prototype.toString.call(array).slice(8, -1) === \'Array\' && typeofleft === \'number\' && typeofright === \'number\'){ if(left < right){ varx = array[right],i = left - 1,temp; for(varj = left;j <= right;j++){ if(array[j] <= x){ i++; temp = array[i]; array[i] = array[j]; array[j] = temp; } } quickSort(array,left,i - 1); quickSort(array,i + 1,right); }; }else{ return\'array is not an Array or left or right is not a number!\'; }} varaaa = [3,5,2,9,1];quickSort(aaa,0,aaa.length - 1);console.log(aaa);




• //方法二varquickSort = function(arr){　　if(arr.length <= 1){returnarr;}　　varpivotIndex = Math.floor(arr.length / 2);　　varpivot = arr.splice(pivotIndex,1)[0];　　varleft = [];　　varright = [];　　for(vari = 0;i < arr.length;i++){　　　　if(arr[i] < pivot){　　　　　　left.push(arr[i]);　　　　}else{　　　　　　right.push(arr[i]);　　　　}　　}　　returnquickSort(left).concat([pivot],quickSort(right));};3）算法分析

• 最佳情况：T(n) = O(nlogn)

• 最差情况：T(n) = O(n2)

• 平均情况：T(n) = O(nlogn)

六、堆排序

1）算法简介堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。2）算法描述和实现具体算法描述如下：

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

• /*方法说明：堆排序@param array 待排序数组*/ functionheapSort(array){ if(Object.prototype.toString.call(array).slice(8, -1) === \'Array\'){//建堆 varheapSize = array.length,temp; for(vari = Math.floor(heapSize / 2);i >= 0;i--){ heapify(array,i,heapSize); } //堆排序 for(varj = heapSize - 1;j >= 1;j--){ temp = array[0]; array[0] = array[j]; array[j] = temp; heapify(array,0, --heapSize); } }else{ return\'array is not an Array!\'; }}/*方法说明：维护堆的性质@param arr 数组@param x 数组下标@param len 堆大小*/functionheapify(arr,x,len){ if(Object.prototype.toString.call(arr).slice(8, -1) === \'Array\' && typeofx === \'number\'){ varl = 2 * x,r = 2 * x + 1,largest = x,temp; if(l < len && arr[l] > arr[largest]){ largest = l; } if(r < len && arr[r] > arr[largest]){ largest = r; } if(largest != x){ temp = arr[x]; arr[x] = arr[largest]; arr[largest] = temp; heapify(arr,largest,len); } }else{ return\'arr is not an Array or x is not a number!\'; }




• 3）算法分析

• 最佳情况：T(n) = O(nlogn)

• 最差情况：T(n) = O(nlogn)

• 平均情况：T(n) = O(nlogn)

七、归并排序

1）算法简介归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。2）算法描述和实现具体算法描述如下：

• 把长度为n的输入序列分成两个长度为n/2的子序列；

• 对这两个子序列分别采用归并排序；

• 将两个排序好的子序列合并成一个最终的排序序列。

• functionmergeSort(array,p,r){ if(p < r){ varq = Math.floor((p + r) / 2); mergeSort(array,p,q); mergeSort(array,q + 1,r); merge(array,p,q,r); }}functionmerge(array,p,q,r){ varn1 = q - p + 1,n2 = r - q,left = [],right = [],m = n = 0; for(vari = 0;i < n1;i++){ left[i] = array[p + i]; } for(varj = 0;j < n2;j++){ right[j] = array[q + 1 + j]; } left[n1] = right[n2] = Number.MAX_VALUE; for(vark = p;k <= r;k++){ if(left[m] <= right[n]){ array[k] = left[m]; m++; }else{ array[k] = right[n]; n++; } }}




• 3）算法分析

• 最佳情况：T(n) = O(n)

• 最差情况：T(n) = O(nlogn)

• 平均情况：T(n) = O(nlogn)

八、桶排序

1）算法简介桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。2）算法描述和实现具体算法描述如下：

• 设置一个定量的数组当作空桶；

• 遍历输入数据，并且把数据一个一个放到对应的桶里去；

• 对每个不是空的桶进行排序；

• 从不是空的桶里把排好序的数据拼接起来。

• /*方法说明：桶排序@param array 数组@param num 桶的数量*/functionbucketSort(array,num){ if(array.length <= 1){ returnarray; } varlen = array.length,buckets = [],result = [],min = max = array[0],regex = \'/^[1-9]+[0-9]*$/\',space,n = 0; num = num || ((num > 1 && regex.test(num))?num : 10); for(vari = 1;i < len;i++){ min = min <= array[i]?min : array[i]; max = max >= array[i]?max : array[i]; } space = (max - min + 1) / num; for(varj = 0;j < len;j++){ varindex = Math.floor((array[j] - min) / space); if(buckets[index]){ // 非空桶，插入排序 vark = buckets[index].length - 1; while(k >= 0 && buckets[index][k] > array[j]){ buckets[index][k + 1] = buckets[index][k]; k--; } buckets[index][k + 1] = array[j]; }else{ //空桶，初始化 buckets[index] = []; buckets[index].push(array[j]); } } while(n < num){ result = result.concat(buckets[n]); n++; } returnresult;}




• 3）算法分析桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

九、计数排序

1）算法简介计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。2）算法描述和实现具体算法描述如下：

• 找出待排序的数组中最大和最小的元素；

• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；

• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

• functioncountingSort(array){ varlen = array.length,B = [],C = [],min = max = array[0]; for(vari = 0;i < len;i++){ min = min <= array[i]?min : array[i]; max = max >= array[i]?max : array[i]; C[array[i]] = C[array[i]]?C[array[i]] + 1 : 1; } for(varj = min;j < max;j++){ C[j + 1] = (C[j + 1] || 0) + (C[j] || 0); } for(vark = len - 1;k >=0;k--){ B[C[array[k]] - 1] = array[k]; C[array[k]]--; } returnB;}




• 3）算法分析当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

欢迎在留言区留下你的观点，一起讨论提高。如果今天的文章让你有新的启发，学习能力的提升上有新的认识，欢迎转发分享给更多人。

猜你还想看

阿里、腾讯、百度、华为、京东最新面试题汇集

“12306”的架构到底有多牛逼？看完这篇你就明白了！

Spring Boot & Restful API 构建实战

某小公司RESTful、共用接口、前后端分离、接口约定的实践

关注「程序员小乐」，收看更多精彩内容
嘿，你在看吗？

JavaScript中sort方法有哪些？

在平时的业务开发中，数组(Array)是我们经常用到的数据类型，那么对数组的排序也很常见，除去使用循环遍历数组的方法来排列数据，使用JS数组中原生的方法sort来排列。JavaScript中sort方法有哪些？

1、举例

数组中能够直接用来排序的方法有：reverse()和sort(),由于reverse()方法不够灵活，才有了sort()方法。在默认情况下，sort()方法按升序排列数组。

vararr=[1,3,5,9,4];

console.log(arr.sort());

//输出:[1,3,4,5,9]

这时发现数据按照从小到大排列，没问题；于是再把数组改成：vararr=[101,1,3,5,9,4,11];，再调用sort()方法打印排序结果。

1

2

3

vararr=[101,1,3,5,9,4,11];

console.log(arr.sort());

//输出:[1,101,11,3,4,5,9]

这个时候发现数组101,11都排在3前面，是因为sort()方法会调用数组的toString()转型方法，然后比较得到的字符串，确定如何排序，即使数组中的每一项都是数值，sort()方法比较的也是字符串。

那么字符串又是怎么排序的呢，是根据字符串的unicode编码从小到大排序的。下面我们尝试打印出数组每一项的unicode编码看一下。

//转码方法

functiongetUnicode(charCode){

returncharCode.charCodeAt(0).toString(16);

}

//打印转码

arr.forEach((n)=>{

console.log(getUnicode(String(n)))

});

//输出:31313133343539

惊奇地发现，1,101,11的字符串unicode编码都是31

2、传入比较函数以指定顺序

以上发现sort()方法不是按照我们想要的顺序排序的，那么，怎么解决呢，sort()方法可以接收一个比较函数作为参数，以便指定哪个值位于哪个值前面。

比较函数(compare)接收两个参数，如果第一个参数位于第二个之前则返回一个负数，如果两个参数相等则返回0，如果第一个参数位于第二个之后则返回一个整数。

functioncompare(value1,value2){

if(value1<value2){

return-1;

}elseif(value1>value2){

return1;

}else{

return0;

}

}

我们把比较函数传递给sort()方法，在对arr数组进行排列，打印结果如下：

vararr=[101,1,3,5,9,4,11];

console.log(arr.sort(compare));

//输出:[1,3,4,5,9,11,101];

可以发现排序从小到大没有什么问题。

3、对象数组的排序

sort()方法通过传入一个比较函数来排序数字数组，但是在开发中，我们会对一个对象数组的某个属性进行排序，例如id，年龄等等，那么怎么解决呢？

要解决这个问题：我们可以定义一个函数，让它接收一个属性名，然后根据这个属性名来创建一个比较函数并作为返回值返回来（JS中函数可以作为值来使用，不仅可以像传递参数一样把一个函数传递给另一个函数，也可以将一个函数作为另一个函数的结果返回，函数作为JS中的第一等公民不是没有原因的，确实很灵活。），代码如下。

functioncompareFunc(prop){

returnfunction(obj1,obj2){

varvalue1=obj1[prop];

varvalue2=obj2[prop];

if(value1<value2){

return-1;

}elseif(value1>value2){

return1;

}else{

return0;

}

}

}

定义一个数组users，调用sort()方法传入compareFunc(prop)打印输出结果：

varusers=[

{name:\'tom\',age:18},

{name:\'lucy\',age:24},

{name:\'jhon\',age:17},

];

console.log(users.sort(compareFunc(\'age\')));

//输出结果

[{name:\"jhon\",age:17},

{name:\"tom\",age:18},

{name:\"lucy\",age:24}]

在默认情况下，调用sort()方法不传入比较函数时，sort()方法会调用每个对象的toString()方法来确定他们的次序，当我们调用compareFunc(\'age\')方法创建一个比较函数，排序是按照对象的age属性排序的。

4、XML节点的排序

尽管现在很多后台返回数据就是JSON格式的，很轻量又方便解析。但是之前有个项目因为后台返回的都是XML字符串，前端拿到数据后还得进行序列化，有些需要排序，之前的排序都是把XML转换成数组对象进行排序的，这样做没有什么问题，只不过感觉代码写的很冗余麻烦。后来就突发奇想，xml获取得到也是类数组对象，把类数组对象转换成数组不就可以直接排序了么。

//1.模拟后端返回的XML字符串

varstr=`

<root>

<user>

<name>tom</name>

<age>18</age>

</user>

<user>

<name>lucy</name>

<age>24</age>

</user>

<user>

<name>jhon</name>

<age>17</age>

</user>

<root>

`

//2.定义比较函数

functioncompareFunction(prop){

returnfunction(a,b){

varvalue1=a.getElementsByTagName(prop)[0].textContent;

varvalue2=b.getElementsByTagName(prop)[0].textContent;

if(value1<value2){

return-1;

}elseif(value1>value2){

return1;

}else{

return0;

}

}

}

//3.xml字符串转换成xml对象

vardomParser=newDOMParser();

varxmlDoc=domParser.parseFromString(str,\'text/xml\');

varuserElements=xmlDoc.getElementsByTagName(\'user\'));

//4.userElements类数组对象转换成数组再排序

varuserElements=Array.prototype.slice.call(xmlDoc.getElementsByTagName(\'user\'));

var_userElements=userElements.sort(compareFunction(\'age\'));

//5.打印排序后的结果

_userElements.forEach((user)=>{

console.log(user.innerHTML);

});

打印排序后的结果

可以发现，XML节点已经按照age从小到大排序了。

JS数组的sort方法因为有了传入比较函数使得排序灵活了许多，还有根据时间，汉字拼音首字母排序等等，我们只要牢记通过传入比较函数明确比较两个对象属性值，通过比较属性值来决定对象的排序顺序即可。自己也是在工作中遇到问题从而发现解决问题的新思路，以上就简单总结这么多了，如有不足，多多指正。