排序算法-归并排序(含C语言代码示例)

这篇具有很好参考价值的文章主要介绍了排序算法-归并排序(含C语言代码示例)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、算法介绍

        归并排序是一种基于分治思想的经典排序算法,其主要思想是将待排序的数组分割成两个子数组,分别对这两个子数组进行递归排序,然后将排好序的子数组合并起来得到最终有序数组。整个归并排序的过程可以分为三个步骤:分割、排序和合并。

        首先,在分割步骤中,算法将待排序数组递归地分成两半,直到每个子数组的长度为1或0。这一步骤确保了每个子数组都是有序的。

        其次,在排序步骤中,对每一对有序的子数组进行合并排序。这里使用了一个辅助数组来存储排序后的元素,然后将结果复制回原始数组。

        最后,在合并步骤中,将排好序的两个子数组合并成一个有序数组。这一步骤是整个归并排序的关键,通过比较两个子数组的元素大小,并依次合并到辅助数组中,最终得到完全有序的数组。

        归并排序的时间复杂度为O(n log n),其中n是待排序数组的长度。虽然它在时间复杂度上不如快速排序那么优越,但归并排序具有稳定性,且对于链表等非连续存储结构也适用,因此在实际应用中具有一定的优势。文章来源地址https://www.toymoban.com/news/detail-795524.html

二、代码示例

int min(int a, int b) {
    return a < b ? a : b;
}
void merge_sort(int index[], int len) {
    int *a = index;
    int *b = (int *) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg * 2) {
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != index) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

到了这里,关于排序算法-归并排序(含C语言代码示例)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构和算法笔记4:排序算法-归并排序

    归并排序算法完全遵循分治模式。直观上其操作如下: 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列。 解决:使用归并排序递归地排序两个子序列。 合并:合并两个已排序的子序列以产生已排序的答案。 我们直接来看例子理解算法的过程,下面是要排序

    2024年01月21日
    浏览(64)
  • 数据结构与算法—归并排序&计数排序

    目录 一、归并排序 1、主函数 2、递归实现 3、优化递归  4、非递归实现 5、特性总结: 二、计数排序 1、代码: 2、特性总结: 三、各种排序总结 时间空间复杂度汇总  基本思想: 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用 分治法 的一个非常典型的

    2024年02月04日
    浏览(48)
  • 数据结构算法--5 归并排序

    我们先看一下归并排序是怎么归并的  两个有序列表,有low指针指向2,high指针指向6,mid指针指向9 再建一个新列表,12,所以1放到列表,右指针右移一位,再比较2和3,2放入列表,左指针右移一位,以此类推,肯定有一部分列表率先没有数,这时将另一列表直接append进入新

    2024年02月11日
    浏览(48)
  • 数据结构与算法:归并排序

    在讲解归并排序前,我们先看到一个问题: 对于这样两个有序的数组,如何将它们合并为一个有序的数组? 在此我们处理这个问题的思路就是:开辟一个新的数组,然后分别安置一个指针在左右数组,利用指针遍历数组,每次对比将比较小的那个元素插入到数组的尾部。 像

    2024年01月21日
    浏览(46)
  • 【C语言】数据结构——排序三(归并与计数排序)

    💗个人主页💗 ⭐个人专栏——数据结构学习⭐ 💫点击关注🤩一起学习C语言💯💫 我们在前面学习了排序,包括直接插入排序,希尔排序,选择排序,堆排序,冒泡排序和快排。 今天我们来讲一讲归并排序和计数排序。 关注博主或是订阅专栏,掌握第一消息。 归并排序的

    2024年01月19日
    浏览(58)
  • python算法与数据结构---排序和归并排序

    掌握归并排序的基本原理 使用python语言解答归并排序题目 原理及过程 将两个有序的数组合并成一个有序数组称为 从上往下分解:把当前区间一分为二,直至分解为若干个长度为1的子数组 从上往下的合并:两个有序的子区域两两向上合并; 体现了分治思想,稳定排序 复杂

    2024年01月21日
    浏览(72)
  • 【数据结构】排序算法(二)—>冒泡排序、快速排序、归并排序、计数排序

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.冒泡排序 2.快速排序 2.1Hoare版 2.2占坑版 2.3前后指针版 2.4三数取中对快速排序的优化 2.5非递归版 3.归

    2024年02月08日
    浏览(54)
  • 【数据结构与算法】:非递归实现快速排序、归并排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 上篇文章我们详细讲解了递归版本的快速排序,本篇我们来探究非递归实现快速排序和归并排序 快速排序的非递归实现主要依赖于栈(stack)来模拟递归过程中的函数调用栈。递归版本的快速排序通过递归调用自身来处理子

    2024年03月24日
    浏览(55)
  • [数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

    目录 1、归并的思想 2、归并排序的思想 2.1 基本思想 2.2 图解分析 3、归并排序递归版本代码实现 3.1 代码解析 3.2 注意事项 3.2.1错误划分:[begin, mid-1],[mid, end] 3.2.2 正确划分:[begin, mid], [mid+1, end] 4、归并排序的测试 5、时间复杂度、空间复杂度分析 5.1 时间复杂度 5.2 空间复杂

    2024年02月16日
    浏览(50)
  • 【数据结构】—超级详细的归并排序(含C语言实现)

    ​                                         食用指南:本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了: C语言                                        ♈️ 今日夜电波:斜陽—ヨルシカ            

    2024年02月08日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包