玩数据结构和算法-实现自己的归并排序

news/2024/5/17 20:14:05 标签: 归并排序, 数据结构算法

文章目录

归并排序的实现原理和动画可以网上找

归并排序实现

import java.util.*;

public class MergeSort {

    // 我们的算法类不允许产生任何实例
    private MergeSort() {
    }

    // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
    private static void merge(Comparable[] arr, int l, int mid, int r) {

        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);

        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {

            if (i > mid) {  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {   // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l].compareTo(aux[j - l]) < 0) {  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i - l];
                i++;
            } else {  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    // 递归使用归并排序,对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr, int l, int r) {

        if (l >= r)
            return;

        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public static void sort(Comparable[] arr) {

        int n = arr.length;
        sort(arr, 0, n - 1);
    }

    // 测试MergeSort
    public static void main(String[] args) {

        // Merge Sort是我们学习的第一个O(nlogn)复杂度的算法
        // 可以在1秒之内轻松处理100万数量级的数据
        // 注意：不要轻易尝试使用SelectionSort, InsertionSort或者BubbleSort处理100万级的数据
        // 否则，你就见识了O(n^2)的算法和O(nlogn)算法的本质差异：）
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("C03_Sorting_Advance.S02_Merge_Sort.MergeSort", arr);

        return;
    }
}

归并排序和插入排序的性能比较

import java.util.Arrays;

public class Main {

    // 比较InsertionSort和MergeSort两种排序算法的性能效率
    // 整体而言, MergeSort的性能最优, 对于近乎有序的数组的特殊情况, 见测试2的详细注释
    public static void main(String[] args) {

        int N = 50000;

        // 测试1 一般测试
        System.out.println("Test for random array, size = " + N + " , random range [0, " + N + "]");

        Integer[] arr1 = SortTestHelper.generateRandomArray(N, 0, N);
        Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);

        SortTestHelper.testSort("C03_Sorting_Advance.S02_Merge_Sort.InsertionSort", arr1);
        SortTestHelper.testSort("C03_Sorting_Advance.S02_Merge_Sort.MergeSort", arr2);

        System.out.println();


        // 测试2 测试近乎有序的数组
        // 对于近乎有序的数组, 数组越有序, InsertionSort的时间性能越趋近于O(n)
        // 所以可以尝试, 当swapTimes比较大时, MergeSort更快
        // 但是当swapTimes小到一定程度, InsertionSort变得比MergeSort快
        int swapTimes = 10;
        assert swapTimes >= 0;

        System.out.println("Test for nearly ordered array, size = " + N + " , swap time = " + swapTimes);

        arr1 = SortTestHelper.generateNearlyOrderedArray(N, swapTimes);
        arr2 = Arrays.copyOf(arr1, arr1.length);

        SortTestHelper.testSort("C03_Sorting_Advance.S02_Merge_Sort.InsertionSort", arr1);
        SortTestHelper.testSort("C03_Sorting_Advance.S02_Merge_Sort.MergeSort", arr2);

        return;
    }
}

在这里插入图片描述
对随机数组的排序，归并排序远远快于插入排序；当然对有序数组的排序，插入排序快于归并排序，因为对有序数组的排序，插入排序的时间复杂度转变为O(n)。

归并排序改进

优化1: 对于arr[mid] <= arr[mid+1]的情况,不进行merge
优化2: 对于小规模数组, 使用插入排序。因为当元素少到一定程度的时候，插入排序的性能高于插入排序

在这里插入图片描述

贴上插入排序的代码

    // 对arr[l...r]的区间使用InsertionSort排序
    public static void sort(Comparable[] arr, int l, int r){

        for( int i = l + 1 ; i <= r ; i ++ ){
            Comparable e = arr[i];
            int j = i;
            for( ; j > l && arr[j-1].compareTo(e) > 0 ; j--)
                arr[j] = arr[j-1];
            arr[j] = e;
        }
    }

再次性能比较

public class Main {

    // 比较InsertionSort和MergeSort两种排序算法的性能效率
    // 整体而言, MergeSort的性能最优, 对于近乎有序的数组的特殊情况, 见测试2的详细注释
    public static void main(String[] args) {

        int N = 50000;

        // 测试1 一般测试
        System.out.println("Test for random array, size = " + N + " , random range [0, " + N + "]");

        Integer[] arr1 = SortTestHelper.generateRandomArray(N, 0, N);
        Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
        Integer[] arr3 = Arrays.copyOf(arr1, arr1.length);

        SortTestHelper.testSort("C03_Sorting_Advance.S03_Merge_Sort_Advance.InsertionSort", arr1);
        SortTestHelper.testSort("C03_Sorting_Advance.S03_Merge_Sort_Advance.MergeSort", arr2);
        SortTestHelper.testSort("C03_Sorting_Advance.S03_Merge_Sort_Advance.MergeSort2", arr3);

        System.out.println();


        // 测试2 测试近乎有序的数组
        int swapTimes = 10;
        assert swapTimes >= 0;

        System.out.println("Test for nearly ordered array, size = " + N + " , swap time = " + swapTimes);

        arr1 = SortTestHelper.generateNearlyOrderedArray(N, swapTimes);
        arr2 = Arrays.copyOf(arr1, arr1.length);
        arr3 = Arrays.copyOf(arr1, arr1.length);

        SortTestHelper.testSort("C03_Sorting_Advance.S03_Merge_Sort_Advance.InsertionSort", arr1);
        SortTestHelper.testSort("C03_Sorting_Advance.S03_Merge_Sort_Advance.MergeSort", arr2);
        SortTestHelper.testSort("C03_Sorting_Advance.S03_Merge_Sort_Advance.MergeSort2", arr3);

        return;
    }
}

在这里插入图片描述
从结果可以看出归并排序优化后的性能好于优化前

自底向上的归并排序

import java.util.*;

public class MergeSortBU {

    // 我们的算法类不允许产生任何实例
    private MergeSortBU() {
    }

    // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
    private static void merge(Comparable[] arr, int l, int mid, int r) {

        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);

        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {

            if (i > mid) {  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {   // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l].compareTo(aux[j - l]) < 0) {  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i - l];
                i++;
            } else {  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    //没有使用数组一个重要特性（通过索引获取元素），所以可以自底向上的归并排序可以很好的使用O(NlogN)的时间复杂度对链表进行排序。
    public static void sort(Comparable[] arr) {

        int n = arr.length;

        // Merge Sort Bottom Up 无优化版本
//        for (int sz = 1; sz < n; sz *= 2)
//            for (int i = 0; i < n - sz; i += sz+sz)
//                // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
//                merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1));

        // Merge Sort Bottom Up 优化
        // 对于小数组, 使用插入排序优化
        for (int i = 0; i < n; i += 16)
            InsertionSort.sort(arr, i, Math.min(i + 15, n - 1));

        for (int sz = 16; sz < n; sz += sz)
            for (int i = 0; i < n - sz; i += sz + sz)
                // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
                if (arr[i + sz - 1].compareTo(arr[i + sz]) > 0)
                    merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1));

    }

    // 测试 MergeSort BU
    public static void main(String[] args) {

        // Merge Sort BU 也是一个O(nlogn)复杂度的算法，虽然只使用两重for循环
        // 所以，Merge Sort BU也可以在1秒之内轻松处理100万数量级的数据
        // 注意：不要轻易根据循环层数来判断算法的复杂度，Merge Sort BU就是一个反例
        // 关于这部分陷阱，推荐看我的《玩转算法面试》课程，第二章：《面试中的复杂度分析》：）
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("C03_Sorting_Advance.S04_Merge_Sort_Bottom_Up.MergeSortBU", arr);

        return;
    }
}

两种归并排序的性能比较

public class Main {

    // 比较Merge Sort和Merge Sort Bottom Up两种排序算法的性能效率
    // 整体而言, 两种算法的效率是差不多的。但是如果进行仔细测试, 自底向上的归并排序会略胜一筹。
    // 更详细的测试, 可以参考课程的这个问题: http://coding.imooc.com/learn/questiondetail/3208.html
    // 本章节的代码仓也会给出更详细的测试代码
    public static void main(String[] args) {

        int N = 1000000;

        // 测试1 一般测试
        System.out.println("Test for random array, size = " + N + " , random range [0, " + N + "]");

        Integer[] arr1 = SortTestHelper.generateRandomArray(N, 0, N);
        Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);

        SortTestHelper.testSort("C03_Sorting_Advance.S04_Merge_Sort_Bottom_Up.MergeSort", arr1);
        SortTestHelper.testSort("C03_Sorting_Advance.S04_Merge_Sort_Bottom_Up.MergeSortBU", arr2);

        System.out.println();


        // 测试2 测试近乎有序的数组
        int swapTimes = 10;
        assert swapTimes >= 0;

        System.out.println("Test for nearly ordered array, size = " + N + " , swap time = " + swapTimes);

        arr1 = SortTestHelper.generateNearlyOrderedArray(N, swapTimes);
        arr2 = Arrays.copyOf(arr1, arr1.length);

        SortTestHelper.testSort("C03_Sorting_Advance.S04_Merge_Sort_Bottom_Up.MergeSort", arr1);
        SortTestHelper.testSort("C03_Sorting_Advance.S04_Merge_Sort_Bottom_Up.MergeSortBU", arr2);

        return;
    }
}

在这里插入图片描述

性能上并没有很大的区别。

自底向上的归并排序：没有使用数组一个重要特性（通过索引获取元素），所以自底向上的归并排序可以很好的使用O(NlogN)的时间复杂度对链表进行排序。


http://www.niftyadmin.cn/n/1837356.html

相关文章

文件传输(二)---断点续传

文件传输(二)---断点续传

.NET的类库中有一些操作FTP的类&#xff0c;不过用起来都没不是很直观&#xff0c;需要一些封装才比较好用&#xff0c;在sourceforge上找到一个人写的FTPClient&#xff0c;这个类对.NET的类库System.Net.Sockets进行了一定的封装&#xff0c;主要是使用了其中的类TcpClient&a…
阅读更多...
java中this可以出现在任何方法中吗_在Java中，“this”可以为null吗？

java中this可以出现在任何方法中吗_在Java中，“this”可以为null吗？

一个正常的this在真正的Java代码1中永远不能为null &#xff0c;你的例子使用正常的this 。 有关更多详细信息&#xff0c;请参阅其他答案。一个合格的this 不应该是null &#xff0c;但是有可能打破这个。 考虑以下几点&#xff1a;public class Outer { public Outer() {} pu…
阅读更多...
Visual Studio 2008 debug的时候发生郁闷的错误ContextSwitchDeadlock was detected

Visual Studio 2008 debug的时候发生郁闷的错误ContextSwitchDeadlock was detected

异常信息&#xff1a; CLR 无法从 COM 上下文 0x645e18 转换为 COM 上下文 0x645f88&#xff0c;这种状态已持续 60 秒。拥有目标上下文/单元的线程很有可能执行的是非泵式等待或者在不发送 Windows 消息的情况下处理一个运行时间非常长的操作。这种情况通常会影响到性能&#…
阅读更多...
██mips指令之jump,branch

██mips指令之jump,branch

jump和branch指令的相同之处就是都跟当前pc相关&#xff0c;是一个相对的跳转。如果要实现绝对地址跳转则要用jr指令&#xff0c;jr可跳至2G的地址范围。转载于:https://www.cnblogs.com/beinghu2/archive/2009/11/21/1607749.html
阅读更多...
工作一年半记录

工作一年半记录

大家好&#xff0c;好久没有更新博客了&#xff0c;工作挺多的&#xff0c;而且休息的时候现在更愿意花时间去外面跟朋友面对面聊天&#xff0c;所以不常更新博客了。回想去年7月从大学毕业到现在&#xff0c;也有一年半了&#xff0c;毕业后来到上海&#xff0c;这个纷繁的城市…
阅读更多...
Android开发中MVC、MVP到MVVM演化

Android开发中MVC、MVP到MVVM演化

文章目录一般模式activity_normal.xmlNormalActivityAccountMCallbackMVCMVC简介MVC各层功能MVCModelMVCActivity优缺点MVP简介V层IMVPViewMVPActivityM层P层优缺点使用建议MVVM简介MVVMModelMVVMViewModel布局文件MVVMActivity优缺点总结有一个需求&#xff1a;需要查询用户账…
阅读更多...
C#--理解Thread.Sleep函数

C#--理解Thread.Sleep函数

C#--理解Thread.Sleep函数我们可能经常会用到 Thread.Sleep 函数来使线程挂起一段时间。那么你有没有正确的理解这个函数的用法呢&#xff1f;思考下面这两个问题&#xff1a; 1、假设现在是 2008-4-7 12:00:00.000&#xff0c;如果我调用一下 Thread.Sleep(1000) &#xff0c;…
阅读更多...
Android性能优化之SparseArray

Android性能优化之SparseArray

文章目录什么是性能优化&#xff1f;几种数据结构比较线性数据结构顺序表与链表Hash表HashMapSparseArrayHashMap 与 SparseArrayHashMap 和 SparseArray性能对比内存时间什么是性能优化&#xff1f; 一款app除了要有令人惊叹的功能和令人发指交互之外&#xff0c;在性能上也应…
阅读更多...
最新文章

Copyright @ 2022~2023