//插入排序
function insertSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    //在前面已经排序好的位置里找到当前元素应该插入的位置
    for (let j = 0; j < i; j++) {
      if (arr[i] <= arr[j]) {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}
//希尔排序
function shellSort(array) {
  if (array.length <= 1) return array; // 如果数组长度为1，直接返回
  var gap = Math.floor(array.length / 2);
  while (gap > 0) {
    for (var i = gap; i < array.length; i++) {
      var j = i;
      var temp = array[j];
      while (j > 0 && array[j - gap] > temp) {
        // 若array[j - gap]>temp(即array[j]) 则互换位置
        array[j] = array[j - gap]; // 这里可看成是将 j-gap 后移一个 gap 位 //TODO 插入排序这里是后移一位
        array[j - gap] = temp; // 由于不像插入排序那样需要比较很多个元素，而是两个数的比较，此处将大得值往前移一个 gap 位即可
        j -= gap; // 跳出循环的条件
      }
    }
    gap = Math.floor(gap / 2); // 减小增量
  }
  return array;
}

//选择排序
function chooseSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    //在剩下的位置找最小的然后替换到当前位置
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[i]) {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}
//冒泡排序
function bubbleSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    //从0开始对比相邻位置的大小，大的冒泡上去
    for (let j = 0; j < arr.length - i; j++) {
      if (arr[j + 1] < arr[j]) {
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}
//归并排序
function mergeSort(arr, start, end) {
  if (start < end) {
    let mid = ((start + end) / 2) >> 0;
    //分治左右处理
    arr = mergeSort(arr, start, mid);
    arr = mergeSort(arr, mid + 1, end);
    //这里对一边的数组进行操作，经过上面的操作，这里的数组两边都是有序的
    let left = start,
      right = mid + 1,
      tempArr = [];
    //数组两边进行归并
    while (left <= mid && right <= end) {
      if (arr[left] < arr[right]) {
        tempArr.push(arr[left++]);
      } else {
        tempArr.push(arr[right++]);
      }
    }
    //哪边多出来了就拿出来合并
    left > mid
      ? tempArr.push(...arr.slice(right, end + 1))
      : tempArr.push(...arr.slice(left, mid + 1));
    //把排好序的替换掉之前的
    arr.splice(start, end - start + 1, ...tempArr);
  }
  return arr;
}
//快速排序
function quickSort(arr, start, end) {
  if (start < end) {
    let left = start,
      right = end;
    let temp = arr[left];
    //左右分别找，大的放左边，小的放右边
    while (left < right) {
      while (arr[right] >= temp && left < right) {
        right--;
      }
      arr[left] = arr[right];
      while (arr[left] <= temp && left < right) {
        left++;
      }
      arr[right] = arr[left];
    }
    arr[left] = temp;
    //分治，左右的递归继续操作
    arr = quickSort(arr, start, left - 1);
    arr = quickSort(arr, left + 1, end);
  }
  return arr;
}