分治法——归并排序

￡神魔★判官ぃ 2021-06-22 15:36 449阅读 0赞

# 归并排序 #

归并排序是成功应用分治法的完美例子，归并排序是按照记录在序列中的位置对序列进行划分。

## 【问题】 ##

应用归并排序方法对一个记录序列进行升序排序。归并排序（merge sort）的分治策略如下：

1.  划分：将待排序的序列r1,r2,···，rn划分成两个长度相等的子序列r1，···，rn/2和rn/2+1,···，rn。
2.  求解子问题：分别对这两个子序列进行排序，得到两个有序的子序列。
3.  合并：将这两个有序子序列合并成一个有序的子序列。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70]

## 【想法】 ##

归并排序首先执行划分过程，将序列划分成两个子序列，  
如果子序列的长度为1，则划分结束，  
否则继续执行划分，结果将具有n个待排序的记录序列划分成n个长度为1的有序子序列，  
然后进行两两合并，得到\[n/2\]个长度为2的有序子序列（最后一个序列的长度可能为1），  
再进行两两合并，得到\[n/4\]个长度为4的有序序列（最后一个序列的长度可能小于4），……  
直至得到一个长度为n的有序序列。

## 【算法】 ##

设对数组r\[n\]进行升序排序，归并排序的递归算法用伪代码描述如下：

归并排序 MergeSort
    输入：待排序的数组r[n]，待排序的区间[s,t]
    输出：升序序列r[s]~r[t]
    
    1. 如果s等于t，则待排序区间只有一个记录，算法结束；
    2. 计算划分中点：m=(s+t)/2；
    3. 对前半个子序列r[s]~r[m]进行升序排列；
    4. 对后半个子序列r[m+1]~r[t]进行升序排列；
    5. 合并两个升序序列r[s]~r[m]和r[m+1]~r[t]；

## 【算法分析】 ##

设待排序的记录个数为n，则执行一趟合并算法的时间复杂性为*O(n)*，所以归并排序算法存在如下递推式：  
![在这里插入图片描述][20191120172305339.png]  
归并排序的时间代价是*O(n log2n)*。

## 【算法实现】 ##

函数`mergeSort()`实现一个数组的归并排序。  
函数`merge()`实现两个子序列的合并操作。

import java.util.Arrays;
    
    /** * 归并排序算法 * * @author veeja.Liu * @date 2019/11/20 - 12:54 * @E-mail veejaliu@gmail.com */
    public class MergeSortDemo { 
        public static void main(String[] args) { 
            int[] array = { 8, 3, 2, 6, 7, 1, 5, 4};
            System.out.println(Arrays.toString(array));
    
            mergeSort(array, 0, array.length-1);
            System.out.println(Arrays.toString(array));
        }
    
        /** * 合并子序列 * * @param r * @param r1 * @param s * @param m * @param t */
        public static void merge(int r[], int r1[], int s, int m, int t) { 
            int i = s;
            int j = m + 1;
            int k = s;
            while (i <= m && j <= t) { 
                // 取出r[i]和r[j]中较小的放入r1[k]
                if (r[i] <= r[j]) r1[k++] = r[i++];
                else r1[k++] = r[j++];
            }
    
            // 如果第一个子序列没有处理完，则进行收尾处理
            while (i <= m) { 
                r1[k++] = r[i++];
            }
            // 如果第二个子序列没有处理完，则进行收尾处理
            while (j <= t) { 
                r1[k++] = r[j++];
            }
        }
    
        /** * 对序列r[s]~r[t]进行归并排序 * * @param r * @param s * @param t */
        public static void mergeSort(int r[], int s, int t) { 
            int m;
            // 数组r1是临时数组，假设最多1000个元素
            int[] r1 = new int[1000];
            // 递归的边界条件，只有一个记录
            if (s == t) return;
            else { 
                // 划分
                m = (s + t) / 2;
                // 求解子问题1，归并排序前半个子序列
                mergeSort(r, s, m);
                // 求解子问题2，归并排序后半个子序列
                mergeSort(r, m + 1, t);
                // 合并两个有序子序列，结果存在数组r1中
                merge(r, r1, s, m, t);
                // 将有序序列传回数组中
                for (int i = s; i <= t; i++) { 
                    r[i] = r1[i];
                }
            }
        }
    }

运行结果：  
![在这里插入图片描述][20191120174941182.png]

--------------------

END.  
如果你不沉下心来认真练习，所有的阅读都是白费的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70]: /images/20210615/28589a92342240a78dea1e107b418837.png
[20191120172305339.png]: /images/20210615/fc66248de7a44483bfe1d7635c71db84.png
[20191120174941182.png]: /images/20210615/dd0415aad1af4c078e1a8007660c6580.png