归并排序（递归和非递归法）

╰半橙微兮° 2022-08-01 12:28 209阅读 0赞

本文主要参考两篇博文：  
递归法归并排序函数代码来自：  
[http://blog.csdn.net/morewindows/article/details/6678165/][http_blog.csdn.net_morewindows_article_details_6678165]  
非递归法归并排序函数代码来自：  
[http://www.cnblogs.com/xing901022/p/3671771.html][http_www.cnblogs.com_xing901022_p_3671771.html]

以下是我根据两篇博文，写的一点学习笔记。

**归并排序原理：**  
含有 n 个元素的数列，可以将其分解成 n 个子序列，每个子序列含有一个元素，因此每一个子序列皆为有序数列，两两合并，可以合并成 n/2 个有序数列，依次类推，最终合并成一个完整的有序数列。  
**因此，归并排序可以分为两个部分：递归分解部分，以及，合并有序数列部分**

**算法的时间复杂度：O(N\*logN)**

在了解归并排序之前，需要了解一个概念，即**如何将两个有序数列合并成一个有序数列。**  
代码如下：

//将两个有序数组合并，a[] and b[] 合并成 c[]
    void Merge_array(int a[], n, int b[], m, int c[])
    {
        int i, j, k;
    
        i = j = k = 0;
        while (i < n && j < m)
        {
            if (a[i] < b[j])
                c[k++] = a[i++]; //c[k] = a[i];k++;i++;这里j不变
            else
                c[k++] = b[j++]; //c[k] = b[i];k++;j++;这里i不变
        }
        //到这里总会有一个数组会先结束，将剩下的数组的剩余数据依次补充进c[]就可以了
        while (i < n)
            c[k++] = a[i++];
    
        while (j < m)
            c[k++] = b[j++];
    }

了解了上述合并原理后，写归并排序的代码就比较容易了。  
**以下为使用递归原理的代码：**

// 用于输出数列
    void show(int a[],int n)
    {
        int i;
        for(i = 0; i < n; i++)
            cout << a[i] << ' ';
        cout << endl;
    }
    //将有二个有序数列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];  /**将temp重新赋给a[]*/
    }
    
    // 递归分解和合并
    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); //再将二个有序数列合并
        }
    }
    
    bool MergeSort(int a[], int n)
    {
        int *p = new int[n];
        if (p == NULL)
            return false;
        mergesort(a, 0, n - 1, p);
        show(a,9);  /*用于输出数列*/
        delete[] p;
        return true;
    }

**使用非递归方法，代码如下：**

/*此函数用于合并两个数列*/
    void sort(int *arr3,int *arr1,int begin,int m,int end){
        int i=begin,j=m+1,k,h;
        for(k=i; i<=m && j<=end;k++){
            if(arr3[i] < arr3[j])
                arr1[k] = arr3[i++];
            else
                arr1[k] = arr3[j++];
        }
        if(i <= m){
            for(h=0; h<=m-i;h++)
                arr1[k+h] = arr3[i+h];
        }else{
            for(h=0; h<=end-j;h++)
                arr1[k+h] = arr3[j+h];
        }
    }
    
    void Merge(int *arr1,int *temp,int k,int length){
        int i = 0,j;
        while(i <= length-2*k){
            sort(arr1,temp,i,i+k-1,i+2*k-1);
            i += 2*k;
        }
        if(i < length-k+1) //如过剩余个数比一个k长度还多...那么就在进行一次合并
            sort(arr1,temp,i,i+k-1,length-1);
        else
            for(j=i;j<length;j++)
                temp[j] = arr1[j];
        for(i=0;i<length;i++){
            arr1[i] = temp[i];
        }
    }
    
    void MergeSort2(int *arr,int length){
        int *temp = new int[length];
        int i = 1;
        while(i<length){
            Merge(arr,temp,i,length);
            i *= 2;
        }
    }

**总代码如下：**

#include <iostream>
    
    using namespace std;
    
    void show(int a[],int n)
    {
        int i;
        for(i = 0; i < n; i++)
            cout << a[i] << ' ';
        cout << endl;
    }
    
    /*递归*/
    //将有二个有序数列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];  /**将temp重新赋给a[]*/
    }
    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); //再将二个有序数列合并
        }
    }
    /*递归法，归并排序函数*/
    bool MergeSort(int a[], int n)
    {
        int *p = new int[n];
        if (p == NULL)
            return false;
        mergesort(a, 0, n - 1, p);
        show(a,10);
        delete[] p;
        return true;
    }
    
    /**非递归*/
    /**此函数用于合并两个数列*/
    void sort(int *arr3,int *arr1,int begin,int m,int end){
        int i=begin,j=m+1,k,h;
        for(k=i; i<=m && j<=end;k++){
            if(arr3[i] < arr3[j])
                arr1[k] = arr3[i++];
            else
                arr1[k] = arr3[j++];
        }
        if(i <= m){
            for(h=0; h<=m-i;h++)
                arr1[k+h] = arr3[i+h];
        }else{
            for(h=0; h<=end-j;h++)
                arr1[k+h] = arr3[j+h];
        }
    }
    
    void Merge(int *arr1,int *temp,int k,int length){
        int i = 0,j;
        while(i <= length-2*k){
            sort(arr1,temp,i,i+k-1,i+2*k-1);
            i += 2*k;
        }
        if(i < length-k+1) //如过剩余个数比一个k长度还多...那么就在进行一次合并
            sort(arr1,temp,i,i+k-1,length-1);
        else
            for(j=i;j<length;j++)
                temp[j] = arr1[j];
        for(i=0;i<length;i++){
            arr1[i] = temp[i];
        }
    }
    
    /*非递归：归并排序函数*/
    void MergeSort2(int *arr,int length){
        int *temp = new int[length];
        int i = 1;
        while(i<length){
            Merge(arr,temp,i,length);
            i *= 2;
        }
    }
    
    int main()
    {
        int a[10] = {
       1,2,0,5,8,9,7,3,6,4};
        cout << "排序前数据：" << endl;
        show(a,10);
    
        cout << "排序后数据：" << endl;
        MergeSort2(a,10);
        show(a,10);
        //MergeSort(a,10);
        return 0;
    }

![这里写图片描述][20150624202729993]

/*点滴积累，我的一小步O(∩\_∩)O~*/

[http_blog.csdn.net_morewindows_article_details_6678165]: http://blog.csdn.net/morewindows/article/details/6678165/
[http_www.cnblogs.com_xing901022_p_3671771.html]: http://www.cnblogs.com/xing901022/p/3671771.html
[20150624202729993]: /images/20220731/2aede9921242445cb7198e8e5876f025.png