js实现归并

归并排序实现

归并排序是一种基于分治思想的稳定排序算法，时间复杂度为O(n log n)。以下是JavaScript的实现方式：

递归实现

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

迭代实现

function mergeSort(arr) {
  let step = 1;
  while (step < arr.length) {
    let left = 0;
    while (left + step < arr.length) {
      const right = left + step;
      const end = Math.min(left + 2 * step, arr.length);
      merge(arr, left, right, end);
      left = end;
    }
    step *= 2;
  }
  return arr;
}

function merge(arr, left, right, end) {
  const temp = [];
  let i = left, j = right;

  while (i < right && j < end) {
    temp.push(arr[i] < arr[j] ? arr[i++] : arr[j++]);
  }

  while (i < right) temp.push(arr[i++]);
  while (j < end) temp.push(arr[j++]);

  for (let k = 0; k < temp.length; k++) {
    arr[left + k] = temp[k];
  }
}

使用示例

const array = [5, 3, 8, 4, 2, 7, 1, 10];
console.log(mergeSort(array)); // [1, 2, 3, 4, 5, 7, 8, 10]

性能优化

对于大型数组，可以添加一些优化措施：

• 当子数组长度小于某个阈值时，改用插入排序
• 检查数组是否已经有序，避免不必要的合并操作
• 使用临时数组避免频繁的内存分配

归并排序特别适合处理链表排序和大规模数据的外部排序场景。