归并排序

基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤

void _MergeSort(int* a, int left, int right,int*tmp)
{
    if (left >= right)
        return;
    int mid = left + ((right - left) >>1);
    //进行分治
    _MergeSort(a, left, mid, tmp);
    _MergeSort(a, mid + 1, right, tmp);
    //进行归并
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    //归并的可不一定是0
    int index = left;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            tmp[index++] = a[begin1++];
        }
        else
        {
            tmp[index++] = a[begin2++];
        }
    }
    while (begin1 <= end1)
    {
        tmp[index++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[index++] = a[begin2++];
    }
    //将数据拷贝回原数组
    for (int i = left; i <= right; i++)
    {
        a[i] = tmp[i];
    }

}

void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);
}
void TestMergeSort()
{
    int a[] = { 105,5,8,2,50,7,-1,100,66 };
    int n = sizeof(a) / sizeof(a[0]);
    MergeSort(a,n);
    Print(a, n);
}
int main()
{
    TestMergeSort();
}

归并排序的特性总结：

归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定

非递归实现

void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (NULL == tmp)
    {
        perror("malloc fail");
        exit(-1);
    }
    else
    {
        //每组数组的个数
        int gap = 1;
        while (gap < n)
        {
            for (int i = 0; i < n; i += 2 * gap)
            {
                //[i,i+gap-1]  [i+gap,i+2*gap-1]
                int begin1 = i, end1 = i + gap - 1;
                int begin2 = i + gap, end2 = i + 2 * gap - 1;
                //进行边界修正
                if (begin2 >= n)
                    break;
                if (end2 >= n)
                {
                    end2 = n - 1;
                }

                int index = i;
                while (begin1 <= end1 && begin2 <= end2)
                {
                    if (a[begin1] < a[begin2])
                    {
                        tmp[index++] = a[begin1++];
                    }
                    else
                    {
                        tmp[index++] = a[begin2++];
                    }
                }
                while (begin1 <= end1)
                {
                    tmp[index++] = a[begin1++];
                }
                while (begin2 <= end2)
                {
                    tmp[index++] = a[begin2++];
                }
                //将数据拷贝回原数组
                for (int j = i; j <=end2; j++)
                {
                    a[j] = tmp[j];
                }
            }
            gap *= 2;
        }
    }
    
}
void TestMergeSortNonR()
{
    int a[] = { 105,5,8,2,50,7,-1,100,66 };
    int n = sizeof(a) / sizeof(a[0]);
    MergeSortNonR(a, n);
    Print(a, n);
}
int main()
{
    TestMergeSortNonR();
}