JavaScript算法-归并排序

归并排序 - 图1

  • 归并排序
  • 归并排序是建立在归并操作上的一种有效的排序算法。该算法是分治法的一个非常典型的应用。归并排是一种稳定的排序方法。将已有序列的子序列合并
  • .把长度为n的输入序列分成两个长度为n/2的子序列；
  • .对这两个子序列分别采用归并排序；
  • .将两个排序好的子序列合并成一个最终的排序序列。
  1. function mergeSort(arr) {  //采用自上而下的递归方法
  2.     var len = arr.length;
  3.     if(len <2) {
  4.         return arr;
  5.     }
  6.     var middle = Math.floor(len / 2),
  7.         left = arr.slice(0, middle),
  8.         right = arr.slice(middle);
  9.     return merge(mergeSort(left), mergeSort(right));
  10. }
  12. function merge(left, right){
  13.     var result = [];
  14.     console.time('归并排序耗时');
  15.     while (left.length && right.length) {
  16.         if (left[0] <= right[0]) {
  17.             result.push(left.shift());
  18.         } else {
  19.             result.push(right.shift());
  20.         }
  21.     }
  23.     while (left.length)
  24.         result.push(left.shift());
  26.     while (right.length)
  27.         result.push(right.shift());
  28.     console.timeEnd('归并排序耗时');
  29.     return result;
  30. }
  31. var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
  32. console.log(mergeSort(arr));
  33. // 归并排序耗时: 0.009033203125ms
  34. // 归并排序耗时: 0.0048828125ms
  35. // 归并排序耗时: 0.004150390625ms
  36. // 归并排序耗时: 0.002197265625ms
  37. // 归并排序耗时: 0.0048828125ms
  38. // 归并排序耗时: 0.0029296875ms
  39. // 归并排序耗时: 0.0009765625ms
  40. // 归并排序耗时: 0.000732421875ms
  41. // 归并排序耗时: 0.003173828125ms
  42. // 归并排序耗时: 0.003173828125ms
  43. // 归并排序耗时: 0.001220703125ms
  44. // 归并排序耗时: 0.002197265625ms
  45. // 归并排序耗时: 0.0029296875ms
  46. // 归并排序耗时: 0.002685546875ms
  47. //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]