归并排序的简单理解

详细描述

归并排序的基本思想是,将已有序的子序列合并,可以得到有序的完整序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

归并排序详细的执行步骤如下:

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

算法图解

归并排序

问题解疑

归并排序和快速排序比较怎么样?

归并排序的比较次数小于快速排序的比较次数,移动次数一般多于快速排序的移动次数。

归并排序的应用在什么场景?

归并排序速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的序列。

归并排序的时间复杂度是多少?

每次合并操作的平均时间复杂度为 \(O(n)\),而完全二叉树的深度为 \(\log_2n\),总的平均时间复杂度为 \(O(n \log n)\)

并且,归并排序的最好、最坏、平均时间复杂度均为 \(O(n \log n)\)

代码实现

package cn.fatedeity.algorithm.sort;

/**
 * 归并排序算法
 */
public class MergeSort {
    private static void merge(int[] numbers, int low, int mid, int high) {
        int i = low;
        int j = mid + 1;
        int[] newNumbers = new int[high - low + 1];
        int k = 0;

        while (i <= mid && j <= high) {
            if (numbers[i] < numbers[j]) {
                newNumbers[k++] = numbers[i++];
            } else if (numbers[i] > numbers[j]) {
                newNumbers[k++] = numbers[j++];
            } else {
                newNumbers[k++] = numbers[i++];
                newNumbers[k++] = numbers[j++];
            }
        }
        while (i <= mid) {
            newNumbers[k++] = numbers[i++];
        }
        while (j <= high) {
            newNumbers[k++] = numbers[j++];
        }

        if (high + 1 - low >= 0) {
            System.arraycopy(newNumbers, 0, numbers, low, high + 1 - low);
        }
    }

    private static int[] sort(int[] numbers, int low, int high) {
        if (low < high) {
            int mid = (low + high) >> 1;
            sort(numbers, low, mid);
            sort(numbers, mid + 1, high);
            merge(numbers, low, mid, high);
        }
        return numbers;
    }

    public static int[] sort(int[] numbers) {
        return sort(numbers, 0, numbers.length - 1);
    }
}

原文连接:https://www.cnblogs.com/fatedeity/p/16407530.html

相关推荐

LeetCode周赛300,差点AK,刚拿到的勋章要丢了……

浅谈JS内存管理和GC算法

「React深入」一文吃透虚拟DOM和diff算法

为什么 React 的 Diff 算法不采用 Vue 的双端对比算法?

链表设计与Java实现,手写LinkedList这也太清楚了吧!!!

ONNX YOLOv6目标检测、GitHub搜索引擎、AI前沿论文 | ShowMeAI资讯日报 #2022.07.03

556. 下一个更大元素 III : 简单构造模拟题

React中的任务调度算法详解

基于SEIR的传播动力学模型

Python实现约瑟夫生者死者游戏可视化(单向循环链表实现)

Web版3D可视化工具,程序员应该知道的97件事,AI前沿论文 | 资讯日报 #2022.07.01

前端解决方案-雪花算法ID传输到前端之后精度丢失的问题

871. 最低加油次数 : 简单优先队列(堆)贪心题

使用简单算法两小时实现猎杀乌姆帕斯(Hunt the Wumpus)Python小游戏

OT算法在协同编辑器中的应用

基于组合优化的旅行商问题

​面试:聊一聊 Java 数组默认的排序算法,我懵了

241. 为运算表达式设计优先级 : DFS 运用题

如何为空间索引创建高效的数据结构?

树的子结构