归并排序的分析及实现

归并排序的分析及实现

思想：将两个（或以上）的有序表组成新的有序表。

说明：

（1）更实际的意义：可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ，首先做两两归并，得到 én / 2ù 个长度为 2 的子序列 ；再做两两归并，…，如此重复，直到最后得到一个长度为 n 的有序序列。

（2）性能分析。空间性能：辅助空间 O(n)。时间复杂度：O(nlogn)。稳定性：稳定。

（3）虽然归并排序的运行时间是O(nlogn)，但它很难用于主存排序，主要问题在于合并两个排序的表需要线性附加内存，在整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样一些附加的工作，其结果严重放慢了排序的速度。

（4）归并排序与堆排序和快速排序相比，最大的特点是它是一种稳定的排序方法，所使用的比较次数几乎是最优的。

（5）归并排序的一种变形也可非递归实现，但对于内部排序而言，人们还是选择快速排序。

#include <stdio.h>
#include <stdlib.h>

void Merge(int arr[], int tmpArr[], int left, int mid, int right)
{
    if (!arr || !tmpArr)
    {
        printf("Error Appear!\n");
        return;
    }

    int lEnd = mid;                                    //左子数组上界
    int rStart = mid + 1;                            //右子数组下界
    int cPos = left;   
    int arrNum = right - left + 1;

    while (left <= lEnd && rStart <= right)
    {
        if (arr[left] <= arr[rStart])
        {
            tmpArr[cPos++] = arr[left++];
        }
        else
        {
            tmpArr[cPos++] = arr[rStart++];
        }
    }

    while (left <= lEnd)
    {
        tmpArr[cPos++] = arr[left++];
    }
    while (rStart <= right)
    {
        tmpArr[cPos++] = arr[rStart++];
    }

    for (int i = 0; i < arrNum; i++, right--)
    {
        arr[right] = tmpArr[right];
    }
}

void MSort(int arr[], int tmpArr[], int left, int right)
{
    if (!arr || !tmpArr)
    {
        printf("Error Appear!\n");
        return;
    }

    int mid;
    if (left < right)
    {
        mid = (left + right) / 2;
        MSort(arr, tmpArr, left, mid);
        MSort(arr, tmpArr, mid + 1, right);
        Merge(arr, tmpArr, left, mid, right);
    }
}

void MergeSort(int arr[], int len)
{
    int *tmpArr = (int *)malloc(sizeof(int) * len);
    if (tmpArr != NULL)
    {
        MSort(arr, tmpArr, 0, len - 1);
        free(tmpArr);
    }
    else
    {
        printf("Malloc Failed!\n");
        return;
    }
}

int main(void)
{
    int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    MergeSort(arr, 10);

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

本文永久更新链接地址：