059期数据结构与算法四归并排序

2020-08-20 19:21 Java最全面试题库

  点击上方蓝色字体,关注我吧

2020年百日百更原创Java最全面试题库之往期回顾

【000期】Java最全面试题库思维导图

【020期】JavaSE系列面试题汇总(共18篇)

【028期】JavaWeb系列面试题汇总(共10篇)

【042期】JavaEE系列面试题汇总(共13篇)

【049期】数据库系列面试题汇总(共6篇)

【053期】中间件系列面试题汇总(共3篇)

【054期】计算机网络面试题(一)

【055期】计算机网络面试题(二)

【056期】数据结构与算法(一):插入排序

【057期】数据结构与算法(二):交换排序

【058期】数据结构与算法(三):选择排序


开篇介绍

大家好,我是Java最全面试题库提裤姐今天这篇是数据结构与算法那的第四篇,主要总结了归并归并排序相关的问题;在后续,会沿着第一篇开篇的知识线路一直总结下去,做到日更!如果我能做到百日百更,希望你也可以跟着百日百刷,一百天养成一个好习惯。


Q:

归并排序

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

  • 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);

  • 自下而上的迭代

归并排序.png

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

特性:

  • 时间复杂度:O(nlogn)

  • 空间复杂度:O(n)

  • 稳定性:稳定

实现:

public class MergeSort {
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
        return result;
    }
}







“一个专注于分享各类Java面试题的号主,长按二维码关注我吧 ”

祝大家都能拿到心仪的offer!







长按识别二维码

等风也等你



文章都看完了不点个 吗

本文章转载自公众号:tikujie

首页 - Java 相关的更多文章: