java实现归并排序算法

懒驴 2022年12月30日 149次浏览

归并排序算法

归并排序算法: 归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并算法操作: 归并操作,也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。
如 设有数列{6,202,100,301,38,8,1}
初始状态:6,202,100,301,38,8,1
第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;
第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;
第三次归并后:{1,6,8,38,100,202,301},比较次数:4;
总的比较次数为:3+4+4=11;
逆序数为14

归并排序示意图


Java代码实现 ↓↓↓↓↓↓↓

/***
 * 归并排序基础代码
 */
public class MergeSortBase {

    /**
     * 分 和 合并
     */
    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);
            // 最后合并
            // 由于是递归,合并这里一定是栈顶的先执行(两边数组各只有一个数时)
            // 第一次:left = 0,right=1
            // 第二次:left = 2,right=3
            // 第三次:left = 0,right=3
            // System.out.println("left=" + left + ";right=" + right);
            merge(arr, left, mid, right, temp);
        }
    }

    /**
     *
     *  最难的是合并,所以可以先完成合并的方法,此方法请参考 基本思想 和 思路分析中的图解来完成
     *  动脑筋
     * @param arr   要排序的原始数组
     * @param left  因为是合并,所以要得到左右两边的的数组信息,这个是左侧数组的第一个索引值
     * @param mid   因为是一个数组,标识是第一个数组的最后一个索引,即 mid+1 是右侧数组的第一个索引,即中间索引
     * @param right 右侧数组的结束索引,右边数组的最后一个数
     * @param temp  临时空间,临时数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        // 定时临时变量,用来遍历数组比较
        int l = left;  // 左边有序数组的初始索引
        int r = mid + 1; // 右边有序数组的初始索引
        int t = 0; // temp 数组中当前最后一个有效数据的索引

        // 1. 按思路先将两个数组(有序的)有序的合并到 temp 中
        // 因为是合并两个数组,所以需要两边的数组都还有值的时候才能进行 比较合并
        // 若其中一个数组的值遍历完了(取完了),那么就跳出该循环,把另一个数组所剩的值,直接copy进临时数组即可
        while (l <= mid && r <= right) {
            // 如果左边的比右边的小,则将左边的该元素填充到 temp 中
            // 并移动 t++,l++,好继续下一个
            if (arr[l] < arr[r]) {
                temp[t] = arr[l];
                t++;//移动 temp 临时数组中当前最后一个有效数据的索引
                l++; //左边原始数组的索引移动
            }
            // 否则则将右边的移动到 temp 中
            else {
                temp[t] = arr[r];
                t++;//移动 temp 临时数组中当前最后一个有效数据的索引
                r++;//右边原始数组的索引移动
            }
        }
        // 2. 如果有任意一边的数组还有值,则依序将剩余数据填充到 temp 中
        // 如果左侧还有值
        while (l <= mid) {
            temp[t] = arr[l];
            t++;
            l++;
        }
        // 如果右侧还有值
        while (r <= right) {
            temp[t] = arr[r];
            t++;
            r++;
        }

        // 3. 将 temp 数组,拷贝到原始数组
        // 注意:只拷贝当前temp有效数据到对应的原始数据中,通俗点说,就是原始数组中要排序的数据,通过temp排成了有序的,然后将temp中的有序数据将原始数组中原来要排序的那部分覆盖了就行了
        int tempL = left; // 从左边开始拷贝,左边第一个值的索引
        t = 0;  // temp 中的有效值索引,有效值边界可以通过 right 判定,因为合并两个数组到 temp 中,边界就是 right ,这里自己好好想想
        /*
         * 对于 8,4,5,7,1,3,6,2 这个数组,
         * 从栈顶开始合并:8,4 | 5,7       1,3 | 6,2
         * 先左递归的话:
         * 第一次:8,4 合并:tempL=0,right=1
         * 第二次:5,7 合并:tempL=2,right=3
         * 第三次:4,8 | 5,7 进行合并,tempL=0,right=3
         * 直到左递归完成,得到左侧一个有序的序列:4,5,7,8 然后再开始递归右边那个无序的
         * 最后回到栈底分解成两个数组的地方,将两个数组合并成一个有序数组
         * 这里真的得自己想了,我只能这么说了。
         */
        System.out.println("tempL=" + tempL + "; right=" + right);
        while (tempL <= right) {
            arr[tempL] = temp[t];
            tempL++;
            t++;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{97, 58, 3, 12, 88, 77, 101, 7, 22, 33, 44, 8, 66, 22};
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println("排序后:" + Arrays.toString(arr));
    }

}

代码纯享版↓↓↓↓↓↓↓↓↓


/***
 * 归并排序基础代码
 */
public class MergeSortBase {
    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);
          
            // System.out.println("left=" + left + ";right=" + right);
            merge(arr, left, mid, right, temp);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int l = left;  
        int r = mid + 1; 
        int t = 0; 
        while (l <= mid && r <= right) {
            if (arr[l] < arr[r]) {
                temp[t] = arr[l];
                t++;
                l++; 
            }else {
                temp[t] = arr[r];
                t++;
                r++;
            }
        }
        while (l <= mid) {
            temp[t] = arr[l];
            t++;
            l++;
        }
        while (r <= right) {
            temp[t] = arr[r];
            t++;
            r++;
        }
        int tempL = left; // 从左边开始拷贝,左边第一个值的索引
        t = 0;  
        System.out.println("tempL=" + tempL + "; right=" + right);
        while (tempL <= right) {
            arr[tempL] = temp[t];
            tempL++;
            t++;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{97, 58, 3, 12, 88, 77, 101, 7, 22, 33, 44, 8, 66, 22};
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println("排序后:" + Arrays.toString(arr));
    }

}

运行结果 ↓↓↓↓↓↓↓

运行结果