排序算法

从小到大排序

基础排序

/**
 * max排序
 * @param {*} arr 
 * 耗时：760ms
 */
 function maxSort(arr) {
     let result = [...arr];
     for(let i=0,len=result.length; i< len; i++) {
        let minV = Math.min(...result.slice(i))
        let pos = result.indexOf(minV,i)
        result.splice(pos, 1)
        result.unshift(minV)
     }
     return result.reverse()
 }

冒泡排序

冒泡1

/**
  * 置换函数
  * @param {源数组} arr 
  * @param {原数组的A项} indexA 
  * @param {原数组的B项} indexB 
  */
 function swap(arr, indexA, indexB) {
    [arr[indexA], arr[indexB]] = [arr[indexB], arr[indexA]];
 }
/**
 * 原始冒泡排序
 * @param {数组} arr 
 * 耗时：377ms
 */
 function bubbleSort1(arr) {
    for (let i = arr.length - 1; i > 0; i--) {
      for (let j = 0; j < i; j++) {
        if (arr[j] > arr[j + 1]) {
          swap(arr, j, j + 1);
        }
      }
    }
    return arr;
  }

冒泡排序2

/**
 * 利用索引优化后的冒泡排序
 * @param {数组} arr 
 * 耗时：350ms
 */ 
function bubbleSort2(arr) {
    let i = arr.length - 1;
    while (i > 0) {
        let pos = 0;
        for (let j = 0; j < i; j++) {
        if (arr[j] > arr[j + 1]) {
            pos = j;
            swap(arr, j, j + 1);
        }
        }
        i = pos;
    }
    return arr;
}

冒泡排序3

/**
 * 在每趟排序中进行正向和反向两遍冒泡 ,
 * 一次可以得到两个最终值（最大和最小）, 
 * 从而使外排序趟数大概减少了一半
 * @param {*} arr 
 * 耗时：312ms
 */
function bubbleSort3(arr) {
    let start = 0;
    let end = arr.length - 1;
    while (start < end) {
      let endPos = 0;
      let startPos = 0;
      for (let i = start; i < end; i++) {
        if (arr[i] > arr[i + 1]) {
            endPos = i;
            swap(arr, i, i + 1);
        }
      }
      end = endPos;
      for (let i = end; i > start; i--) {
        if (arr[i - 1] > arr[i]) {
          startPos = i;  
          swap(arr, i - 1, i);
        }
      }
      start = startPos;
    }
    return arr;
  }

选择排序

selectSort() {
    for (let i = 0; i < this.list.length - 1; i++) {
      let minIndex = i;
      for (let j = minIndex + 1; j < this.list.length; j++) {
        if (this.list[minIndex] > this.list[j]) {
          // 将后边小的移动到前部
          minIndex = j;
        }
      }
      this.swap(minIndex, i);
    }
    return this.list;
  }

二分搜索+插入排序

插入排序1

  insertionSort() {
    for (let i = 1; i < this.list.length; i++) {
      let temp = this.list[i];
      // 定义frontMove变量，不断的寻找要插入temp的位置。
      // 如果出现this.list[frontMove-1]不大于temp，则终止while循环，将temp放入次位置
      let frontMove = i;
      // this.list[frontMove-1]>temp已经排好序的部分，大于要插入的temp，则继续往前查找。
      while (this.list[frontMove - 1] > temp && frontMove > 0) {
        // 此时temp比已排好元素小，把已排好的元素向后移动一位，将frontMove-1的值赋值给frontMove
        this.list[frontMove] = this.list[frontMove - 1];
        frontMove--;
      }
      // 前面排好序号的元素，找到了不大于temp的位置，此时将temp放入该位置
      this.list[frontMove] = temp;
    }
    return this.list;
  }

/**
   * 改造二分查找,查找小于value且离value最近的值的索引
   * @param {*} arr 
   * @param {*} maxIndex 
   * @param {*} value 
   */
  function binarySearch1(arr, maxIndex, value) {
    let min = 0;
    let max = maxIndex;
    while (min <= max) {
      const m = Math.floor((min + max) / 2);
      if (arr[m] <= value) {
        min = m + 1;
      } else {
        max = m - 1;
      }
    }
    return min;
  }
/**
 * 使用二分法来优化插入排序
 * @param {*} arr 
 * 耗时：86ms
 */
function insertionSort1(arr) {
    for (let i = 1, len = arr.length; i < len; i++) {
        const temp = arr[i];
        const insertIndex = binarySearch1(arr, i - 1, arr[i]);
        for (let preIndex = i - 1; preIndex >= insertIndex; preIndex--) {
        arr[preIndex + 1] = arr[preIndex];
        }
        arr[insertIndex] = temp;
    }
    return arr;
}

希尔排序

/**
 * 希尔排序
 * 核心：通过动态定义的 gap 来排序，先排序距离较远的元素，再逐渐递进
 * @param {*} arr
 * 耗时：15ms
 */
function shellSort(arr) {
  const len = arr.length;
  let gap = Math.floor(len / 2);
  while (gap > 0) {
    // gap距离
    for (let i = gap; i < len; i++) {
      const temp = arr[i];
      let preIndex = i - gap;
      while (arr[preIndex] > temp) {
        arr[preIndex + gap] = arr[preIndex];
        preIndex -= gap;
      }
      arr[preIndex + gap] = temp;
    }
    gap = Math.floor(gap / 2);
  }
  return arr;
}
console.log("shellSort", shellSort(testArr))

快速排序

const quickFn = (arr) => {
  // 快速排序使用了递归，首先需要定义递归的终止条件
  if (arr.length < 2) return arr;
  // 获取数组中间位置的值，作为标志位
  let pivotIndex = Math.floor(arr.length / 2);
  let pivot = arr.splice(pivotIndex, 1)[0];
  // 定义left【加入比标志位小的】数组，right【比标志位大的】数组
  let left = [],right = [];
  for (let i = 0; i < arr.length; i++) {
    // 小的放入left数组
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      // 大的放入right数组
      right.push(arr[i]);
    }
  }
  // 递归调用left和right数组，并且拼接上标志位元素pivot。
  return quickFn(left).concat([pivot], quickFn(right));
};

归并排序

/**
 * 归并排序
 * @param {*} arr 
 * 耗时 30ms
 */
function concatSort(arr) {
  const len = arr.length;
  if (len < 2) { return arr; }
  const mid = Math.floor(len / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  return concat(concatSort(left), concatSort(right));
}
function concat(left, right) {
  const result = [];
  while (left.length > 0 && right.length > 0) {
    // 一直对比left和right数组的第一个元素，如果left的小。则添加left到result
    result.push(left[0] <= right[0] ? left.shift() : right.shift());
  }
  return result.concat(left, right);
}
console.log('concatSort', concatSort(testArr));