Home 算法 归并排序(Merge Sort)

归并排序(Merge Sort)

0 74

5、归并排序(Merge Sort)

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

5.1 算法描述

  • 把长度为n的输入序列分成两个长度为n/2的子序列;
  • 对这两个子序列分别采用归并排序;
  • 将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

 

import java.util.Arrays;
import java.util.Random;

/**
 * @Author Chengzhi
 * @Date 2021/9/5 10:03
 * @Version 1.0
 *
 * 归并排序
 */
public class MergeSort {

    public static void main(String[] args) {
        //生成随机数组
        Random rd = new Random();
        int[] num = new int[10];
        for (int i = 0; i < 10; i++) {
            num[i] = rd.nextInt(100) + 1;
        }
        System.out.println(Arrays.toString(num));
        //进行归并排序
        mergeSort(num, 0, num.length-1);
        System.out.println(Arrays.toString(num));
    }

    private static void mergeSort(int[] num, int left, int right) {
        if (left >= right) {//递归终止条件
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(num, left, mid);//排序左序列
        mergeSort(num, mid + 1, right);//排序右序列
        merge(num, left, mid, right); //将左右两部分,利用临时数组进行归并
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] aux = new int[right - left + 1]; //临时辅助数组
        for (int i = left; i <= right; i++)
            aux[i - left] = arr[i]; /*减去的left是原数组相对于临时数组的偏移量*/

        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++) {
            if (i > mid) { //检查左下标是否越界
                arr[k] = aux[j - left];
                j++;
            } else if (j > right) { //检查右下标是否越界
                arr[k] = aux[i - left];
                i++;
            } else if (aux[i - left] <= aux[j - left]) {
                arr[k] = aux[i - left];
                i++;
            } else {
                arr[k] = aux[j - left];
                j++;
            }
        }
    }
}

SIMILAR ARTICLES

发表评论

发表评论