陈恒承

插入排序

算法思想:假设第一个元素排好序，然后往后遍历元素，当前元素与已经排好的序中的元素比较。
如果不符合，就交换位置。

function insertSort(nums) {
  // 假定第一个已经排好序

  for (let i = 1; i < nums.length; i++) {
    let position = i;
    // 寻找插入点
    while (position !== 0 && nums[i] < nums[position - 1]) {
      position--;
    }
    // 移动元素
    if (position !== i) {
      const e = nums[i];
      let k = i;
      while (k > position) {
        nums[k] = nums[k - 1];
        k--;
      }
      nums[position] = e;
    }
  }
  console.log("排序好的", nums);
}

insertSort([1, 4, 3, 1, 12, 3]);
insertSort([1, 2, 3, 4, 5, 5]);
insertSort([5, 4, 3, 2, 1, 1]);
insertSort([8, 5, 7]);

合并搜索和交换的实现

从第一个代码实现来看，先查找插入位置，最后，插入，这个有点啰嗦了。我们可以换一种更好的方式。
在比较的同时，交换元素。这样就避免了不必要的重复。

function insertSort(nums) {
  // 假定第一个已经排好序
  for (let i = 1; i < nums.length; i++) {
    let p = i;
    // 比较交换元素
    while (p !== 0 && nums[p] < nums[p - 1]) {
      //  交换逻辑，跟往后挪位又不同，且看第三次改写代码
      const temp = nums[p];
      nums[p] = nums[p - 1];
      nums[p - 1] = temp;

      p--;
    }
  }
  console.log("排序好的哦", nums);
}

insertSort([1, 4, 3, 1, 12, 3]);
insertSort([1, 2, 3, 4, 5, 5]);
insertSort([5, 4, 3, 2, 1, 1]);
insertSort([8, 5, 7]);

正统的实现???

unction insertSort(nums) {
  // 假定第一个已经排好序
  for (let i = 1; i < nums.length; i++) {
    let p = i;
    const e = nums[p];
    while (p !== 0 && e < nums[p - 1]) {
      // 找的时候，直接往后退位
      nums[p] = nums[p - 1];
      p--;
    }
    // 插入元素
    nums[p] = e;
  }
  console.log("排序好!", nums);
}

insertSort([1, 4, 3, 1, 12, 3]);
insertSort([1, 2, 3, 4, 5, 5]);
insertSort([5, 4, 3, 2, 1, 1]);
insertSort([8, 5, 7]);

折半插入排序

其实可以发现，我们可以采用二分法查找插入的位置，减少查询次数。

希尔排序

插入排序的升级版，主要是尽量使 集合 有序

• 明确增量是什么
• 每一趟排序，都采用插入排序

function shellSort(nums) {
  let len = nums.length;
  let gNum = Math.floor(len / 2);

  while (gNum >= 1) {
    // 分组，
    for (let i = gNum; i < len; i++) {
      for (let j = i; j >= gNum && nums[j] < nums[j - gNum]; j = j - gNum) {
        const temp = nums[j - gNum];
        nums[j - gNum] = nums[j];
        nums[j] = temp;
      }
    }

    console.log("增量:" + gum + "排序-" + nums);

    gNum = Math.floor(gNum / 2);
  }

  return nums;
}

console.log(shellSort([10, 9, 8, 7, 6]));
/*
   第一趟:6,7,8,9,10
*/