0基础学C#笔记10:归并排序法

这篇具有很好参考价值的文章主要介绍了0基础学C#笔记10:归并排序法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

将一个大的无序数组有序,我们可以把大的数组分成两个,然后对这两个数组分别进行排序,之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的,所以在合并的时候是很快的。


一、递归的方式

通过递归的方式将大的数组一直分割,直到数组的大小为 1,此时只有一个元素,那么该数组就是有序的了,之后再把两个数组大小为1的合并成一个大小为2的,再把两个大小为2的合并成4的 …… 直到全部小的数组合并起来。

为方便理解我还准备了动图:
0基础学C#笔记10:归并排序法,0基础学习C#笔记,c#,笔记,排序算法

二、代码

public class MergeSort {
    // 归并排序
    public static int[] mergeSort(int[] arr, int left, int right) {
        // 如果 left == right,表示数组只有一个元素,则不用递归排序
        if (left < right) {
            // 把大的数组分隔成两个数组
            int mid = (left + right) / 2;
            // 对左半部分进行排序
            arr = mergeSort(arr, left, mid);
            // 对右半部分进行排序
            arr = mergeSort(arr, mid + 1, right);
            //进行合并
            merge(arr, left, mid, right);
        }
        return arr;
    }

    // 合并函数,把两个有序的数组合并起来
    // arr[left..mif]表示一个数组,arr[mid+1 .. right]表示一个数组
    private static void merge(int[] arr, int left, int mid, int right) {
        //先用一个临时数组把他们合并汇总起来
        int[] a = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                a[k++] = arr[i++];
            } else {
                a[k++] = arr[j++];
            }
        }
        while(i <= mid) a[k++] = arr[i++];
        while(j <= right) a[k++] = arr[j++];
        // 把临时数组复制到原数组
        for (i = 0; i < k; i++) {
            arr[left++] = a[i];
        }
    }
}

然而面试官要你写个非递归式的归并排序怎么办?别怕,我这还撸了个非递归式的归并排序,代码如下:

public class MergeSort {
    // 非递归式的归并排序
    public static int[] mergeSort(int[] arr) {
        int n = arr.length;
        // 子数组的大小分别为1,2,4,8...
        // 刚开始合并的数组大小是1,接着是2,接着4....
        for (int i = 1; i < n; i += i) {
            //进行数组进行划分
            int left = 0;
            int mid = left + i - 1;
            int right = mid + i;
            //进行合并,对数组大小为 i 的数组进行两两合并
            while (right < n) {
                // 合并函数和递归式的合并函数一样
                merge(arr, left, mid, right);
                left = right + 1;
                mid = left + i - 1;
                right = mid + i;
            }
            // 还有一些被遗漏的数组没合并,千万别忘了
            // 因为不可能每个字数组的大小都刚好为 i
            if (left < n && mid < n) {
                merge(arr, left, mid, n - 1);
            }
        }
        return arr;
    }
}

总结

性质:
1、时间复杂度:O(nlogn)
2、空间复杂度:O(n)
3、稳定排序
4、非原地排序文章来源地址https://www.toymoban.com/news/detail-639379.html

到了这里,关于0基础学C#笔记10:归并排序法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C#,归并排序算法(Merge Sort Algorithm)的源代码及数据可视化

    归并算法采用非常经典的 分治策略 ,每次把序列分成n/2的长度,将问题分解成小问题,由复杂变简单。 因为使用了递归算法,不能用于大数据的排序。 核心代码: using System; using System.Text; using System.Collections.Generic; using System.Windows.Forms; namespace WindowsFormsApp6 {     public parti

    2024年02月02日
    浏览(59)
  • 【基础算法】八大排序算法:直接插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序(快排),归并排序,计数排序

      🧑‍🎓 个人主页:简 料   🏆 所属专栏:C++   🏆 个人社区:越努力越幸运社区   🏆 简       介: 简料简料,简单有料~在校大学生一枚,专注C/C++/GO的干货分享,立志成为您的好帮手 ~ C/C++学习路线 (点击解锁) ❤️ C语言阶段(已结束) ❤️ 数据结构与算法(ing) ❤

    2024年02月01日
    浏览(45)
  • 算法基础学习笔记——①排序

    ✨ 博主:命运之光 ✨ 专栏: 算法基础学习 前言: 算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,感谢大家的支持! 因为x参与交换之后仍然会被留在左右区间中的一个里。 1.确定分界点:(这里的分界点不一定是x,可以随意取值,常用取值方法如下) q[l],q[(l+r)/2],q[r],随机

    2024年02月07日
    浏览(46)
  • 【数据结构与算法】归并排序详解:归并排序算法,归并排序非递归实现

    归并排序是一种经典的排序算法,它使用了分治法的思想。下面是归并排序的算法思想: 递归地将数组划分成较小的子数组,直到每个子数组的长度为1或者0。 将相邻的子数组合并,形成更大的已排序的数组,直到最终得到一个完全排序的数组。 归并排序的过程可以分为三

    2024年01月22日
    浏览(67)
  • 考研算法31天:归并排序 【归并排序,分治】

    算法介绍 归并算法其过程分为三步: 1.分:递归到最下面 2.治:两个元素之间排序。 3。归:递归到最下层然后返回,从两个元素变成四个元素再排序。 如下图所示: 动态图如下: 算法题目 算法ac代码:

    2024年02月11日
    浏览(39)
  • 0基础学C#笔记09:希尔排序法

    希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序,如果数组的最大值刚好是在第一位,要将它挪到正确的位置就需要 n - 1 次移动。也就是说,原数组的一个元素如果距离它正确的位置很远的话,则需要与相邻元素交换很多次才能到达正确的位置,这样是

    2024年02月13日
    浏览(36)
  • 【排序算法】归并排序与快速排序

           🔥🔥 欢迎来到小林的博客!!       🛰️博客主页:✈️小林爱敲代码       🛰️博客专栏:✈️ 算法训练笔记       🛰️社区 :✈️ 进步学堂       🛰️欢迎关注:👍点赞🙌收藏✍️留言 今天给大家分享两种排序,一种是

    2024年01月19日
    浏览(38)
  • 【算法】排序——归并排序和计数排序

     ========================================================================= 主页点击直达:个人主页 我的小仓库:代码仓库 C语言偷着笑:C语言专栏 数据结构挨打小记: 初阶数据结构专栏 Linux被操作记: Linux专栏 LeetCode刷题掉发记: LeetCode刷题 算法头疼记: 算法专栏  ========================

    2024年02月08日
    浏览(34)
  • 【初阶算法4】——归并排序的详解,及其归并排序的扩展

    目录 前言 学习目标: 学习内容: 一、介绍归并排序 1.1 归并排序的思路 1.2 归并排序的代码 1.2.1 mergesort函数部分  1.2.2 process函数部分  1.2.3 merge函数部分  二、AC两道经典的OJ题目 题目一:逆序对问题 题目二:小和问题  三、练习一道LeetCode的题目 四、总结在什么情况下使

    2024年02月08日
    浏览(40)
  • 归并排序--排序算法

    归并排序和快速排序一样,都是基于分治思想的应用。 通过递归,不断将原数列分为两个数列,然后再分别使其有序,最后通过归并将两个有序子数列合并为新的有序数列。 值得注意的是,与快速排序不同,归并排序是稳定的。 和快速排序先排序后递归不同,归并排序是先

    2024年02月06日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包