C语言简明讲解归并排序的应用
目录
- 一.归并排序
- 1.1归并排序引入
- 1.2归并排序的概念
- 1.3归并排序的原理
- 1.4实例说明
- 1.5具体步骤说明
- 1.6代码实现
- 1.7性能分析
一.归并排序
1.1归并排序引入
对于堆排序来说，因为用到了完全二叉树的深度是（log2n+1）的特性，所以效率就比较高，但是堆结构的设计比较复杂，现在我们想要可以直接利用完全二叉树来排序的方法，这个方法就是归并排序。
1.2归并排序的概念
归并排序是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，最终所有的元素都是有序的。
1.3归并排序的原理
原理：假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子数列，再两两归并，如此重复直到得到一个长度为n的有序序列为止。
1.4实例说明
(1).以4，5，8，1，7，2，6，3为例，排序过程：
(2).以84，9，18，19，48，12，90，84，8，12为例，排序过程：
这里的两两合并指的是两个组合并；
每组的数据单独看是有序的。
1.5具体步骤说明
以实例中的第一个为例：
序列逐层拆分如下：
然后从下往上逐层合并，首先对第一层序列1（只包含元素4）和序列2（只包含元素5）进行合并
创建一个大序列，序列长度为两个小序列长度之和，A、B指针分别指向两个小序列的第一个元素，C指向大序列的第一个元素
比较A、B指向的元素，4小于5，将4填入C指向的元素，C、A往右移一位
此时，序列1已经没有元素，将序列2的元素依次填入大序列中
序列8和1，序列7和2，序列6和3，用同样的方式填入新的序列
接着，以4、5为序列1，1、8为序列2，继续进行合并
创建一个序列长度为4的大序列，A指向序列1的第一个元素4，B指向序列2的第一个元素1，C指向大序列的第一个元素
4和1比较，4大于1，1填入C指向的元素，C、B往右移一位
4和8比较，4小于8，4填入C指向的元素，C、A往右移一位
5和8比较，5小于8，5填入C指向的元素，C、A往右移一位
自此，序列1已经没有元素，将序列2的元素依次填入大序列中
序列2、7和序列3、6以同样的方式合并成新的序列
最后，将序列1、4、5、8和序列2、3、6、7以同样的方式继续合并成新的序列
所有元素均已排好。
1.6代码实现
void MergeSort(int *arr, int len)
{
for(int i=1; i<len; i*=2)// O（logn）
{
Merge(arr, len, i);
}
}
//一次划分函数 核心函数 //返回基准值最终所在下标
int Partition(int *arr, int left, int right)
{
//先讲arr数组里的[left， right]的第一个值 作为基准值
int tmp = arr[left];
while(left < right)
{
while(left<right && arr[right] > tmp)//左右边界没有相遇且当前右边的值大于基准值tmp
right--;
if(left < right)//如果此时，左右边界没有相遇，那就只能证明右边right找到了一个小于等于基准值tmp的值
{
arr[left] = arr[right];
}
else
{
break;
}
while(left<right && arr[left] <= tmp)//左右边界没有相遇且当前左边的值小于等于基准值tmp
left++;
if(left < right)//如果此时，左右边界没有相遇，那就只能证明左边left找到了一个大于基准值tmp的值
{
arr[right] = arr[left];
}
else
{
break;
}
}
arr[left] = tmp;//此时 因为 left == right
return left;//return right ok
}
1.7性能分析
- 时间复杂度：最好，最坏，平均的时间复杂度均为O(nlogn)。
- 空间复杂度：空间复杂度O（n）。
- 稳定性：稳定。
到此这篇关于C语言简明讲解归并排序的应用的文章就介绍到这了,更多相关C语言归并排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
C语言 实现归并排序算法
C语言 实现归并排序算法 归并排序(Merge sort)是创建在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 一个归并排序的例子:对一个随机点的链表进行排序 算法描述 归并操作的过程如下: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针到达序列尾
-
举例讲解C语言对归并排序算法的基础使用
基础概念 百度百科是这么描述归并排序的: 归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作. 设有数列 {6,202,100,301,38,8,1} 初始状态: [6] [202] [100] [301] [38] [8] [1] 比较次数 i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3 i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4 i=3 [ 1 6 8 38 100 202 301 ] 4 总计: 1
-
C语言非递归算法解决快速排序与归并排序产生的栈溢出
目录 1.栈溢出原因和递归的基本认识 2.快速排序(非递归实现) 3.归并排序(非递归实现) 建议还不理解快速排序和归并排序的小伙伴们可以先去看我上一篇博客哦!C语言超详细讲解排序算法下篇 1.栈溢出原因和递归的基本认识 我们先简单来了解下内存分布结构: 栈区:用于存放地址.临时变量等: 堆区:程序运行期间动态分配所使用的场景: 静态区
-
C语言演示对归并排序算法的优化实现
基础 如果有两个数组已经有序,那么可以把这两个数组归并为更大的一个有序数组.归并排序便是建立在这一基础上.要将一个数组排序,可以将它划分为两个子数组分别排序,然后将结果归并,使得整体有序.子数组的排序同样采用这样的方法排序,这个过程是递归的. 下面是示例代码: #include "timsort.h" #include <stdlib.h> #include <string.h> // 将两个长度分别为l1, l2的已排序数组p1, p2合并为一个 // 已排序
-
C语言实现排序算法之归并排序详解
排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序.归并是指将若干个已排序的子文件合并成一个有序的文件. 一.实现原理: 1.算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中. (1)合并过程 合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置.合并时依次比较R[i
-
C语言简明讲解归并排序的应用
目录 一.归并排序 1.1归并排序引入 1.2归并排序的概念 1.3归并排序的原理 1.4实例说明 1.5具体步骤说明 1.6代码实现 1.7性能分析 一.归并排序 1.1归并排序引入 对于堆排序来说,因为用到了完全二叉树的深度是(log2n+1)的特性,所以效率就比较高,但是堆结构的设计比较复杂,现在我们想要可以直接利用完全二叉树来排序的方法,这个方法就是归并排序. 1.2归并排序的概念 归并排序是建立在归并操作上的一种有效的排序算法,归并排序对序列的元素进行逐层折半分组,然后从最小分组开始比
-
C语言简明讲解三目运算符和逗号表达式的使用
目录 一.三目运算符 二.逗号表达式 三.小结 一.三目运算符 三目运算符( a ? b : c)可以作为逻辑运算的载体 规则:当 a 的值为真时,返回 b 的值:否则返回 c 的值 下面看一段代码: #include <stdio.h> int main() { int a = 1; int b = 2; int c = 0; c = a < b ? a : b; (a < b ? a : b) = 3; printf("%d\n", a); printf(&
-
C语言简明讲解队列的实现方法
目录 前言 队列的表示和实现 队列的概念及结构 代码实现 束语 前言 大家好啊,我又双叒叕来水博客了,道路是曲折的,前途是光明的,事物是呈螺旋式上升的,事物最终的发展结果还是我们多多少少能够决定的,好啦,吹水结束,这与这篇博客的主题并没有太多联系.关于栈和队列这一板块本来是想不写(就是想偷懒),但是想了想,觉得这样不太好,关于数据结构这一块可能会有缺失,所以最终还是决定写,必须补齐这一块,恰好最近有时间写博客,所以还是写了,这篇博客将介绍队列的知识点,理解链表那一块的操作后,栈和队列的相关操作还
-
C语言简明讲解类型转换的使用与作用
目录 一.类型之间的转换 二.强制类型转换 三.隐式类型转换 四.表达式中的隐式类型转换 五.小结 一.类型之间的转换 C语言中的数据类型可以进行转换 强制类型转换 隐式类型转换 二.强制类型转换 强制类型转换的语法 (Type)var_name; (Type)value; 强制类型转换的结果 目标类型能够容纳目标值:结果不变 目标类型不能容纳目标值:结果将产生截断 注意:不是所有的强制类型转换都能成功,当不能进行强制类型转换时,编译器将产生错误信息(比如将自定义数据类型转换成基本数据类型).
-
C语言简明讲解操作符++和--的使用方法
目录 一.++与--操作符的本质 二.++与-- 操作符使用分析 三.小结 一.++与--操作符的本质 ++ 和 -- 操作符对应两条汇编指令 前置 变量自增(减)1 取变量值 后置 取变量值 变量自增(减)1 下面看一段神奇的代码: #include <stdio.h> int main() { int i = 0; int r = 0; r = (i++) + (i++) + (i++); printf("i = %d\n", i); printf("r =
-
C语言简明讲解变量的属性
目录 一.C语言中的变量属性 二.auto 关键字 三.register 关键字 四.static 关键字 五.extern 关键字 六.小结 一.C语言中的变量属性 C语言中的变量可以有自己的属性 在定义变量的时候可以加上“属性”关键字 "属性”关键字指明变量的特有意义 语法: property type var_name; 示例: int main() { auto char i; register int j; static long k; extern double m; return
-
C语言简明讲解单引号与双引号的使用
目录 一.单引号和双引号 二.小贴士 三.程序实例分析1 四.程序实例分析2 五.容易混淆的代码 六.小结 一.单引号和双引号 C语言中的单引号用来表示字符字面量 C语言中的双引号用来表示字符串字面量 'a'表示字符字面量,在内存中占1个字节,'a'+1表示'a'的ASCII码加1,结果为'b' "a"表示字符串字面量,在内存中占2个字节,"a"+1表示指针运算,结果指向"a"结束符'\0' 下面看一段单引号和双引号本质的代码: #include
-
C语言简明讲解预编译的使用
目录 小复习 1.内置符号 2.自定义符号 3.自定义宏 4.条件编译 小复习 预处理,预编译是编译的第一步. 会有三件基本的事情发生: 引入#include 去除注释 修改#define 1.内置符号 这些符号都可以直接使用: __FILE__ 点c文件全名__LINE__ 当前行号__DATE__ 编译日期__TIME__ 编译时间 举例: #include<stdio.h> int main() {
-
C语言简明讲解快速排序的应用
目录 快速排序 1.1快速排序引入 1.2快速排序的基本思想 1.3快速排序的排序流程 1.4实例说明 1.5代码实现 1.6性能分析 快速排序 快速排序,说白了就是给基准数据找其正确索引位置的过程 1.1快速排序引入 希尔排序相当于直接插入排序的升级,他们属于插入排序类:堆排序相当于简单选择排序的升级,他们同属于选择排序类:而对于交换排序类的冒泡排序升级版本就是快速排序. 1.2快速排序的基本思想 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字比另一部分记录的关键字小,则可分
-
C语言简明清晰讲解枚举
目录 概述 简单使用 入门 判断 自定义数值 一种不严格的写法 概述 一个类型,值只能是一堆值中的一个. 比如星期几,只会是星期一到星期天. 用数值表示的话就是0到6,但是0到6不太好理解. 而枚举可以用单词表示,提高了可读性. 本质上还是0到6. 简单使用 入门 新建三个变量,值分别为a b c #include<stdio.h> enum Gender { Male, Female, Empty }; int main() { enum Gender a = Male; enum Gend