归并排序（Merge Sort）

发布时间：2018-04-20作者：laosun阅读（1651）

java归并排序（Merge Sort），归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

基本思想：

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序示例：

合并方法：

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为n-i +1、n-m。

j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束
//选取r[i]和r[j]较小的存入辅助数组rf
如果r[i]<r[j]，rf[k]=r[i]； i++； k++；转⑵
否则，rf[k]=r[j]； j++； k++；转⑵
//将尚未处理完的子表中元素存入rf
如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空
如果j<=n , 将r[j…n] 存入rf[k…n] //后一子表非空
合并结束。

public class MergeSortTest {    
    
    public static void main(String[] args) {    
        int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };    
        print(data);    
        mergeSort(data);    
        System.out.println("排序后的数组：");    
        print(data);    
    }    
    
    public static void mergeSort(int[] data) {    
        sort(data, 0, data.length - 1);    
    }    
    
    public static void sort(int[] data, int left, int right) {    
        if (left >= right)    
            return;    
        // 找出中间索引    
        int center = (left + right) / 2;    
        // 对左边数组进行递归    
        sort(data, left, center);    
        // 对右边数组进行递归    
        sort(data, center + 1, right);    
        // 合并    
        merge(data, left, center, right);    
        print(data);    
    }    
    
    /**  
     * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序  
     *   
     * @param data  
     *            数组对象  
     * @param left  
     *            左数组的第一个元素的索引  
     * @param center  
     *            左数组的最后一个元素的索引，center+1是右数组第一个元素的索引  
     * @param right  
     *            右数组最后一个元素的索引  
     */    
    public static void merge(int[] data, int left, int center, int right) {    
        // 临时数组    
        int[] tmpArr = new int[data.length];    
        // 右数组第一个元素索引    
        int mid = center + 1;    
        // third 记录临时数组的索引    
        int third = left;    
        // 缓存左数组第一个元素的索引    
        int tmp = left;    
        while (left <= center && mid <= right) {    
            // 从两个数组中取出最小的放入临时数组    
            if (data[left] <= data[mid]) {    
                tmpArr[third++] = data[left++];    
            } else {    
                tmpArr[third++] = data[mid++];    
            }    
        }    
        // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）    
        while (mid <= right) {    
            tmpArr[third++] = data[mid++];    
        }    
        while (left <= center) {    
            tmpArr[third++] = data[left++];    
        }    
        // 将临时数组中的内容拷贝回原数组中    
        // （原left-right范围的内容被复制回原数组）    
        while (tmp <= right) {    
            data[tmp] = tmpArr[tmp++];    
        }    
    }    
    
    public static void print(int[] data) {    
        for (int i = 0; i < data.length; i++) {    
            System.out.print(data[i] + "\t");    
        }    
        System.out.println();    
    }    
    
}

归并的迭代算法

1 个元素的表总是有序的。所以对n 个元素的待排序列，每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表，所得子表除最后一个子表长度可能为1 外，其余子表长度均为2。再进行两两合并，直到生成n 个元素按关键码有序的表。

void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
  
//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
{  
    int j,k;  
    for(j=m+1,k=i; i<=m && j <=n ; ++k){  
        if(r[j] < r[i]) rf[k] = r[j++];  
        else rf[k] = r[i++];  
    }  
    while(i <= m)  rf[k++] = r[i++];  
    while(j <= n)  rf[k++] = r[j++];  
    print(rf,n+1);  
}  
  
void MergeSort(ElemType *r, ElemType *rf, int lenght)  
{   
    int len = 1;  
    ElemType *q = r ;  
    ElemType *tmp ;  
    while(len < lenght) {  
        int s = len;  
        len = 2 * s ;  
        int i = 0;  
        while(i+ len <lenght){  
            Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并  
            i = i+ len;  
        }  
        if(i + s < lenght){  
            Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并  
        }  
        tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf  
    }  
}  
  
  
int main(){  
    int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    int b[10];  
    MergeSort(a, b, 10);  
    print(b,10);  
    cout<<"结果：";  
    print(a,10);  
  
}

两路归并的递归算法

void MSort(ElemType *r, ElemType *rf,int s, int t)  
{   
    ElemType *rf2;  
    if(s==t) r[s] = rf[s];  
    else  
    {   
        int m=(s+t)/2;          /*平分*p 表*/  
        MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/  
        MSort(r, rf2, m+1, t);      /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/  
        Merge(rf2, rf, s, m+1,t);   /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/  
    }  
}  
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  
{   /*对顺序表*p 作归并排序*/  
    MSort(r, rf,0, n-1);  
}