数据结构：排序—归并排序（四 ）

一、归并排序

基本思想：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

基本思路：根据上述的说法，我们要将一组数据分成一个一个的子序列，然后让这些子序列有序，最后将这些有序的子序列合并，并将他排序，形成一个有序的序列。

我们要将一组数据分成子序列，而当我们把这组数据都分成一个一个的单个数据的时候，我们发现他一定是有序的。这时我们就可以进行两组之间的合并了，对于他们的合并，我们完全可以根据我们要合并数据的个数创建一个数组，并将数据进行排序，按照从小到大的顺序放入数组中，在这样的不断重复的过程中我们就实现了归并排序。

分割方法：我们先创建两个指针，分别指向一组数据的头和尾，然后我们按照对半的方式得到中间结点mid，然后再利用递归的方式分割左右两边，每次传入新的头和尾，左边的头尾分别为left和mid,右边的头尾分别为mid+1和right。

排序方法：我们先要根据传入数据的头和尾，根据他们的差值+1得到要创建数组的长度，然后再创建五个指针，k（作为指针指向数组下标）,s1(指向left),e1(指向中间结点mid),s2(指向中间结点mid+1处)，e2(指向right)，此时我们发现我们的s1和e1就是，我们左边的第一个数据和最后一个数据，s2和e2就是，我们右边边的第一个数据和最后一个数据，而我们知道左边和右边已经是有序的了，如果s1的值比s2小，我们就将s1的值放入数组中，并让s1和k向后移动一位，如果s2的值比s1小，我们就将s2的值放入数组中，并让s2和k向后移动一位。如果移动完后发现一边已经都进入数组中了即s1和s2的指向超过了e1和e2,我们就将另一边的剩余数据放入数组中。最后我们循环这个数组，更新临时数组的数据，为了防止每次递归，后更新的是同一个位置，我们要将原数组的下标更新位置设置为i+left，这样就能防止更新的是同一个位置。

  public static void mergeSort(int[] arr){
        mergeSortChild(arr,0,arr.length-1);
    }

    public static void mergeSortChild(int[] arr, int left, int right) {
        if(left >= right){
            return;
        }
        int mid = (left+right)/2;
        mergeSortChild(arr,left,mid);
        mergeSortChild(arr,mid+1,right);
        merge(arr,left,right,mid);
    }

    public static void merge(int[] arr,int left,int right,int mid){
        int[] keyArr = new int[right-left+1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        while(s1 <= e1 && s2<= e2){
            if(arr[s1] < arr[s2]){
                keyArr[k++] = arr[s1++];
            }else{
                keyArr[k++] = arr[s2++];
            }
        }
        while(s1 <= e1){
            keyArr[k++] = arr[s1++];
        }
        while(s2 <= e2){
            keyArr[k++] = arr[s2++];
        }
        for (int i = 0; i < keyArr.length; i++) {
            arr[i+left] = keyArr[i];
        }
    }

二、归并排序的非递归实现

基本思路：我们可以先让一组数据，一个一个的有序（gap= 1），然后再让他们两个两个的有序(gap=2)，最后如果我们的gap>arr.length了就代表我们的数组已经有序了。因此我们可以利用一个循环，我们还是要的到一个中间位置而这个中间位置就等于left + gap - 1,每次left = i,right= mid+gap每次合并排位两组数后我们要让i跳到跳到另一边因此要i +=gap*2。

public static void merge(int[] arr,int left,int right,int mid){
        int[] keyArr = new int[right-left+1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        while(s1 <= e1 && s2<= e2){
            if(arr[s1] < arr[s2]){
                keyArr[k++] = arr[s1++];
            }else{
                keyArr[k++] = arr[s2++];
            }
        }
        while(s1 <= e1){
            keyArr[k++] = arr[s1++];
        }
        while(s2 <= e2){
            keyArr[k++] = arr[s2++];
        }
        for (int i = 0; i < keyArr.length; i++) {
            arr[i+left] = keyArr[i];
        }
    }

    //归并排序非递归
    public static void mergeSortNor(int[] arr) {
        int gap = 1;
        while (gap < arr.length) {
            for (int i = 0; i < arr.length; i += 2 * gap) {
                int left = i;
                int mid = left + gap - 1;
                if (mid >= arr.length) {
                    mid = arr.length - 1;
                }
                int right = mid + gap;
                if (right >= arr.length) {
                    right = arr.length - 1;
                }
                merge(arr, left, right, mid);
            }
            gap *= 2;
        }
    }

好了，今天的分享就到这里了，还请大家多多关注，我们下一篇见！