归并排序的介绍

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间,属于以空间换时间的典型应用。

算法步骤

  • 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
  • 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
  • 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
  • 重复步骤 3 直到某一指针达到序列尾;
  • 将另一序列剩下的所有元素直接复制到合并序列尾。

动画演示

归并排序

代码实现

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[]{5,-4,0,15,7,-3,9,6,22};
        System.out.println(Arrays.toString(arr));
        mergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int i, j, k = 0; // 定义三个变量
        int[] tmp = new int[arr.length]; // 创建一个辅助空间
        for (k = left; k <= right; k++) {
            tmp[k] = arr[k];
        }

        for(i = left, j=mid+1,k=i;i<= mid&& j<= right;k++){
            if(tmp[i]<= tmp[j]){
                arr[k] = tmp[i];
                i++;
            }else{
                arr[k] = tmp[j];
                j++;
            }
        }

        //将剩余元素加入
        while(i<=mid){
            arr[k++] = tmp[i++];
        }

        while(j<=right){
            arr[k++] = tmp[j++];
        }
    }

    public static void mergeSort(int[] arr,int low,int high){
        if(low<high){
            int mid = (low + high) / 2;
            mergeSort(arr, low, mid);
            mergeSort(arr, mid+1, high);
            merge(arr, low, mid, high);
        }
    }
}
Last modification:December 20th, 2020 at 01:35 am
如果觉得我的文章对你有用,请随意赞赏