归并排序 算法

算法

1. 适用范围:

优点:

1. 第一梯队的速度和稳定性
2. 稳定排序

1.1. 缺点:

1. 需要一个相同规模的额外数组
2. 空间复杂度高

实现方式

自底向上

2. 梗概:

1. 把原数组分成每组一个的多个组, 这时组内已经有序
2. 把有序的每两组归并为一组, 同时保持有序
3. 一直持续上一步, 直到整个组包含原数组

3. 在c语言中的实现

梗概:

1. 需要一个临时工作数组, 用来保存当前迭代已排序完成的记录
2. 两组两组的合并
   1. low到mid指向待合并组1
   2. mid到high指向待合并组2 代码:

int min(int x, int y) { return x < y ? x : y; }
void merge_sort(RecordType Records[], int len) {
    RecordType* a = Records; // 指向当前步骤需要排序的数组
    /*指向当前步骤排序好的数组,作为下一次的排序材料*/
    RecordType* b = (RecordType*)calloc(len, sizeof(RecordType));
    int seg, start;
    /*按数量分组,一组seg个,初始每组一个,天生组内有序*/
    for (seg = 1; seg < len; seg += seg) {
        /*依次归并两组*/
        for (start = 0; start < len; start += seg * 2) {
            /*最后两组可能并不能达到要求数量,凑合即可*/
            int low = start, mid = min(start + seg, len),
                high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            /*归并已经组内有序的两组*/
            while (start1 < end1 && start2 < end2)
                b[k++] =
                    a[start1].key < a[start2].key ? a[start1++] : a[start2++];
            /*其中一组为空,另一组直接放进有序数组b即可*/
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        /*交换a和b指向的数组,为下次做准备*/
        RecordType* temp = a;
        a = b;
        b = temp;
    }
    /*此时a必定指向排序好的数组,但a不一定指向传入的数组地址*/
    if (b == Records) { // b指向传入数组的地址
        int i;
        /*把排序好的数组搬到传入的数组中*/
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a; // 此时a指向的数组才是函数内分配出来的
    }
    free(b);
}

自顶向下

在JS中的实现

代码:

function merge(left, right) {
  let result = [];
  let i = 0;
  let 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) {
 
  if (arr.length <= 1) {
    return arr;
  }
 
  const middle = Math.floor(arr.length / 2);
 
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);
 
  return merge(mergeSort(left),mergeSort(right));
}