数据结构与算法之归并排序

冷不防 2022-01-05 07:57 319阅读 0赞

# 数据结构与算法之归并排序 #

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

## 目录： ##

1.  归并排序介绍
2.  归并排序思想示意图
3.  代码实现

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

### 1. 归并排序介绍 ###

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。即先将每个子序列有序，再使子序列短间有序。它的时间复杂度是 O(nlogn)，空间复杂度是 O(n)，是稳定的排序算法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]

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

### 2. 归并排序思想示意图 ###

1.  归并排序思想示意图1-基本思想:  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]  
    说明:  
    可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程。
2.  归并排序思想示意图2-合并相邻有序子序列:  
    再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将\[4,5,7,8\]和\[1,2,3,6\]两个已经有序的子序列，合并为最终序列\[1,2,3,4,5,6,7,8\]，来看下实现步骤  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]

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

### 3. 代码实现 ###

代码实现一：

import java.util.Arrays;
    
    public class MergeSort {
        
        public static void main(String[] args) {
        
            int[] arr= {
        5,3,1,2,6};
            mergeSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        private static void mergeSort(int[] arr) {
        
           if (arr==null||arr.length<2)
               return;
           mergeSort(arr,0,arr.length-1);
        }
    
        private static void mergeSort(int[] arr,int l,int r) {
        
            if (l == r)
                return;
            int mid = (l+r)/2;
            mergeSort(arr,l,mid);
            mergeSort(arr,mid+1,r);
            merge(arr,l,mid,r);
        }
    
        private static void merge(int[] arr, int l, int mid, int r) {
        
            int[] help = new int[r-l+1];
            int i = 0;
            int p1 = l;
            int p2 = mid+1;
            while (p1<=mid&&p2<=r)
                help[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
    
            while (p1<=mid)
                help[i++] = arr[p1++];
    
            while (p2<=r)
                help[i++] = arr[p2++];
    
            for (i = 0; i < help.length; i++)
                arr[l+i] = help[i];
        }
    }

代码实现二：

import java.util.Arrays;
    
    public class MergeSort {
        
        public static void main(String[] args) {
        
            int[] arr = {
        8,4,5,7,1,3,6,2};
            int temp[] = new int[arr.length];
            mergeSort(arr, 0, arr.length - 1, temp);
    
            System.out.println("归并排序后=" + Arrays.toString(arr));
        }
    
        //分+合的方法
        public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        
            if (left < right) {
        
                int mid = (left + right) / 2; //中间索引
                //向左递归进行分解
                mergeSort(arr, left, mid, temp);
                //向右递归进行分解
                mergeSort(arr, mid + 1, right, temp);
                //到合并
                merge(arr, left, mid, right, temp);
            }
        }
    
        //合并的方法
    
        /**
         * @param arr   带排序的原始数组
         * @param left  左边有序序列的初始索引
         * @param mid   中间索引
         * @param right 右边索引
         * @param temp  中转的数组
         */
        public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        
            int i = left; //初始化i，左边有序序列的初始索引
            int j = mid + 1; //右边有序序列的初始化索引
            int t = 0; //指向temp数组的当前索引
         
            //1. 先把左右两边的数据按规则填充到temp数组
            //直到左右两边的有序序列，有一边处理完毕为止
            while (i <= mid && j <= right) {
            //继续
                if (arr[i] <= arr[j]) {
        
                    //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
                    //即将左边的当前元素，拷贝到temp数组
                    //然后t++，i++
                    temp[t] = arr[i];
                    ++t;
                    ++i;
                } else {
         //反之将右边有序序列的当前元素填充到temp数组
                    temp[t] = arr[j];
                    ++t;
                    ++j;
                }
            }
    
            //2. 把有剩余数据的一边的数据依次填充到temp
            while (i <= mid) {
             //左边的有序序列还有剩余的元素，就全部填充到temp
                temp[t] = arr[i];
                ++t;
                ++i;
            }
    
            while (j <= right) {
             //右边的有序序列还有剩余的元素，就全部填充到temp
                temp[t] = arr[j];
                ++t;
                ++j;
            }
            
            //3. 将temp数据的元素拷贝到arr
            //注意：不是每次都拷贝所有
            t = 0;
            //第一次合并tempLeft = 0 ，right = 1 // tempLeft=2 ，right= 3 //tempLeft=0，right=3
            for (int tempLeft = left; tempLeft <= right; ++tempLeft) {
        
                arr[tempLeft] = temp[t];
                ++t;
            }
        }
    }

编译结果  
![在这里插入图片描述][20190623145835863.png]  
800万条数据大概3s排完。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: /images/20211229/08dbf5039d3048539718472c1e52b823.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: /images/20211229/8b40b90f08414e2bbd73d25c8c7edc44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]: /images/20211229/b3c10f4c65a24ef1a0cd51c6a5acd69c.png
[20190623145835863.png]: /images/20211229/b58a417f2bf043f7965fef8111467899.png