算法排序-归并排序

简介: 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++;
            }
        }

    }

}

优化部分

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

最后

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

相关文章
|
3月前
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
|
17天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
13 1
|
24天前
|
搜索推荐 Shell
解析排序算法:十大排序方法的工作原理与性能比较
解析排序算法:十大排序方法的工作原理与性能比较
37 9
|
17天前
|
算法 搜索推荐 Java
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
17 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
|
16天前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
27 0
|
20天前
|
存储 搜索推荐 算法
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
|
22天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
55 0
|
24天前
|
搜索推荐 Java Go
深入了解归并排序算法
深入了解归并排序算法
12 0
|
3月前
|
算法 搜索推荐 Java
算法实战:手写归并排序,让复杂排序变简单!
归并排序是一种基于“分治法”的经典算法,通过递归分割和合并数组,实现O(n log n)的高效排序。本文将通过Java手写代码,详细讲解归并排序的原理及实现,帮助你快速掌握这一实用算法。
41 0
|
3月前
|
数据采集 搜索推荐 算法
【高手进阶】Java排序算法:从零到精通——揭秘冒泡、快速、归并排序的原理与实战应用,让你的代码效率飙升!
【8月更文挑战第21天】Java排序算法是编程基础的重要部分,在算法设计与分析及实际开发中不可或缺。本文介绍内部排序算法,包括简单的冒泡排序及其逐步优化至高效的快速排序和稳定的归并排序,并提供了每种算法的Java实现示例。此外,还探讨了排序算法在电子商务、搜索引擎和数据分析等领域的广泛应用,帮助读者更好地理解和应用这些算法。
35 0