• 首页 首页 icon
  • 工具库 工具库 icon
    • IP查询 IP查询 icon
  • 内容库 内容库 icon
    • 快讯库 快讯库 icon
    • 精品库 精品库 icon
    • 问答库 问答库 icon
  • 更多 更多 icon
    • 服务条款 服务条款 icon

一天一个经典算法:合并排序算法

武飞扬头像
正经程序员
帮助26

前言

合并排序(归并排序)是一种高效的排序算法,可以产生稳定的排序,这意味着如果两个元素具有相同的值,则它们在排序序列中的相对位置与它们在输入中的相对位置相同。

换句话说,具有相等值的元素的相对顺序保留在排序序列中。合并排序是一种比较排序,这意味着它可以对定义了小于关系的任何输入进行排序。

与快速排序一样,合并排序是一种分治算法。它将输入数组分成两半,为这两半调用自身,然后合并两半。

merge() 函数用于合并两半。merge(arr, l, m, r) 是一个关键过程,它假设 arr[l..m] 和 arr[m 1..r] 已排序,并将两个排序后的子数组合并为一个。

image.png

上图来自维基百科,显示了示例数组 {38、27、43、3、9、82、10} 的完整合并排序过程。如果我们仔细看这个图,我们可以看到数组被递归地分成两半,直到大小变为 1。一旦大小变为 1,合并过程开始动作并开始合并数组,直到完整的数组合并。

Java示例


import java.util.Arrays;
 
class Main
{
    // 合并两个排序的子数组 arr[low … mid]、 arr[mid 1 … high]
    public static void merge(int[] arr, int[] aux, int low, int mid, int high)
    {
        int k = low, i = low, j = mid   1;
 
        while (i <= mid && j <= high)
        {
            if (arr[i] <= arr[j]) {
                aux[k  ] = arr[i  ];
            }
            else {
                aux[k  ] = arr[j  ];
            }
        }
 
        // 复制剩余的元素
        while (i <= mid) {
            aux[k  ] = arr[i  ];
        }
 
        // 无需复制下半部分(因为剩下的项目已在辅助数组中处于正确位置)
        // 复制回原始数组
        for (i = low; i <= high; i  ) {
            arr[i] = aux[i];
        }
    }
 
    // 排序数组 arr[low…high]、 辅助数组 aux
    public static void mergesort(int[] arr, int[] aux, int low, int high)
    {
        if (high == low) {        // if run size == 1
            return;
        }
 
        // 找到中点
        int mid = (low   ((high - low) >> 1));
 
        // 递归地将数组运行分成两半,直到运行大小=1,然后合并它们
        mergesort(arr, aux, low, mid);          // 拆分/合并左半部分
        mergesort(arr, aux, mid   1, high);     // 拆分/合并右半部分
 
        merge(arr, aux, low, mid, high);        // 合并
    }
 
    // 检查arr是否按升序排序
    public static boolean isSorted(int[] arr)
    {
        int prev = arr[0];
        for (int i = 1; i < arr.length; i  )
        {
            if (prev > arr[i])
            {
                System.out.println("MergeSort Fails!!");
                return false;
            }
            prev = arr[i];
        }
 
        return true;
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 12, 3, 18, 24, 0, 5, -2 };
        int[] aux = Arrays.copyOf(arr, arr.length);
        System.out.println("排序前:");
        System.out.println(Arrays.toString(arr)); 
        // 使用辅助数组'aux'对数组'arr'进行排序
        mergesort(arr, aux, 0, arr.length - 1);
 
        if (isSorted(arr)) {
            System.out.println("排序后:");
            System.out.println(Arrays.toString(arr));
        }
    }
}

输出:

排序前 
[12, 3, 18, 24, 0, 5, -2] 
排序后 
[-2, 0, 3, 5, 12, 18, 24]

性能

归并排序的最坏情况时间复杂度是O(n.log(n)),其中n是输入的大小。递归关系为:

T(n) = 2T(n/2) cn = O(n.log(n))

递归基本上总结了合并排序算法 - 对原始列表一半大小的两个列表进行排序,并添加n合并结果两个列表所采取的步骤。

归并排序算法所需的辅助空间是调用堆栈的O(n)。

缺点:

  • 对于较小的任务,与其他排序算法相比速度较慢。
  • 合并排序算法需要额外的 0(n) 内存空间用于临时数组。
  • 即使数组是已经排序过的,也会经历整个过程。

这篇好文章是转载于:学新通技术网

  • 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
  • 本站站名: 学新通技术网
  • 本文地址: /boutique/detail/tanfbeag
系列文章
更多 icon
同类精品
更多 icon
继续加载