本文收集了几种常用排序方式的JS代码实现与性能比较，包括：冒泡排序，选择排序，插入排序，归并排序和快速排序，我们从实现方式最简单的冒泡排序入手 一、冒泡排序 原理：依次比较两个相邻的项，如果前者大于后
本文收集了几种常用排序方式的JS代码实现与性能比较，包括：冒泡排序，选择排序，插入排序，归并排序和快速排序，我们从实现方式最简单的冒泡排序入手
一、冒泡排序
原理：依次比较两个相邻的项，如果前者大于后者，则交换两者位置，就如同气泡往上冒一样。
代码实现：
Array.prototype.bubbleSort = function(){ var length = this.length; for(var i=0;i<length;i++){ for(var j=0;j<length-1-i;j++){ this[j]>this[j+1] && swap(this,j,j+1) //swap方法交换两个元素 } }}注意，内层循环的次数需要减掉外层已循环过的次数，因为外层循环每走一遍就有一个元素被排好序，无需再进行排序。
这种排序方式的时间复杂度为O(n^2)，(时间复杂度的计算方法参见http://baike.baidu.com/link?url=DnQgmILQ4dt2kCRwafBtNJHo21upzQVZAX2Y6TyJLoh2rxy_YQtxfhjwhmHmneETaSlw9KuKCjzSJqwGtzL4CUSm4aC3mYTfDlsjfZWCRFiQ8TiPnKHvn3mZ6-YpTkAYX1MEn5BRoFmjOHFRjzNCSK)
，我们可以在http://math.hws.edu/eck/js/sorting/xSortLab.html中模拟这个过程，结果如下：
执行10个长度为10000的乱序数组的排序，总耗时为28.7秒
二、选择排序
原理：从数组中找到最小值，与数组首位交换位置(即放在第一位)，接着再寻找第二小的值，放在第二位，以此类推
代码实现：
Array.prototype.selectSort = function(){ var length = this.length, minIndex; for(var i =0;i<length-1;i++){ minIndex = i; for(var j=i;j<length;j++){ if(this[minIndex]>this[j])minIndex = j; } i !== minIndex) && swap(this,i,minIndex); //swap方法交换两个元素 }}这种排序方式的时间复杂度为O(n^2)，模拟排序结果如下：
执行10个长度为10000的乱序数组的排序，总耗时为17.7秒
三、插入排序
插入排序分为直接插入排序，二分插入排序和希尔排序，这里介绍的是直接插入排序
原理：将数列的第一个元素视为有序数列，后面都视为无序数列：
{{a1}，{a2，a3，a4，…，an}}
然后将无序数列中的元素插入到有序数列的对应位置，插入前通过比大小的方式找到其在有序数列中的对应位置。
Array.prototype.insertSort = function(){ var length = this.length, j, temp; for(var i=1;i<length;i++){ j = 1; temp = array[i]; //temp为待排序项 while(j>0 && array[j-1] > temp){ array[j] = array[j-1]; j--; } //若temp项之前存在比temp大的项，则把这个项移到当前位置上， //直到找不到比temp更大的项时， array[j] = temp //执行插入操作 }}这种排序方式的时间复杂度为O(n^2)，模拟排序结果如下：
执行10个长度为10000的乱序数组的排序，总耗时为8秒
四、归并排序
从这里开始才是真正能投入实际使用的排序方法，包括最后的快速排序，浏览器一般使用这两种方法之一作为sort函数的实现(但是V8对较短的数组使用插入排序方法)
原理：归并排序采用分治--递归的思想，先对一个数组进行不断的对半拆解，直至子项个数为1。如图：
(原图:http://www.108js.com/article/article5/img/1.png)
之后执行合并，从最下层开始，依次比较左边的项是否比右边的小，是的话移除左数组的第一位并放进新数组中，否则移除右数组的第一位并放进新数组中，这样就可以重新合并出一个排完序的大数组。
代码实现：
function merge(left, right) { var result = []; while(left.length > 0 && right.length > 0) { if(left[0] < right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } } // 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 console.log(result) return result.concat(left).concat(right); } function mergeSort(array) { if(array.length == 1) return array; // 对半划分 var mid = Math.floor(array.length / 2); var left = array.slice(0, mid); var right = array.slice(mid); // 递归合并 return merge(mergeSort(left), mergeSort(right)); }这种排序方式的时间复杂度为O(n*log n)，模拟排序结果如下：
能发现归并排序对大数组的排序效率已经有了质的提升
五、快速排序
原理：首先选取一个基准项(pivot),我们一般选取中间项作为pivot；接着所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。然后对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止
代码实现：
var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = []; for (var i = 0; i < arr.length; i++){ if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat([pivot], quickSort(right));};这里参考了阮一峰老师的文章，详情可移步
http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html
这种排序方式的时间复杂度为O(n*log n)，模拟排序结果如下：
与归并排序很接近，对于快速排序与归并排序的性能比较，可参考以下文章：
http://stackoverflow.com/questions/680541/quick-sort-vs-merge-sort
