常用排序算法专题—归并排序

作者: 9f5e612a0d44 | 来源:发表于2019-03-21 17:35 被阅读295次

归并排序

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

  • 基本思路
    分而治之

  在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
  我们可以看到上图中,待排序数组为{4,8,2,7,1,6,3,5},我们先将它们分解成{4,8,2,7}{1,6,3,5}两部分,将这两部分继续分解为{4,8}、{2,7}和{1,6}、{3、5};以此类推,分解的过程完成。接着我们将4,8,2,7,1,6,3,5两两排序合并,变成{4,8}、{2,7}、{1,6}、{3、5},紧接着继续将以上四部分两两排序合并,变成{2,4,7,8}{1,3,5,6},最后再将这两部分排序合并,排序完成。

  • 归并操作
      归并操作需要将两个已经有序的子序列合并成一个有序序列,我们选择图中的{2,4,7,8}{1,3,5,6}为例,它是怎么合并成一个有序数列呢?
      我们先重新申请一个能容纳两个数组归并的空间(命名temp的数组),两个哨兵指针 i 和 j 分别指向两个数组的开头;我们对比两个指针所指向数据的大小,将小的数据移向temp数组,指向该数据的指针向后移动。

注:我们发现 j 指针已经指向结尾,那么把前一个数组的剩余数据按顺序移到temp数组。


  此时两个已经有序的子序列合并成了一个有序序列。

JAVA 代码

package DataStructure;

public class MergeSort {

    public static void sort(int[] arr, int low, int high, int[] temp) {
        if (low < high) {
            int mid = (low + high) / 2;
            sort(arr, low, mid, temp);
            sort(arr, mid + 1, high, temp);
            merge(arr, low, mid, high, temp); // 对两个子数组进行合并操作
        }
    }

    private static void merge(int[] arr, int low, int mid, int high, int[] temp) {
        int tempPoint = 0; // temp数组指针
        int i = low; // i指针
        int j = mid + 1; // j指针

        while (i <= mid && j <= high)
            if (arr[i] <= arr[j])
                temp[tempPoint++] = arr[i++];
            else
                temp[tempPoint++] = arr[j++];

        while (i <= mid)
            temp[tempPoint++] = arr[i++]; // 左边剩余的填充至temp数组中
        while (j <= high)
            temp[tempPoint++] = arr[j++]; // 右边剩余的填充至temp数组中

    
        int t = 0;
        while (low <= high)     // 返回至原数组
            arr[low++] = temp[t++];

    }

    public static void main(String[] args) {
        int[] arr = { 4, 8, 2, 7, 1, 6, 3, 5 };
        int[] temp = new int[arr.length];
        sort(arr, 0, arr.length - 1, temp);
        for (int n : arr)
            System.out.print(n + " ");
    }
}
  • 时间复杂度

  归并排序是稳定排序,它也是一种十分高效的排序,上图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为O(logn)。总平均时间复杂度为O(nlogn)。而且,归并排序的最好、最坏、平均时间复杂度均为O(nlogn)。

相关文章

  • 常用的排序算法

    常用的排序算法 常用的排序算法插入排序折半插入排序shell 排序冒泡排序选择排序快速排序基数排序归并排序堆排序K...

  • 排序算法

    排序算法分类 排序算法常用主要有:冒泡排序法、快速排序法、选择排序法、插入排序法、堆排序法、归并排序法等几种。 ...

  • 程序员应该掌握哪些算法

    程序员必须掌握的常用算法,主要包括以下内容: 算法: 1、排序算法:快速排序、归并排序、计数排序 2、搜索算法:回...

  • 排序算法

    概述 常用排序算法 冒泡排序 插入排序 选择排序 归并排序 快速排序 冒泡排序 步骤 比较相邻元素,如果前面元素比...

  • java实现快速排序、归并排序、希尔排序、基数排序算法...

    快速排序算法 归并排序算法 希尔排序算法 基数排序算法

  • 2018-06-30

    排序算法之归并排序 归并排序算法是排序算法中的经典算法之一,其核心思想是利用归并的思想实现的排序方法,该算法采用经...

  • 八种基本排序算法的使用

    最经典最常用的排序算法有:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序。这些排序算...

  • 常用排序算法专题—归并排序

    归并排序 归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide...

  • 常用排序算法专题—归并排序

    归并排序 归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide...

  • 排序算法之归并排序

    归并排序(Merge Sort) 归并排序是利用归并的思想实现排序的方式,该算法采用的是经典的分治算法 归并排序过...

网友评论

    本文标题:常用排序算法专题—归并排序

    本文链接:https://www.haomeiwen.com/subject/rducvqtx.html