2.2.12次线性的额外空间

[consoles]

当N不被M整除的时候可能出现最后剩余的数组没有被正确排序的问题：数组arr = [2, 1, 4, 3, 5, 7, 4, 2, 1, 3, 6, 7, -1, -2],M = 3，则-1和-2没有被正确排序。问题出现在对每一块进行单独排序的时候最后一块漏了，并且归并的时候也漏了最后一块。我的算法：

function selectionSort(arr, l, r) {
  for (let i = l; i <= r; i++) {
    let minIndex = i;
    for (let j = i + 1; j <= r; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
}

function merge(arr, aux, start, mid, end) {
  for (let k = start; k <= end; k++) {
    aux[k - start] = arr[k];
  }
  let i = start, j = mid + 1;
  for (let k = start; k <= end; k++) {
    if (i > mid) {
      arr[k] = aux[j++];
    } else if (j > end) {
      arr[k] = aux[i++];
    } else if (aux[i] < aux[j]) {
      arr[k] = aux[i++];
    } else {
      arr[k] = aux[j++];
    }
  }
}

function sort(arr) {
  const M = 3;
  const N = arr.length;

  const count = parseInt(N / M);

  // 对每一块进行选择排序
  let rightOverBounds = false;
  for (let l = 0; l < N;) {
    let r = l + M - 1;
    if (r >= N) {
      r = N - 1;
      rightOverBounds = true;
    }
    selectionSort(arr, l, r);
    if (rightOverBounds) {
      break;
    }
    l += M;
  }

  const sz = Math.max(count, M);
  const aux = new Array(sz);

  const start = 0;
  for (let i = 0; i < count; i++) {
    const mid = (i + 1) * M - 1;
    let end = mid + M;
    if (end > N - 1) {
      end = N - 1;
    }
    merge(arr, aux, start, mid, end);
  }
}

另外，我正在写一份js版本的：https://github.com/consoles/dsa4js

[ikesnowy]

Fixed