开篇

排序是我们日常开发中非常常用的一种操作。目前最经典的排序算法有十种，分别是：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序。下面我们介绍两种最常用的排序算法：冒泡排序和快速排序。

冒泡排序

冒泡排序实现思想比较简单，但是性能较差，适合作为培训教学使用。主要实现思想是：遍历数据中每一个节点，如果不合符我们预期的顺序则和下一个数据交换位置，依此类推。
Javascript排序 - 图1
实现代码如下：

  1. //交换数组元素
  2. function swap(arr,n,n1) {
  3.     let temp = arr[n];
  4.     arr[n] = arr[n1];
  5.     arr[n1] = temp;
  6. }
  7. //冒泡排序
  8. function bubbleSort(arr) {
  9.         for(let i=arr.length-1;i>=0;i--) {
  10.             for(let j=0;j<i;j++) {
  11.                 if(arr[j]>arr[i]) {
  12.                     swap(arr,j,i)
  13.                 }
  14.             }
  15.         }
  16.         return arr;
  17. }

快速排序

快速排序是已知排序算法中最快的之一，适合数据量较大的时候使用。其主要实现思想是：先取一个基数（一般取数据的中间位置），然后对基数两边的数据分别排序，比基数大的放右边，比基数小的放左边。之后，对左右两边的数据进行以上相同的操作，直到左右两边数据为空。
Javascript排序 - 图2
实现代码如下：

  1. //快速排序
  2. function quickSort(arr) {
  3.     let piovtIndex = Math.floor(arr.length/2);
  4.     if(arr.length<=1) return arr;
  5.     let piovt = arr.splice(piovtIndex,1)[0];
  6.     let _left = []
  7.     let _right = []
  8.     for (var i = 0; i < arr.length; i++) {
  9.         let item = arr[i];
  10.         if(item<piovt) {
  11.             _left.push(item)
  12.         } else {
  13.             _right.push(item)
  14.         }
  15.     }
  16.     return quickSort(_left).concat([piovt],quickSort(_right))
  17. }

总结

Javascript排序 - 图3
不难看出：两种算法相对比之下，快速排序的所用的操作更少。下面我们用一个例子来验证下这个结论：

  1. var _arr = []
  2. for(let i=0;i<100000;i++) {
  3.     _arr.push(Math.ceil(Math.random()*100))
  4. }
  6. // console.log(_arr)
  7. //快速排序
  8. function quickSort(arr) {
  9.     let piovtIndex = Math.floor(arr.length/2);
  10.     if(arr.length<=1) return arr;
  11.     let piovt = arr.splice(piovtIndex,1)[0];
  12.     let _left = []
  13.     let _right = []
  14.     for (var i = 0; i < arr.length; i++) {
  15.         let item = arr[i];
  16.         if(item<piovt) {
  17.             _left.push(item)
  18.         } else {
  19.             _right.push(item)
  20.         }
  21.     }
  22.     return quickSort(_left).concat([piovt],quickSort(_right))
  23. }
  25. //交换数组元素
  26. function swap(arr,n,n1) {
  27.     let temp = arr[n];
  28.     arr[n] = arr[n1];
  29.     arr[n1] = temp;
  30. }
  31. //冒泡排序
  32. function bubbleSort(arr) {
  33.         for(let i=arr.length-1;i>=0;i--) {
  34.             for(let j=0;j<i;j++) {
  35.                 if(arr[j]>arr[i]) {
  36.                     swap(arr,j,i)
  37.                 }
  38.             }
  39.         }
  40.         return arr;
  41. }
  43. //测试
  44. let time1 = Date.now()
  46. var a = bubbleSort(_arr)
  48. // console.log(a)
  49. console.log('冒泡排序用时：',Date.now()-time1);
  52. let time2 = Date.now()
  53. quickSort(_arr)
  54. console.log('快速排序用时：',Date.now()-time2);
  56. // 冒泡排序用时： 5373
  57. // 快速排序用时： 533

在数据量为10w时，结果输出为冒泡排序用时5373ms,快速排序用时533ms，两者性能相差10倍之多！

最后附上我的博客地址,欢迎多多交流！