排序算法(5)--归并排序

• 1.1 递归实现
• 1.2 非递归实现

**递归实现归并排序的基本思想: 就是一直对半分, 直到分到剩下一个或者是两个元素的时候为止, 然后对分开到最后的小序列进行排序比较, 比较完后回到上一层的序列中再次进行比较, 直到序列整体有序. **
详细过程如下:

代码如下:

public class MergeSort {
    
    public static void merge(int[] arr, int low, int mid, int high) {
        int s1 = low;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = high;

        int[] tmp = new int[high - low + 1];
        int k = 0; // 代表 tmp 数组的下标

        while (s1 <= e1 && s2 <= e2) {
            if (arr[s1] <= arr[s2]) {
                tmp[k++] = arr[s1++];
            } else {
                tmp[k++] = arr[s2++];
            }
        }
        // 有两种情况
        while (s1 <= e1) {
            // 说明第二个归并段没有了数据, 把第一个归并段剩下的数据全部拷过来
            tmp[k++] = arr[s1++];
        }
        while (s2 <= e2) {
            // 说明第一个归并段没有了, 把第二个归并段剩下的数据全部拷贝过来
            tmp[k++] = arr[s2++];
        }
        // tmp 数组当中, 存储的就是当前归并好的数据
        for (int i = 0; i < tmp.length; i++) {
            arr[i + low] = tmp[i];
        }
    }

    public static void mergeSortInternal(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        mergeSortInternal(arr, low, mid);
        mergeSortInternal(arr, mid + 1, high);
        // 合并的过程
        merge(arr, low, mid, high);
    }

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

    public static void main(String[] args) {
        int[] arr = {3,2,5,7,1,6,8,9,4};
        System.out.println(Arrays.toString(arr));
        mergeSort1(arr);
        System.out.println(Arrays.toString(arr));
    }
}

运行结果:

性能分析:

对于非递归来实现的基本思想就是先从 i = 1开始, 对 i*2 的序列进行排序, 如下图所示, 首先对 3,2 进行排序, 然后再对 2,3,5,7 进行排序, 然后再对 1,2,3,5,6,7,8,9 八个元素进行排序, 最后再对所有元素进行排序.
详细思路如下:

代码如下:

public class MergeSort {
    public static void merge2(int[] arr, int gap) {
        int[] tmp = new int[arr.length];
        int k = 0;

        int s1 = 0;
        int e1 = s1 + gap - 1;
        int s2 = e1 + 1;
        int e2 = s2 + gap - 1 < arr.length ? s2 + gap - 1 : arr.length - 1;

        // 需要保证有两个归并段
        while (s2 < arr.length) {
            while (s1 <= e1 && s2 <= e2) {
                if (arr[s1] <= arr[s2]) {
                    tmp[k++] = arr[s1++];
                } else {
                    tmp[k++] = arr[s2++];
                }
            }
            while (s1 <= e1) {
                tmp[k++] = arr[s1++];
            }
            while (s2 <= e2) {
                tmp[k++] = arr[s2++];
            }
            // 一组完成后, 确定新的区间的开始和结束
            s1 = e2 + 1;
            e1 = s1 + gap - 1;
            s2 = e1 + 1;
            e2 = s2 + gap - 1 < arr.length ? s2 + gap - 1 : arr.length - 1;
        }
        while (s1 <= arr.length - 1) {
            tmp[k++] = arr[s1++];
        }
        for (int i = 0; i < tmp.length; i++) {
            arr[i] = tmp[i];
        }
    }
    public static void mergeSort2(int[] arr) {
        for (int i = 1 ; i < arr.length; i*=2) {
            merge2(arr, i);
        }
}


    public static void main(String[] args) {
        int[] arr = {3,2,5,7,1,6,8,9,4};
        System.out.println(Arrays.toString(arr));
        mergeSort2(arr);
        System.out.println(Arrays.toString(arr));
    }
}

运行结果: