详解JavaScript如何实现四种常用排序

function insertSort(array) {
//第一个默认已经排好
      for (let i = 1; i < array.length; i  ) {
        let target = i;
        for (let j = i - 1; j >= 0; j--) {
          if (array[target] < array[j]) {
            [array[target], array[j]] = [array[j], array[target]]
            target = j;
          } else {
            break;
          }
        }
      }
      return array;
    }

    function bubbleSort(array) {
        //第一个循环是所需次数
      for (let j = 0; j < array.length; j  ) {
        let complete = true;
        for (let i = array.length-1; i>j; i--) {
          // 比较相邻数
          if (array[i] < array[i -1]) {
            [array[i], array[i - 1]] = [array[i - 1], array[i]];
            complete = false;
          }
        }
        // 没有冒泡结束循环
        if (complete) {
          break;
        }
      }
      return array;
    }

//JS自带的sort()就是快排
function quickSort(array, start, end) {
      if (end - start < 1) {
        return;
      }
      const target = array[start];
      let l = start;
      let r = end;
      while (l < r) {
        while (l < r && array[r] >= target) {
          r--;
        }
        array[l] = array[r];
        while (l < r && array[l] < target) {
          l  ;
        }
        array[r] = array[l];
      }
      array[l] = target;
      quickSort(array, start, l - 1);
      quickSort(array, l   1, end);
      return array;
    }

 function selectionSort(array) {
      for (let i = 0; i < array.length - 1; i  ) {
        let minIndex = i;
        for (let j = i   1; j < array.length; j  ) {
          if (array[j] < array[minIndex]) {
            minIndex = j;
          }
        }
        [array[minIndex], array[i]] = [array[i], array[minIndex]];
      }
    }

 function heapSort(array) {
      creatHeap(array);
      console.log(array);
      // 交换第一个和最后一个元素，然后重新调整大顶堆
      for (let i = array.length - 1; i > 0; i--) {
        [array[i], array[0]] = [array[0], array[i]];
        adjust(array, 0, i);
      }
      return array;
    }
    // 构建大顶堆，从第一个非叶子节点开始，进行下沉操作
    function creatHeap(array) {
      const len = array.length;
      const start = parseInt(len / 2) - 1;
      for (let i = start; i >= 0; i--) {
        adjust(array, i, len);
      }
    }
    // 将第target个元素进行下沉，孩子节点有比他大的就下沉
    function adjust(array, target, len) {
      for (let i = 2 * target   1; i < len; i = 2 * i   1) {
        // 找到孩子节点中最大的
        if (i   1 < len && array[i   1] > array[i]) {
          i = i   1;
        }
        // 下沉
        if (array[i] > array[target]) {
          [array[i], array[target]] = [array[target], array[i]]
          target = i;
        } else {
          break;
        }
      }
    }

function mergeSort(array) {
      if (array.length < 2) {
        return array;
      }
      const mid = Math.floor(array.length / 2);
      const front = array.slice(0, mid);
      const end = array.slice(mid);
      return merge(mergeSort(front), mergeSort(end));
    }
 
    function merge(front, end) {
      const temp = [];
      while (front.length && end.length) {
        if (front[0] < end[0]) {
          temp.push(front.shift());
        } else {
          temp.push(end.shift());
        }
      }
      while (front.length) {
        temp.push(front.shift());
      }
      while (end.length) {
        temp.push(end.shift());
      }
      return temp;
    }

function merge(left, right){
    let leftLen = left.length, rightLen = right.length;
    let i = 0, j = 0;
    let temp = new Array(leftLen   rightLen);
    for(let cur = 0; cur < leftLen   rightLen; cur  ){
        // 检查i, j有没有超界
        if(i >= leftLen) temp[cur]= right[j  ];
        else if(j >= rightLen) temp[cur] = left[i  ];
        else if(left[i] <= right[j]){
            temp[cur] = left[i  ];
        }else{
            temp[cur] = right[j  ];
        }
    }
    return temp;
}