算法排序-归并排序

简介: Java系统提供的Arrays.sort函数。对于基础类型,底层使用快速排序。对于非基础类型,底层使用归并排序。请问是为什么?  答:这是考虑到排序算法的稳定性。

Java系统提供的Arrays.sort函数。对于基础类型,底层使用快速排序。对于非基础类型,底层使用归并排序。请问是为什么?
  答:这是考虑到排序算法的稳定性。对于基础类型,相同值是无差别的,排序前后相同值的相对位置并不重要,所以选择更为高效的快速排序,尽管它是不稳定的排序算法;而对于非基础类型,排序前后相等实例的相对位置不宜改变,所以选择稳定的归并排序。

在JDK的源码中也使用了归并排序,可见归并排序的重要性。我们一起来看看归并排序吧

归并排序

复杂度:
时间复杂度为:O(nlog₂n) 这是该算法中最好、最坏和平均的时间性能。
空间复杂度:O(n)

Java实现

图解

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。


img_dbee27c659a1bd5809275a2154143cb7.png
image.png
img_a29c0dd0186d1f8cef3c5ebdedf3e5a3.gif
image

代码

在比较代码中,我们需要定义三个下标。
分别指向当前数组要比较的左部分下标
分别指向当前数组要比较的右部分下标
当前数组要填充的元素

注意数组的边界。

@Slf4j
public class MergeSort {
    public static void main(String[] args) {
        //可随机生成数组
        int[] a =  {6,202,100,301,38,8,1};
        mergeInternal(a,0,a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }


    /**
     * 对数组进行归并
     *
     * @param arr
     * @param l,数组左边下标
     * @param r 数组右边下标
     */
    public static void mergeInternal(int[] arr,int l,int r){

        if (l >= r){
            //这里可以进行优化,在最后要比较的数组范围较小时候进行插入排序。
            return;
        }

        //两个下标的中间元素
        int mid = (l + r) / 2;

        //递归操作
        mergeInternal(arr, l, mid);
        mergeInternal(arr,mid + 1, r);

        // 当mid < mid+1时,代表已经排序过了
        if (arr[mid] < arr[mid + 1]){
            return;
        }
        
        merge(arr,l,mid,r);

    }

    /**
     *
     * @param arr
     * @param l //左下标
     * @param mid //中间位置
     * @param r 右下标
     */
    private static void merge(int[] arr,int l,int mid,int r) {
        //新建临时数组
        int[] temp = new int[(r - l)+1];

        for (int i = 0; i < temp.length; i++) {
            temp[i] = arr[ l + i ];
        }

        int i = l;
        int j = mid + 1;

        for (int k = l; k <= r; k++) {

            // 当左下标拍完序之后,进行右下标的排序
            if (i > mid){
                arr[ k ] = temp[j - l];
                j++;
            // 有下标全部排序完成                
            }else if (j > r){
                arr[ k ] = temp[i - l];
                i++;
            // 进行比较    
            }else if (temp[i - l ] < temp[j - l]){
                arr[k] = temp[i - l];
                i++;
            }else if (temp[i - l] >= temp[j - l]){
                arr[k] = temp[j - l];
                j++;
            }
        }

    }

}

AI 代码解读

优化部分

  1. 归并排序在进行数组排序之前,判断是否已经左右有序了,比较数组的mid下标与mid+1下标
  2. 在最后数据量分到较小的时候,进行插入排序。

最后

个人觉得归并排序是一个很重要的知识,在数据量足够大的时候进行排序还是要掌握一种高效稳定的排序方法。

目录
打赏
0
0
0
0
1130
分享
相关文章
JavaScript 中通过Array.sort() 实现多字段排序、排序稳定性、随机排序洗牌算法、优化排序性能,JS中排序算法的使用详解(附实际应用代码)
Array.sort() 是一个功能强大的方法,通过自定义的比较函数,可以处理各种复杂的排序逻辑。无论是简单的数字排序,还是多字段、嵌套对象、分组排序等高级应用,Array.sort() 都能胜任。同时,通过性能优化技巧(如映射排序)和结合其他数组方法(如 reduce),Array.sort() 可以用来实现高效的数据处理逻辑。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
JS数组操作方法全景图,全网最全构建完整知识网络!js数组操作方法全集(实现筛选转换、随机排序洗牌算法、复杂数据处理统计等情景详解,附大量源码和易错点解析)
这些方法提供了对数组的全面操作,包括搜索、遍历、转换和聚合等。通过分为原地操作方法、非原地操作方法和其他方法便于您理解和记忆,并熟悉他们各自的使用方法与使用范围。详细的案例与进阶使用,方便您理解数组操作的底层原理。链式调用的几个案例,让您玩转数组操作。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
294 7
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
294 8
|
9月前
|
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
82 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
122 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
200 1
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
157 0
|
9月前
|
深入了解归并排序算法
深入了解归并排序算法
129 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问