[排序算法]--归并排序的Java实现

不念不忘少年蓝@ 2022-07-12 01:17 165阅读 0赞

> 归并排序（2-路归并）：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，归并排序将两个已排序的表合并成一个表。

下面先看一个归并排序过程的示例：  
待排序列（14,12,15,13,11,16）：  
首先用分割的方法，将这个序列分割成一个个已经排好序的子序列，然后再利用归并的办法将一个个子序列合并成排好序的序列，如下图：  
![归并排序实例：][SouthEast]

上面很明显就是采用先 “分割” 再 “合并” 的思想。我们首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。

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

/** * 把有序数组a和有序数组b 合并到数组c中，这里假设数组c的容量足够大，可以容纳数组a和数组b中的所有元素。 * @param a * @param n 数组a的长度n * @param b * @param m 数组b的长度m * @param c */
    public static void mergeArray(int a[], int n, int b[], int 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++];
            } else {
                c[k++] = b[j++];
            }
        }
        //将数组a或则b中剩余的元素加入数组c中
        while (i<n){
            c[k++] = a[i++];
        }
    
        while (j < m){
            c[k++] = b[j++];
        }
    }//end

上面的合并算法的效率还是比较高的，可以达到O(n)的时间复杂度。

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

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

/** * 将a[first, mid] 和 a[mid+1, last] 合并 * @param a * @param first * @param mid * @param last * @param temp */
    private static 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];
        }
    }
    
    /** * 二路归并 使用递归解决. * @param a * @param first 数组的起始下标 * @param last 数组的结束下标 * @param temp 辅助数组 */
    public static 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); //再将两个有序序列合并.
        }
    }

测试：

public static void main(String[] args) {
        int[] arr = {
       1,9,3,12,7,8,3,4,65,22};
        int[] temp = {
       0,0,0,0,0,0,0,0,0,0};
    
    
        mergeSort(arr, 0, arr.length-1, temp);
    
        for(int i:arr){
            System.out.print(i+",");
        }
    }

输出：

1,3,3,4,7,8,9,12,22,65,

归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N\*logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N\*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。

本文给出的是数组实现，下面也给出一个单链表实现的思路，其实就是leetcode的一个题目：  
[http://blog.csdn.net/u010853261/article/details/54884650][http_blog.csdn.net_u010853261_article_details_54884650]

本文所有代码的github地址：  
[https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Algorithm/MergeSort.java][https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Algorithm_MergeSort.java]

[SouthEast]: /images/20220711/824af89d4f634b30839a7bccdc312717.png
[http_blog.csdn.net_u010853261_article_details_54884650]: http://blog.csdn.net/u010853261/article/details/54884650
[https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Algorithm_MergeSort.java]: https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Algorithm/MergeSort.java