master

分支 (1)

管理

管理

master

base_knowledge
/
归并排序.html

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>归并排序</title>
</head>
<body>

</body>
</html>

<script>
  // let arr = [3, 1, 5, 4, 2, 6]
  // function mergeSort(arr) { //采用自上而下的递归方法
  //   var len = arr.length;
  //   if(len < 2) {
  //     return arr;
  //   }
  //   var middle = Math.floor(len / 2),
  //       left = arr.slice(0, middle),
  //       right = arr.slice(middle);
  //   return merge(mergeSort(left), mergeSort(right));
  // }
  //
  //
  // function merge(left, right){
  //   var result = [];
  //   // console.time('归并排序耗时');
  //   while (left.length && right.length) {
  //     console.log('left[0]:', left[0])
  //     console.log('right[0]:', right[0])
  //     if (left[0] <= right[0]) {
  //       result.push(left.shift());
  //     } else {
  //       result.push(right.shift());
  //     }
  //   }
  //
  //   while (left.length){
  //     result.push(left.shift());
  //   }
  //   while (right.length){
  //     result.push(right.shift());
  //   }
  //   // console.timeEnd('归并排序耗时');
  //   return result;
  // }
  // console.log('mergeSort:', mergeSort(arr))


  function quick_sort(arr, start, end) {
    if (start >= end) {
      return
    }
    let mid = arr[start]
    let low = start
    let high = end
    while (low < high) {
      while (low < high && arr[high] >= mid) {
        high--
      }
      arr[low] = arr[high]
      while (low < high && arr[low] < mid) {
        low++
      }
      arr[high] = arr[low]
    }
    arr[low] = mid
    quick_sort(arr, start, low - 1)
    quick_sort(arr, low + 1, end)
  }

  let arr1 = [7, 4, 3, 67, 34, 1, 8]
  quick_sort(arr, 0, arr1.length - 1) // [ 1, 3, 4, 7, 8, 34, 67 ]

  // 分析： 第一次外层while循环跳出，将数组分成左边两部分，中间为7， 左边都比7小，右边都比7大，之后将左边数组传入递归，当左边全部排好后，才会将右边数组传入进行递归，循环结束后，如果我们以7为根节点，可以转化一个典型的二叉树，而我们上面的操作像不像深度优先遍历的递归算法。
</script>