欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

算法——归并排序

程序员文章站 2022-07-03 19:37:42
归并排序算法是基于归并(Merge)操作的一种有效排序算法,是采用分治法(Divide and Conquer)的典型应用。基本思想:归并排序的原理是先将原始数组分解为多个子序列,然后对每个子序列进行排序,最后将排好序的子序列合并起来。/** * @Classname A * @Description TODO * @Date 2020/12/30 11:15 * @Created zzf */public class A { public static void main...

归并排序算法是基于归并(Merge)操作的一种有效排序算法,是采用分治法(Divide and Conquer)的典型应用。

基本思想:归并排序的原理是先将原始数组分解为多个子序列,然后对每个子序列进行排序,最后将排好序的子序列合并起来。



/**
 * @Classname A
 * @Description TODO
 * @Date 2020/12/30 11:15
 * @Created zzf
 */
public class A {
    public static void main(String[] args) {
        int[] arr = {11, 44, 5, 67, 49, 65, 1, 48, 9, 12};
        int[] tmp = new int[arr.length];
        for (int a : arr) {
            System.out.print(a + " ");
        }
        System.out.println("\n--------------------------------");
        mergeSort(arr, 0, arr.length - 1, tmp);
        System.out.println("--------------------------------");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void merge(int[] arr, int low, int mid, int high, int[] tmp) {
        int i = 0;
        //左边序列
        int j = low;
        //右边序列起始索引
        int k = mid + 1;
        while (j <= mid && k <= high) {
            if (arr[j] < arr[k]) {
                tmp[i++] = arr[j++];
            } else {
                tmp[i++] = arr[k++];
            }
        }
        //若左边序列还有剩余,则将其全部拷贝进tmp[]中
        while (j <= mid) {
            tmp[i++] = arr[j++];
        }
        //若右边序列还有剩余,则将其全部拷贝进tmp[]中
        while (k <= high) {
            tmp[i++] = arr[k++];
        }
        //将临时数组中的数据覆盖入原数组中
        for (int t = 0; t < i; t++) {
            arr[low + t] = tmp[t];
        }
    }

    public static void mergeSort(int[] arr, int low, int high, int[] tmp) {
        if (low < high) {
            int mid = (low + high) / 2;
            //对左边序列进行归并排序
            mergeSort(arr, low, mid, tmp);
            //对右边序列进行归并排序
            mergeSort(arr, mid + 1, high, tmp);
            //合并两个有序序列
            merge(arr, low, mid, high, tmp);
            for (int a : arr) {
                System.out.print(a + " ");
            }
            System.out.println();
        }
    }

}

算法——归并排序

算法——归并排序

本文地址:https://blog.csdn.net/qq_37598011/article/details/111986865