• 归并排序— —递归、非递归实现【十大经典排序算法】

    归并排序

    先归（归类/拆分），再并：就是指先将数组分区（左半区、右半区），然后再让各自分区有序，最后将分区合并，让整个分区整体有序

    在这里插入图片描述

    一、递归实现

    1 首先定义process函数，用来拆分数组

    /**
 * 对arr的L到R位置进行拆分
 * @param arr
 * @param L
 * @param R
 */
public static void process(int[] arr, int L, int R){
    if(L == R){
        return;
    }
    int mid = L + ((R - L) >> 1);//防止越界【R-L右移相当于除以2】
    process(arr, L, mid);
    process(arr, mid+1, R);
    merge(arr, L, mid, R);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    2 定义merge函数，用来合并数组（分区排序后合并）

    /**
 * 合并左右两半区，并将结果拷贝到arr
 *
 * @param arr
 * @param L
 * @param M
 * @param R
 */
public static void merge(int[] arr, int L, int M, int R) {
    //定义结果数组
    int[] help = new int[R - L + 1];
    int i = 0;
    //p1指向左半区的head, p2指向右半区的head
    int p1 = L;
    int p2 = M + 1;
    //两边都未越界
    while (p1 <= M && p2 <= R) {
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= M) {
        help[i++] = arr[p1++];
    }
    while (p2 <= R) {
        help[i++] = arr[p2++];
    }
    //拷贝结果
    for (int j = 0; j < help.length; j++) {
        arr[L + j] = help[j];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    3 定义mergeSort，调用process函数，完成整体逻辑

    public static void mergeSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    process(arr, 0, arr.length - 1);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    4 整体代码

    public static void mergeSort1(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    process(arr, 0, arr.length - 1);
}

/**
 * 合并左右两半区，并将结果拷贝到arr
 *
 * @param arr
 * @param L
 * @param M
 * @param R
 */
public static void merge(int[] arr, int L, int M, int R) {
    //定义结果数组
    int[] help = new int[R - L + 1];
    int i = 0;
    //p1指向左半区的head, p2指向右半区的head
    int p1 = L;
    int p2 = M + 1;
    //两边都未越界
    while (p1 <= M && p2 <= R) {
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= M) {
        help[i++] = arr[p1++];
    }
    while (p2 <= R) {
        help[i++] = arr[p2++];
    }
    //拷贝结果
    for (int j = 0; j < help.length; j++) {
        arr[L + j] = help[j];
    }
}

/**
 * 对arr的L到R位置进行拆分
 * @param arr
 * @param L
 * @param R
 */
public static void process(int[] arr, int L, int R){
    if(L == R){
        return;
    }
    int mid = L + ((R - L) >> 1);//防止越界
    process(arr, L, mid);
    process(arr, mid+1, R);
    merge(arr, L, mid, R);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    二、非递归实现【迭代】

    不递归调用process函数，直接手动完成逻辑

    1 merge函数

     /**
  * 合并左右两半区，并将结果拷贝到arr
  *
  * @param arr
  * @param L
  * @param M
  * @param R
  */
 public static void merge(int[] arr, int L, int M, int R) {
     //定义结果数组
     int[] help = new int[R - L + 1];
     int i = 0;
     //p1指向左半区的head, p2指向右半区的head
     int p1 = L;
     int p2 = M + 1;
     //两边都未越界
     while (p1 <= M && p2 <= R) {
         help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
     }
     while (p1 <= M) {
         help[i++] = arr[p1++];
     }
     while (p2 <= R) {
         help[i++] = arr[p2++];
     }
     //拷贝结果
     for (int j = 0; j < help.length; j++) {
         arr[L + j] = help[j];
     }
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    2 mergeSort2代码

    /**
  * 以非递归方式合并[通过逐步增加步长的方式]【代替process函数】
  * @param arr
  */
 public static void mergeSort2(int[] arr) {
     if(arr == null || arr.length < 2){
         return;
     }
     int step = 1;
     int N = arr.length;
     while(step < N){//等于N是多此一举
         //先确定左半区分区【及边界条件】
         int L = 0;
         while(L < N){
             int M = 0;
             if(N - L >= step){
                 //表明够分区
                 M = L + step - 1;
             } else {
                 //不够分区，直接[x,x,x,x]:[x]
                 M = N - 1;
             }
             if(M == N - 1){
                 //到了数组末尾，无法继续分为两半区,直接跳出
                 break;
             }
             //确定右半区
             int R = 0;
             if(N - 1 - M >= step){
                 //够分右半区
                 R = M + step;
             } else {
                 R = N - 1;
             }
             //对划分好的区域进行排序，并合并
             merge(arr, L, M, R);
             if(R == N - 1){
                 break;
             } else {
                 //下一个左半区起始位置
                 L = R + 1;
             }
         }
         // N / 2 是向下取整
         if(step > N / 2){
             break;
         }
         step *= 2;
     }
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    3 整体代码：

    /**
 * 以非递归方式合并[通过逐步增加步长的方式]【代替process函数】
 * @param arr
 */
public static void mergeSort2(int[] arr) {
    if(arr == null || arr.length < 2){
        return;
    }
    int step = 1;
    int N = arr.length;
    while(step < N){//等于N是多此一举
        //先确定左半区分区【及边界条件】
        int L = 0;
        while(L < N){
            int M = 0;
            if(N - L >= step){
                //表明够分区
                M = L + step - 1;
            } else {
                //不够分区，直接[x,x,x,x]:[x]
                M = N - 1;
            }
            if(M == N - 1){
                //到了数组末尾，无法继续分为两半区,直接跳出
                break;
            }
            //确定右半区
            int R = 0;
            if(N - 1 - M >= step){
                //够分右半区
                R = M + step;
            } else {
                R = N - 1;
            }
            //对划分好的区域进行排序，并合并
            merge(arr, L, M, R);
            if(R == N - 1){
                break;
            } else {
                //下一个左半区起始位置
                L = R + 1;
            }
        }
        // N / 2 是向下取整
        if(step > N / 2){
            break;
        }
        step *= 2;
    }
}




 /**
  * 合并左右两半区，并将结果拷贝到arr
  *
  * @param arr
  * @param L
  * @param M
  * @param R
  */
 public static void merge(int[] arr, int L, int M, int R) {
     //定义结果数组
     int[] help = new int[R - L + 1];
     int i = 0;
     //p1指向左半区的head, p2指向右半区的head
     int p1 = L;
     int p2 = M + 1;
     //两边都未越界
     while (p1 <= M && p2 <= R) {
         help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
     }
     while (p1 <= M) {
         help[i++] = arr[p1++];
     }
     while (p2 <= R) {
         help[i++] = arr[p2++];
     }
     //拷贝结果
     for (int j = 0; j < help.length; j++) {
         arr[L + j] = help[j];
     }
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84

    三、使用对数器验证方法是否正确

    对数器：
    1.有一个你想要测的方法a；
    2.实现一个绝对正确但是复杂度不好的方法b；
    3.实现一个随机样本产生器；
    4.实现对比算法a和b的方法；
    5.把方法a和方法b比对多次来验证方法a是否正确；
    6.如果有一个样本使得比对出错，打印样本分析是哪个方法出错；
    7.当样本数量很多时比对测试依然正确，可以确定方法a已经正确

    1 generateRandomArray构造随机数组

    private static int[] generateRandomArray(int maxSize, int maxValue) {
      int size = (int)(Math.random() * maxSize);
      int value;
      int[] arr = new int[size];
      for (int i = 0; i < size; i++) {
          value = (int)(Math.random() * maxValue);
          arr[i] = value;
      }
      return arr;
  }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    2 isEquals()、copyArray()

    public static boolean isEquals(int[] arr1, int[] arr2) {
    for (int i = 0; i < arr1.length; i++) {
        if(arr1[i] != arr2[i]){
            return false;
        }
    }
    return true;
}

private static int[] copyArray(int[] arr1) {
    int[] arr2 = new int[arr1.length];
    for (int i = 0; i < arr1.length; i++) {
        arr2[i] = arr1[i];
    }
    return arr2;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    package com.ali.test;

import java.util.Arrays;


public class Test05 {
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("测试开始-----");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            mergeSort1(arr1);
            mergeSort2(arr2);
            if(!isEquals(arr1, arr2)){
                System.out.println("error....");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                break;
            }
        }
        System.out.println("测试结束....");
    }

    public static void mergeSort1(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    /**
     * 合并左右两半区，并将结果拷贝到arr
     *
     * @param arr
     * @param L
     * @param M
     * @param R
     */
    public static void merge(int[] arr, int L, int M, int R) {
        //定义结果数组
        int[] help = new int[R - L + 1];
        int i = 0;
        //p1指向左半区的head, p2指向右半区的head
        int p1 = L;
        int p2 = M + 1;
        //两边都未越界
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        //拷贝结果
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];
        }
    }

    /**
     * 对arr的L到R位置进行拆分
     * @param arr
     * @param L
     * @param R
     */
    public static void process(int[] arr, int L, int R){
        if(L == R){
            return;
        }
        int mid = L + ((R - L) >> 1);//防止越界
        process(arr, L, mid);
        process(arr, mid+1, R);
        merge(arr, L, mid, R);
    }




    /**
     * 以非递归方式合并[通过逐步增加步长的方式]【代替process函数】
     * @param arr
     */
    public static void mergeSort2(int[] arr) {
        if(arr == null || arr.length < 2){
            return;
        }
        int step = 1;
        int N = arr.length;
        while(step < N){//等于N是多此一举
            //先确定左半区分区【及边界条件】
            int L = 0;
            while(L < N){
                int M = 0;
                if(N - L >= step){
                    //表明够分区
                    M = L + step - 1;
                } else {
                    //不够分区，直接[x,x,x,x]:[x]
                    M = N - 1;
                }
                if(M == N - 1){
                    //到了数组末尾，无法继续分为两半区,直接跳出
                    break;
                }
                //确定右半区
                int R = 0;
                if(N - 1 - M >= step){
                    //够分右半区
                    R = M + step;
                } else {
                    R = N - 1;
                }
                //对划分好的区域进行排序，并合并
                merge(arr, L, M, R);
                if(R == N - 1){
                    break;
                } else {
                    //下一个左半区起始位置
                    L = R + 1;
                }
            }
            // N / 2 是向下取整
            if(step > N / 2){
                break;
            }
            step *= 2;
        }
    }

    public static boolean isEquals(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; i++) {
            if(arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

    private static int[] copyArray(int[] arr1) {
        int[] arr2 = new int[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            arr2[i] = arr1[i];
        }
        return arr2;
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int size = (int)(Math.random() * maxSize);
        int value;
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            value = (int)(Math.random() * maxValue);
            arr[i] = value;
        }
        return arr;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162

    3 全部代码

    package com.ali.test;

import java.util.Arrays;


public class Test05 {
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("测试开始-----");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            mergeSort1(arr1);
            mergeSort2(arr2);
            if(!isEquals(arr1, arr2)){
                System.out.println("error....");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                break;
            }
        }
        System.out.println("测试结束....");
    }

    public static void mergeSort1(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    /**
     * 合并左右两半区，并将结果拷贝到arr
     *
     * @param arr
     * @param L
     * @param M
     * @param R
     */
    public static void merge(int[] arr, int L, int M, int R) {
        //定义结果数组
        int[] help = new int[R - L + 1];
        int i = 0;
        //p1指向左半区的head, p2指向右半区的head
        int p1 = L;
        int p2 = M + 1;
        //两边都未越界
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        //拷贝结果
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];
        }
    }

    /**
     * 对arr的L到R位置进行拆分
     * @param arr
     * @param L
     * @param R
     */
    public static void process(int[] arr, int L, int R){
        if(L == R){
            return;
        }
        int mid = L + ((R - L) >> 1);//防止越界
        process(arr, L, mid);
        process(arr, mid+1, R);
        merge(arr, L, mid, R);
    }




    /**
     * 以非递归方式合并[通过逐步增加步长的方式]【代替process函数】
     * @param arr
     */
    public static void mergeSort2(int[] arr) {
        if(arr == null || arr.length < 2){
            return;
        }
        int step = 1;
        int N = arr.length;
        while(step < N){//等于N是多此一举
            //先确定左半区分区【及边界条件】
            int L = 0;
            while(L < N){
                int M = 0;
                if(N - L >= step){
                    //表明够分区
                    M = L + step - 1;
                } else {
                    //不够分区，直接[x,x,x,x]:[x]
                    M = N - 1;
                }
                if(M == N - 1){
                    //到了数组末尾，无法继续分为两半区,直接跳出
                    break;
                }
                //确定右半区
                int R = 0;
                if(N - 1 - M >= step){
                    //够分右半区
                    R = M + step;
                } else {
                    R = N - 1;
                }
                //对划分好的区域进行排序，并合并
                merge(arr, L, M, R);
                if(R == N - 1){
                    break;
                } else {
                    //下一个左半区起始位置
                    L = R + 1;
                }
            }
            // N / 2 是向下取整
            if(step > N / 2){
                break;
            }
            step *= 2;
        }
    }

    public static boolean isEquals(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; i++) {
            if(arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

    private static int[] copyArray(int[] arr1) {
        int[] arr2 = new int[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            arr2[i] = arr1[i];
        }
        return arr2;
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int size = (int)(Math.random() * maxSize);
        int value;
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            value = (int)(Math.random() * maxValue);
            arr[i] = value;
        }
        return arr;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
  • 相关阅读:
    linux ethtool 命令详解
    jvm-sandbox demo 菜鸟学习
    基于SpringBoot构造超简易QQ邮件服务发送(分离-图解-新手)
    小白弄明白了 unix 时间戳的转换问题
    【AI】机器学习——支持向量机(非线性及分析)
    【Putty】win10 / win 11：SSH 远程连接工具 Putty 下载、安装
    jvm学习第三天
    Hive工作原理
    在Openresty中使用lua语言向请求浏览器返回请求头User-Agent里边的值
    智能语音之远场关键词识别实践（一）
  • 原文地址：https://blog.csdn.net/weixin_45565886/article/details/126149927