归并排序

#归并排序

  • 这就像一棵倒立的二叉树
  • 原理就是两两归并，利用递归进行数组切分，再两两归并
  • 归并原理：
  • 1.两块数组(其实就是真数组的对应位置副本)，头指针分别为 i 和 j
  • 2.比较 i 和 j 所指元素大小，将较小元素放入对应真数组位置，i小放真数组中i所指位置，j一样
  • 3.不断循环，直到 i 或 j 一方数组越界
  • 4.再将剩余元素直接插入真数组对应位置
  • 流程：
  • 1.首部low,尾部high,中部middle
  • 2.递归执行左边low到middle,递归执行右边middle+1到high
  • 3.最后归并
  • 4.切记脱离递归条件low>high

    • #归并排序算法实现

    时间复杂度：O(nlog n)

    空间复杂度：O(n)

    //归并排序

    int a[Num];

    void Merge(int arr[], int low, int midle, int high)

    {

    int i=0, j=0, k=0;

    for (k = low; k <= high; k++)

    a[k] = arr[k];

    for (i = low, j = midle + 1, k = i; i <= midle && j <= high; k++)

    {

    if (a[i] <= a[j])

    arr[k] = a[i++];

    else

    arr[k] = a[j++];

    }

    while (i <= midle)

    arr[k++] = a[i++];

    while (j <= high)

    arr[k++] = a[j++];

    }

    void MergeSort(int arr[], int low, int high)

    {

    if (low < high)

    {

    int middle = (low + high) / 2;

    MergeSort(arr, low, middle);

    MergeSort(arr, middle + 1, high);

    Merge(arr, low, middle, high);

    }

    }