数据结构与算法JavaScript描述 笔记 - 排序

class CArray {
  constructor(count) {
    this.arr = [];
    for (let i = 0; i < count; i++)
      this.arr.push(parseInt(Math.random() * count));
    // console.log("CArray inited", this.arr);
  }

  swap(arr, index1, index2) {
    arr[index1] = arr[index1] ^ arr[index2];
    arr[index2] = arr[index1] ^ arr[index2];
    arr[index1] = arr[index1] ^ arr[index2];
  }

  inset(arr, to, from) {
    arr.splice(to, 0, arr[from]);
    arr.splice(from + 1, 1);
  }

  // ------- 简单排序 --------
  /** 冒泡：两两比较，先比较前2个数，再比较前3个数...从后向前小的向前面调 */
  bubble() {
    const arr = [...this.arr];
    let c = 0;
    for (let outer = 1; outer < arr.length; outer++) {
      for (let inner = outer; inner >= 1; inner--) {
        if (arr[inner - 1] > arr[inner]) this.swap(arr, inner, inner - 1);
        c++;
      }
    }
    console.log("c", c);
    return arr;
  }

  /** 选择排序：挨遍找最小的向前挪（越找越少）*/
  selection() {
    const arr = [...this.arr];
    let c = 0;
    for (let outer = 0; outer < arr.length; outer++) {
      for (let inner = outer + 1; inner < arr.length; inner++) {
        if (arr[outer] > arr[inner]) this.swap(arr, outer, inner);
        c++;
      }
    }
    console.log("c", c);
    return arr;
  }

  /** 插入排序：从第2位开始，依次往前插入到合适的位置（前部分为排序好的）*/
  insertion() {
    const arr = [...this.arr];
    let c = 0;
    for (let outer = 1; outer < arr.length; outer++) {
      for (let inner = 0; inner < outer; inner++) {
        // if (arr[inner] > arr[outer]) this.swap(arr, inner, outer)
        if (arr[inner] > arr[outer]) {
          this.inset(arr, inner, outer);
          c++;
          break;
        }
      }
    }
    console.log("c", c);
    return arr;
  }

  // ------- 高级排序 --------
  /** 希尔排序算法：设置一个间隔，按间隔排序插入排序（i++ => i+间隔）*/
  shell() {
    const gaps = this.getGaps();
    const arr = [...this.arr];
    let c = 0;
    gaps.forEach((gap) => {
      // 插入排序：从第2位开始，依次往前插入到合适的位置（前部分为排序好的）
      for (let outer = gap; outer < arr.length; outer++) {
        for (let inner = 0; inner < outer; inner++) {
          if (arr[inner] > arr[outer]) {
            this.inset(arr, inner, outer);
            c++;
            break;
          }
        }
      }
      // for (var i = gap; i < this.dataStore.length; ++i) {
      //     var temp = this.dataStore[i];
      //     for (
      //         var j = i;
      //         j >= gap && this.dataStore[j - gap] > temp;
      //         j -= gap
      //     ) {
      //         this.dataStore[j] = this.dataStore[j - gap];
      //     }
      //     this.dataStore[j] = temp;
      // }
    });
    console.log("c", c);
    return arr;
  }
  getGaps() {
    // let N = this.arr.length;
    // let h = 1;
    // while (h < N / 3) { h = 3 * h + 1; }
    // return h;
    let N = this.arr.length;
    let h = 1;
    let gaps = [h];
    while (h < N / 3) {
      h = 3 * h + 1;
      gaps.push(h);
    }
    return gaps.reverse();
  }

  /** 归并排序：切割数组到最小（2个元素），再把它们合并(一个向另一个里插入)到一起（递归） */
  mergeSort(arr) {
    arr = arr || [...this.arr];
    const len = arr.length;
    const mid = Math.floor(len / 2);
    if (len > 1) {
      const left = this.mergeSort(arr.slice(0, mid));
      const right = this.mergeSort(arr.slice(mid, len));
      return this.merge(left, right);
    }
    return arr;
  }
  merge(left, right) {
    let indexL = 0;
    right.forEach((itemR) => {
      while (left[indexL] < itemR && indexL < left.length) indexL++;
      left.splice(indexL, 0, itemR);
    });
    return left;
  }

  /** 快速排序：从一个基准点（第一个）小的在左，大的在右，左右分别递归 */
  quickSort(arr, begin, end) {
    arr = arr || [...this.arr];
    if (arr === undefined) {
      arr = [...this.arr];
      begin = 0;
      end = arr.length;
    }

    // 以第一个为基准点排序数组，小的在左，大的在右，返回排序后的基准点位置
    const pivot = this.split(arr, begin, end);
    if (begin !== pivot) this.quickSort(arr, begin, pivot);
    if (end !== pivot) this.quickSort(arr, pivot + 1, end);

    return arr;
  }
  split(arr, begin, end) {
    let pivot = begin;
    for (let index = begin + 1; index < end; index++) {
      if (arr[index] < arr[pivot]) {
        this.inset(arr, pivot, index);
        pivot++;
      }
    }
    return pivot;
  }
}
const arr = new CArray(20);
// console.log('origin---', arr.arr)
// console.log('bubble---', arr.bubble())
// console.log('selection', arr.selection())
// console.log('insertion', arr.insertion())
// console.log('shell----', arr.shell())  // 比上3个慢

// console.time('bubble'); arr.bubble(); console.timeEnd('bubble');
// console.time('selection'); arr.selection(); console.timeEnd('selection');
// console.time('insertion'); arr.insertion(); console.timeEnd('insertion');
// console.time('shell'); arr.shell(); console.timeEnd('shell');

// console.log("mergeSort", arr.mergeSort());
// console.log("quickSort", arr.quickSort());

// console.time('mergeSort'); arr.mergeSort(); console.timeEnd('mergeSort');
// console.time("quickSort"); arr.quickSort(); console.timeEnd("quickSort");
// console.time("ooooooooo"); arr.arr.sort(); console.timeEnd("ooooooooo");