归并排序递归和非递归实现

分析

例子：{3,1,5,4}，升序排列

{3}{1}{5}{4}为有序序列，因为序列中只有一个元素；

序列长度为1：{3}和{1}这两个有序序列合并成一个有序序列{1,3}，同理{4,5}

序列长度为1*2：{1,3}和{4,5}这两个有序序列合并，{1,3,4,5}

序列长度为1*2*2：{1,3,4,5}

上面例子，能得出我们要解决两个有序序列合并，并处理有序序列长度从1到1*2*2。

两个有序序列的合并

算法分析

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

代码实现

//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergeArray(int a[], int first, int mid, int last, int temp[]) {
    int i = first, j = mid + 1;
    int m = mid, n = last;
    int k = 0;

    while (i <= m && j <= n) {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= m)
        temp[k++] = a[i++];

    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}

非递归

算法思路

①把 n 个记录看成 n 个长度为1的有序子表；

②进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表；

③重复第②步直到所有记录归并成一个长度为 n 的有序表为止。

算法实现

首先让子表表长 L=1 进行处理；

不断地使 L=2*L ，进行子表处理，直到 L>=n 为止

void mergeSort(int a[], int first, int last, int temp[]) {
    int step = 1, low, mid, high;
    while (step <= last - first) {
        for (int i = first; i <= last; i += 2 * step) {
            low = i;
            if (i + step - 1 > last)
                mid = last;
            else
                mid = i + step - 1;
            if (i + 2 * step - 1 > last)
                high = last;
            else
                high = i + 2 * step - 1;
            mergeArray(a, low, mid, high, temp);
        }
        step *= 2;//范围扩大一倍
    }
}

递归实现

算法思路

解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组 A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将 A，B 组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

代码实现

void mergesort(int a[], int first, int last, int temp[])
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        mergesort(a, first, mid, temp);    //左边有序
        mergesort(a, mid + 1, last, temp); //右边有序
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并
    }
}