前端-二路归并排序

1. 二路归并排序: 分治法思想 (稳定)

   • 思想: 将两个或者两个以上的有序表合并成为一个有序表.
   • 假定待排序表中有n个记录, 将其看成是n个有序的子表, 每个表的长度为1, 然后两两归并, 得到[n/2]个长度为2或者1的有序表, 然后在两两归并...如此重复

2. 时间复杂度: nlog(2n)

const arr_temp = [];

/*
  合并数组low~mid, mid+1~high, 同时对其进行排序后合并
 */
function merge(arr, low, mid, high) {
  // 将arr中的所有元素复制到arr_temp中
  for (var k = low; k <= high; k++) {
    arr_temp[k] = arr[k];
  } // end for
  // i前半部分数组索引  j后半部分数组索引  k最后处理后数据数组索引
  for (var i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
    if (arr_temp[i] <= arr_temp[j]) {
      arr[k] = arr_temp[i++]
    } else {
      arr[k] = arr_temp[j++]
    }
  } // end for

  // 前半部分的长度大于后半部分
  while (i <= mid) {
    arr[k++] = arr_temp[i++];
  }

  // 后半部分的长度大于前半部分
  while (j <= high) {
    arr[k++] = arr_temp[j++];
  }
}

function MergeSort(A, low, high) {
  if (low < high) {
    const mid = parseInt((low + high) / 2);
    MergeSort(A, low, mid);
    MergeSort(A, mid + 1, high);
    merge(A, low, mid, high);
  }
}

const a = [5, 2, 4, 3, 8, 6, 9, 0, 1, 7];
MergeSort(a, 0, a.length - 1)
console.log(a)