Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

2.2.12次线性的额外空间 #532

Closed
consoles opened this issue May 8, 2019 · 1 comment
Closed

2.2.12次线性的额外空间 #532

consoles opened this issue May 8, 2019 · 1 comment
Assignees
Milestone

Comments

@consoles
Copy link

@consoles consoles commented May 8, 2019

当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 ikesnowy self-assigned this May 16, 2019
@ikesnowy ikesnowy added this to the 2.2 milestone May 16, 2019
ikesnowy added a commit that referenced this issue May 16, 2019
@ikesnowy ikesnowy added FIXED and removed IN PROGRESS labels May 16, 2019
@ikesnowy

This comment has been minimized.

Copy link
Owner

@ikesnowy ikesnowy commented May 16, 2019

Fixed

@ikesnowy ikesnowy closed this May 16, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants
You can’t perform that action at this time.