当前位置: 首页 > article >正文

十大排序之归并排序(详解)

文章目录

  • 🐒个人主页
  • 🏅算法思维框架
    • 📖前言:
  • 🎀归并排序 时间复杂度O(n*logn)
      • 🎇1. 算法步骤思想
      • 🎇2、动画演示
      • 🎇3.代码实现

🐒个人主页

🏅算法思维框架

📖前言:

本篇博客主要以介绍十大排序算法中的归并排序,有详细的图解、动画演示、良好的代码注释,帮助加深对这些算法的理解,进行查漏补缺~

🎀归并排序 时间复杂度O(n*logn)

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

🎇1. 算法步骤思想

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

🎇2、动画演示

在这里插入图片描述

🎇3.代码实现

  private int[] temp;//帮助两个区间排序
    public  void sort(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        //思路:将数组分为左右区间,分别进行排序,后使用merge()融合
        temp=new int[arr.length];//创建一个辅助数组来帮助各区间排序
        sortDG(arr,0,arr.length-1);
    }
    private void  sortDG(int[] arr,int left,int right){
        if(left==right){
            return;
        }
        int mid=left+(right-left)/2;
        sortDG(arr,0,mid);
        sortDG(arr,mid+1,right);
        //后序位置,进行两个已经排好序的数组的融合操作
        merge(arr,left,mid,right);

    }
    private void merge(int[] arr,int left,int mid,int right){
        for (int i = left; i <=right ; i++) {//先把原数组arr[]中待排序区间【left,right】寄存在temp[]对应区间内
            temp[i]=arr[i];
        }
        //使用双索引将temp[]寄存区间的值进行排序后回填到arr[]的【left,right】区间内
       int index=left;
        int i=left;
        int j=mid+1;
        while (index<=right){
            if(i>mid){
                arr[index++]=temp[j++];
            }else if(j>right){
                arr[index++]=temp[i++];
            }else if(arr[i]<arr[j]){
                arr[index++]=temp[i++];
            }else if(arr[i]>=arr[j]){
                arr[index++]=temp[j++];
            }
        }
    }
原文地址:https://blog.csdn.net/qq_66443592/article/details/134612254
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/145292.html

相关文章:

  • 基于WSL2+Docker+VScode搭建机器学习(深度学习)开发环境
  • 【Linux篇】gdb调试器的使用
  • 扩散模型实战(十二):使用调度器DDIM反转来优化图像编辑
  • C++ Qt QString用法详解与代码演示
  • 基于5G+物联网+SaaS+AI的农业大数据综合解决方案:PPT全文44页,附下载
  • 振弦式土压力计在岩土工程安全监测应用的方案
  • 项目去除git版本控制
  • 云计算学习哪些技术
  • WebGL/threeJS面试题扫描与总结
  • 编译器核心技术概览
  • Vue: Cannot find module @/xx/xx/xx.vue or its corresponding type declarations.
  • 网络运维与网络安全 学习笔记2023.11.26
  • PYTHON+CH347读写25系列flash
  • 鸿蒙4.0开发笔记之ArkTs语言基础与基本组件结构(四)
  • 使用el-scrollbar实现定位滚动,以及el-scrollbar去掉横向滚动条
  • 高并发内存池
  • 详解Rust编程中的生命周期
  • Spring Cache(缓存框架)
  • Spring AOP:什么是AOP? 为什么要用AOP?如何学习AOP?
  • 洛谷P1047题 校门外的树