本页目录

希尔排序

基本思想：定义缩小增量序列 k=len>>=1，从 k 开始对当前增量间距的元素进行插入排序，直到增量为 1。

算法过程描述：

定义缩小增量序列k=len>>=1；
按增量序列个数k，对序列进行k趟排序；
每趟排序，根据对应的增量k，将待排序列分割成若干长度为~~(len/k)的子序列；
分别对各子表进行直接插入排序；
仅当k===1时，对其直接插入排序，此时完成排序。

移位法

JavaScript

const shellSort = A => {
  const len = A.length

  // 定义增量序列 k=len>>=1
  for (let k = len >> 1; k > 0; k >>= 1) {
    // 从 k 开始直接插入排序
    for (let i = k; i < len; i++) {
      let [kIdx, cur] = [i - k, A[i]]
      while (kIdx >= 0 && A[kIdx] > A[i]) {
        A[kIdx + k] = A[kIdx]
        kIdx -= k
      }
      A[kIdx + k] = cur // 该位置后插入
    }
  }
}

交换法

JavaScript

const shellSort = A => {
  const len = A.length

  // 定义增量序列 k=len>>=1
  for (let k = len >> 1; k > 0; k >>= 1) {
    // 从 k 开始直接插入排序
    for (let i = k; i < len; i++) {
      let kIdx = i - k
      while (kIdx >= 0 && A[kIdx] > A[i]) {
        [A[kIdx], A[i]] = [A[i], A[kIdx]]
        kIdx -= k
      }
    }
  }
}