/*
希尔排序的性能与所选的间隔序列（shell序列）有关。以下是几种常见的希尔排序序列：
Hibbard 序列:
H(k) = 2^k - 1
如：1, 3, 7, 15, 31, ...

Sedgewick 序列:
H(k) = 9 * 4^k - 9 * 2^k + 1 或 4^k - 3 * 2^k + 1
如：1, 5, 19, 41, 109, ...

Knuth 序列:
H(k) = 3^k + 1
如：1, 4, 13, 40, 121, ...

这些序列在实际应用中可能产生不同的性能效果，最佳序列可能取决于特定问题或数据集的性质。

*/

/**
 *
 * @param {number[]} arr
 */
export function shellSort(arr) {
  const n = arr.length;
  // 创建希尔序列,以克努特序列为例
  let gap = 1;
  while (gap < n / 3) {
    gap = gap * 3 + 1;
  }

  while (gap >= 1) {
    // 正常插入排序
    for (let i = 0; i < gap; i++) {
      for (let j = i + gap; j < n; j += gap) {
        const temp = arr[j];
        while (j > 0 && arr[j - gap] > temp) {
          arr[j] = arr[j - gap];
          j -= gap;
        }
        arr[j] = temp;
      }
    }
    // 正常插入排序

    gap = Math.floor(gap / 3);
  }
}

/**
 * @description 使用希尔序列排序
 * @param {number[]} arr
 */
export function shellSort2(arr) {
  const n = arr.length;
  let gap = Math.floor(n / 2);
  while (gap > 0) {
    for (let i = 0; i < gap; i++) {
      for (let j = i + gap; j < n; j += gap) {
        const temp = arr[j];
        while (j > 0 && arr[j - gap] > temp) { // 插入过程s
          arr[j] = arr[j - gap];
          j -= gap;
        }
        arr[j] = temp;
      }
    }
    gap = Math.floor(gap / 2);
  }
}

/**
 * 优化版本
 * @param {number[]} arr
 */
export function shellSort3(arr) {
  const n = arr.length;
  let gap = Math.floor(n / 2);
  while (gap > 0) { // 使用不同的gap对子数组排序
    for (let i = gap; i < n; i++) {
      // 插入过程
      const temp = arr[i];
      let j = i;
      while (j > 0 && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
    gap = Math.floor(gap / 2);
  }
}