精华内容
下载资源
问答
  • 二路归并排序
    2022-03-27 09:34:14

    原理

    图解:一颗二叉树,叶子结点为单个记录,到最后1层后开始两两合并
    在这里插入图片描述

    介绍
    二路归并排序

    1. 子序列长度从1到n/2(把数组划分为2个子序列)
    2. 从左往右一次比较2个子序列

    非递归实现

    1. 子序列长度,h从1开始到?,作2倍变化2h
    2. 子序列个数,根据剩余子序列的个数执行相应的操作(剩余子序列个数大于2;剩余子序列个数大于1小于2;剩余子序列个数小于1)
    3. 记录个数,根据子序列中记录个数执行相应的操作(两个子序列中都有记录;子序列1中还有记录;子序列2中还有记录)

    递归实现:使用递归控制子序列的长度和个数

    • 记录个数,根据子序列中记录个数执行相应的操作(两个子序列中都有记录;子序列1中还有记录;子序列2中还有记录)

    时间复杂度(非递归): n l o g 2 n nlog_2n nlog2n

    • 一趟归并排序需要将待排序序列扫描一遍
    • 2路归并需要进行 l o g 2 n log_2n log2n趟(一颗二叉树)

    空间复杂度(非递归): O ( n ) O(n) O(n)

    • 需要1个和待排序数组同样长的数字作为临时存储空间

    稳定性(非递归):稳定,两个子序列相互比较不改变相对次序

    时间复杂度(递归): n l o g 2 n nlog_2n nlog2n

    • 一趟归并排序需要将待排序序列扫描一遍
    • 2路归并需要进行 l o g 2 n log_2n log2n趟(递归的深度)

    空间复杂度(递归): O ( n ) O(n) O(n)

    • 需要1个和待排序数组同样长的数字作为临时存储空间
    • 压栈 l o g 2 n log_2n log2n

    稳定性(递归):稳定,两个子序列相互比较不改变相对次序

    代码

    package cn.xcrj.data_structure;
    
    import java.util.Scanner;
    
    /**
     * 二路归并排序:
     * 1. 子序列长度从1到n/2(把数组划分为2个子序列)
     * 2. 从左往右一次比较2个子序列
     * <p>
     * <p>
     * 非递归实现
     * 1. 子序列长度,h从1开始到?,作2倍变化2h
     * 2. 子序列个数,根据剩余子序列的个数执行相应的操作
     * 3. 记录个数,根据子序列中记录个数执行相应的操作
     * <p>
     * 递归实现:使用递归控制子序列的长度和个数
     * 1. 记录个数,根据子序列中记录个数执行相应的操作
     */
    public class Way2MergeSort {
        /**
         * 二路归并非递归实现
         *
         * @param r 输入数组
         */
        public static void way2MergeSortG(int[] r) {
            // 实际记录个数
            int n = r.length;
            // 临时数组-目标数组
            int[] r1 = new int[n];
            // 1. 子序列长度
            // 初始子序列长度
            int h = 1;
            // r和r1交替作为归并结果存储空间,最终的结果在r中
            while (h < n) {
                mergePass(r, r1, h, n);
                // 子序列长度变为原来的2倍
                h *= 2;
            }
        }
    
        /**
         * 二路归并递归实现
         *
         * @param rs source 数组
         * @param rd dest 数组
         * @param s  子序列开始位置,包括
         * @param e  子序列结束位置,不包括
         */
        public static void way2MergeSortR(int[] rs, int[] rd, int s, int e) {
            // e-1因为前包后不包
            if (s < e - 1) {
                // 继续往下两两划分
                int m = (s + e) / 2;
                way2MergeSortR(rs, rd, s, m);
                way2MergeSortR(rs, rd, m, e);
                merge(rs, rd, s, m, m, e);
            }
        }
    
        /**
         * 2. 子序列个数
         */
        public static void mergePass(int[] rs, int[] rd, int h, int n) {
            int i = 0;
            // 剩余子序列个数大于2
            while (i < n - 2 * h) {
                // 开始2路归并
                merge(rs, rd, i, i + h, i + h, i + 2 * h);
                i += 2 * h;
            }
            // 剩余子序列个数大于1小于2
            if (i < n - h) {
                merge(rs, rd, i, i + h, i + h, n);
                i += 2 * h;
            }
            // 剩余子序列个数小于1
            for (; i < n; i++) rd[i] = rs[i];
        }
    
        /**
         * 2. 元素个数,开始2路归并
         *
         * @param rs source 数组
         * @param rd dest 数组
         * @param s1 第1个子序列开始位置,包括
         * @param s2 第2个子序列开始位置,包括
         * @param e1 第1个子序列结束位置,不包括
         * @param e2 第2个子序列结束位置,不包括
         */
        public static void merge(int[] rs, int[] rd, int s1, int s2, int e1, int e2) {
            int i1 = s1;
            int i2 = s2;
            int k = s1;
            // 两个子序列中都有记录
            while (i1 < e1 && i2 < e2) {
                // 把小的记录放到rd中
                if (rs[i1] <= rs[i2]) rd[k++] = rs[i1++];
                else rd[k++] = rs[i2++];
            }
    
            // 子序列1中还有记录
            while (i1 < e1) rd[k++] = rs[i1++];
            // 子序列2中还有记录
            while (i2 < e2) rd[k++] = rs[i2++];
            // 将rd中排序好的结果放回rs,s1 < k因为k从s1开始即rd中已经有序的记录从s1开始到k(不包括)
            for (; s1 < k; s1++) rs[s1] = rd[s1];
        }
    
        public static void main(String[] args) {
            // 数组录入
            System.out.println("请以空格隔开输入1个数组序列:");
            System.out.println("示例:2 1 5 7 2 6");
            Scanner s = new Scanner(System.in);
            String inputStr = s.nextLine();
            String[] strArray = inputStr.split(" ");
            int[] r = new int[strArray.length];
            for (int i = 0; i < r.length; i++) {
                r[i] = Integer.parseInt(strArray[i]);
            }
            System.out.print("输入序列为:");
            for (int i = 0; i < r.length; i++) {
                System.out.print(" " + r[i]);
            }
            System.out.println();
    
            // 调用非递归排序
            way2MergeSortG(r);
            // 调用递归排序
    //        int[] rd = new int[r.length];
    //        way2MergeSortR(r, rd, 0, r.length);
    
            // 输出排序好的序列
            System.out.print("排序后序列为:");
            for (int i = 0; i < r.length; i++) {
                System.out.print(" " + r[i]);
            }
        }
    }
    
    
    更多相关内容
  • 主要介绍了c++实现二路归并排序的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • 主要介绍了java二路归并排序示例,需要的朋友可以参考下
  • 二路归并模式:每次仅作两个文件的归并;当有多个文件时,采用两两归并的模式,最终得到一个完整的记录文件。 二元归并树:二路归并模式的归并过程可以用一个二元树的形式描述,称之为二元归并树。 贪心求解: 任意...
  • 二路归并排序

    千次阅读 2019-08-31 15:36:22
    归并排序主要运用了"分治算法",就是将一个大的问题划分为n个规模较小而结构相似的子问题,子问题的解决办法都是相似的,分别解决这些子问题,然后归并子问题的结果,得到大问题的解。 归并排序的主旨就是分解 ,...

    归并排序主要运用了"分治算法",就是将一个大的问题划分为n个规模较小而结构相似的子问题,子问题的解决办法都是相似的,分别解决这些子问题,然后归并子问题的结果,得到大问题的解。

    归并排序的主旨就是分解 ,归并:
    分解:将数组分为单个元素,默认单个就是排好序的。
    归并:从最小的只包含一个元素的数组开始两两合并,合并后的数组也是有序的,最后得到原数组也是有序的。
    如图:
    在这里插入图片描述
    如 设有数列{6,202,100,301,38,8,1}
    初始状态:6,202,100,301,38,8,1
    第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;
    第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;
    第三次归并后:{1,6,8,38,100,202,301},比较次数:4;
    总的比较次数为:3+4+4=11;
    逆序数为14;

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

    比较快排:
    归并排序是稳定的排序,即相等的元素的顺序不会改变。如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要。归并排序的比较次数小于快速排序的比较次数,移动次数一般多于快速排序的移动次数。
    速度仅次于快速排序,一般用于对总体无序,但各子项相对有序的数组排序。
    应用:求逆序对数。在合并的时候,记录逆序对。

    复杂度:

    • 归并排序比较占用内存,需要额外的空间来存放合并后的数组,是典型的用空间换时间的例子。
    • 改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值,则说明序列可以直接形成一段有序序列不需要再归并,反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(n)。
    • TimSort可以说是归并排序的终极优化版本,主要思想就是检测序列中的天然有序子段(若检测到严格降序子段则翻转序列为升序子段)。在最好情况下无论升序还是降序都可以使时间复杂度降至为O(n),具有很强的自适应性。
      在这里插入图片描述
      相比快排:最好O(N),最坏O(N*N),空间复杂度O(1)。
    package sort;
    /*
     * 归并排序:利用递归来分解数组,利用分治来合并数组。
     * 核心思想:将一个无序的n长数组切成n个有序子序列(只有一个数据默认为有序),
     * 			然后两两合并,再将合并后的n/2个子序列继续进行两两合并,循环。。
     * 因为将两个有序的数组归并到另一个数组中,所以需要开辟额外的空间。workspace
     * 
     * 算法:元素总数为n,需要分log2n层,每一层归并复制后,再与上一层继续归并,复制总数n*log2n
     * 		所以算法复杂度为O(n*log2n),比较次数远小于复制次数,可忽略。
     */
    public class Merge {
    	
    	public static int[] mergeSort(int[] nums,int l,int h) {
    		if(l==h) {
    			return new int[] {nums[l]}; //分解到一个元素默认有序。
    		}
    		
    		//先递归分解
    		int mid = l + (h-l)/2;
    		int[] leftArr = mergeSort(nums, l, mid); //对左分组排序
    		int[] rightArr = mergeSort(nums, mid+1, h); //对右分组排序
    		int[] newNum = new int[leftArr.length + rightArr.length]; //存放归并排好序的数组
    		
    		//后归并排序
    		int m=0,i=0,j=0;
    		while(i<leftArr.length && j<rightArr.length) {
    			newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
    		}
    		while(i<leftArr.length) {
    			newNum[m++] = leftArr[i++];
    		}
    		while(j<rightArr.length) {
    			newNum[m++] = rightArr[j++];
    		}
    		
    		return newNum; //返回归并后的数组
    	}
    	
    	public static void main(String[] args) {
    		int[] nums = new int[] {9,3,6,2,0,7,4,1};
    		int[] newNums = mergeSort(nums, 0, nums.length-1);
    		for(int x : newNums) {
    			System.out.print(x+" ");
    		}
    	}
    }
    
    
    展开全文
  • 二路归并排序: 时间复杂度:O(nlogn) 外层函数需要遍历的次数与2的指数次有关(外层的时将复杂度为O(logn)),内层函数需要完全遍历所有数据(内层的时间复杂度为O(n)),两个相乘整体的时间复杂度为O(nlogn) 空间...

    基础数据结构之八大排序算法(五)

    ⑤二路归并排序:

    时间复杂度:O(nlogn) 外层函数需要遍历的次数与2的指数次有关(外层的时将复杂度为O(logn)),内层函数需要完全遍历所有数据(内层的时间复杂度为O(n)),两个相乘整体的时间复杂度为O(nlogn)
    空间复杂度:O(nlogn) 额外的辅助变量会影响的问题的规模(内层额外辅助空间brr,外层函数所需额外辅助变量i),整体空间复杂度为O(nlogn)
    稳定性:不稳定 存在跳跃交换

    (以顺序表作为待排序对象)

    1.基本思想
    (1).一开始将所有数据看作单独的个体(队列),这个时候他们都独自有序。
    (2).两个对列两个队列融合(保证融合后有序稳定(不存在跳跃交换))
    (3).重复第二步直到所有数据都到一个队列中。

    以数组arr[]={21,12,7,9,11,98,56,88,66,68}为例:

    在这里插入图片描述
    (这里初始数据一共是10个,第一次1个队列和1个队列融合,第二次2个数据的队列和2个数据的队列融合,第三次4个数据的队列和4个数据的队列融合,第四次8个数据的队列和8个数据(实际上其中只有2个数据)的队列融合),从而看出融合次数的规律:
    在这里插入图片描述
    【设 i 为运行次数,当( i * 2 ) < 总数据个数时继续排序】

    2.具体合并方法

    (1).需要设置一个临时辅助空间 brr 来存放两两队列对比排序完数据。
    (2).左右手对比时,先从左右手中各从左到右对比,两手中较小的那个放到辅助空间 brr 中,循环这样比较直到一只手空了,则剩下的那个手里的数据依次放到辅助空间 brr 中。
    (3).两手放完后,再去抓另外两组

    *设置临时辅助空间 brr 的原因
    例如数组arr[]={7,9,11,12,12,11,88,98,66,68}时:
    在这里插入图片描述
    当只用arr时会导致无序,不稳定,所以需要设立临时辅助空间brr。

    3.代码实现

    <1>.所需头文件和宏替换:

    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<stdbool.h>
    
    #define ar arr[]={21,12,7,9,11,98,56,88,66,68}
    #define ELEM_TYPE int
    
    int ar;
    

    <2>.顺序表的建立:

    typedef struct Sqlist
    {
    	ELEM_TYPE* data;
    	int length;
    	int SIZE;
    }Sqlist,*PSqlist;
    

    <3>.顺序表的初始化:

    void Init_Sqlist(PSqlist L)
    {
    	L->data = arr;
    	L->length = 0;
    	L->SIZE = sizeof(arr) / sizeof(arr[0]);
    }
    

    <4>.打印

    void Show(PSqlist L)
    {
    	for (int i = L->length; i < L->SIZE; i++)
    	{
    		printf("%d ", L->data[i]);
    	}
    	printf("\n\n");
    }
    

    <5>.每一次的归并排序:

    void Merge(PSqlist L,int gap)          //控制一次融合,gap是每次融合组中数据的个数
    {
    	ELEM_TYPE* brr = (ELEM_TYPE*)malloc(sizeof(ELEM_TYPE) * L->SIZE);   //申请额外辅助空间brr
    	int i = 0;          //辅助空间的下标
    
    	//左右手的边界
    	int low1 = 0;                           
    	int high1 = low1 + gap - 1;      //有边界=左边界+偏移量
    	int low2 = high1 + 1;
    	int high2 = low2 + gap - 1 < L->SIZE ? low2 + gap - 1 : L->SIZE - 1;
    
    	while (low2 <= high2)              //最外层保证可以抓取值
    	{
    		while (low1 <= high1 && low2 <= high2)        //内层保证两只手都有值可以比较大小
    		{
    			if (arr[low1] <= arr[low2])
    			{
    				brr[i++] = arr[low1++];
    			}
    			else
    			{
    				brr[i++] = arr[low2++];
    			}
    		}
    		//内层循环退出的时候代表有一只手为空,这时直接将不为空的手里的数据依次放到brr中
    
    		while (low1<=high1)         //左手不空时
    		{
    			brr[i++] = arr[low1++];
    		}
    
    		while (low2<=high2)         //右手不空时
    		{
    			brr[i++] = arr[low2++];
    		}
    
    		//已经将这次的左右手都放到brr中了,就让左右手再去抓另外的组
    		low1 = high2 + 1;
    		high1 = low1 + gap - 1;
    		low2 = high1 + 1;
    		high2 = low2 + gap - 1 < L->SIZE ? low2 + gap - 1:L->SIZE - 1;    //这里是决定外层循环退出的关键
    
    	}
    	//外层循环退出代表两种情况:1.此时全部数据都已经排完,目前左右手都是空的,这种情况不用管
    	                          //2.此时左手有值右手没有值,这时只需要将左手的值依次放进brr就可以
    
    	while (low1 < L->SIZE)
    	{
    		brr[i++] = arr[low1++];
    	}
    
    	//此时brr已经满了,只需将brr都覆盖arr即可
    	for (int k = 0; k < L->SIZE; k++)
    	{
    		arr[k] = brr[k];
    	}
    
    	//最后将临时辅助空间释放防止内存泄露
    	free(brr);
    }
    

    <6>.二路归并排序:

    void MergeSort(PSqlist L)          //控制总的融合次数
    {
    	for (int i = L->length + 1; i < L->SIZE; i = i * 2)
    	{
    		Merge(L, i);
    	}
    }
    

    <7>.主函数:

    int main()
    {
    	Sqlist head;
    	Init_Sqlist(&head);
    	printf("初始数据为:");
    	Show(&head);
    
    	MergeSort(&head);
    	printf("二路归并排序后数据为:");
    	Show(&head);
    	return 0;
    }
    

    <8>.运行结果:
    在这里插入图片描述
    希望这篇博客能帮助大家更好的学习和理解二路归并排序
    感谢阅读!

    展开全文
  • 目录 前言 两两融合规则 ...若将两个有序表合并成一个有序表,称为二路归并。 这些子问题解决的方法都是类似的,解决掉这些小的问题之后,归并子问题的结果,就得到了“大”问题的解。 时间复杂度:..

    目录

    前言

    一、排序规则

    两两融合规则

    二、代码实现

    1.非递归实现

    2.递归实现

    总结


    前言

    归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

    这些子问题解决的方法都是类似的,解决掉这些小的问题之后,归并子问题的结果,就得到了“大”问题的解。

    时间复杂度:平均情况O(nlogn);最好情况(nlogn);最坏情况O(nlogn)
    空间复杂度:O(n)
    稳定性:       稳定
    基本思想:首先将所有数据看做一个个单独的个体(单独的个体有序),然后两两融合,直到所有的数据都在同一个组内。


    一、排序规则

    1.一开始就将所有值都看作单独的个体,这个时候,从另一个角度来讲,他们独自有序。

    2.两个部分两个部分融合(保证融合后有序且稳定)。

    3.重复第二步,直到所有的数据都在同一个队列中。

    两两融合规则

    左手右手各拿起左右两部分中第一个值(也即是最小值),进行比较,谁小,谁先放置(递增序列),如果相等则先放置左边,这是为了保证原有的顺序性。

    此处的"放置",我们需要借助辅助空间,也就是另一个数组来帮助实现。

    我们依旧设立一组数来帮助理解:{21  12  7  9  11  98  56  88  66  68};

    下面图示中数字下的“横线”,表示分组;

    上图只为表现归并思想,省去了辅助空间。

    即不断进行两两融合,直到最后(第四次),数据全部存在于一个队列中,则排序结束。

    上述为非递归式二路归并排序,而递归式仅是将整个队列规模层层降低,变成一个个单独的元素后再进行上述操作。

    因非递归式较易理解,我们在此仅进行非递归分析。

    二、代码实现

    1.非递归实现

    因为代码较长,且难以理解,在此简单分析一下:
    首先,MergeSort函数中,给出了数据每次进行归并时的规模,并调用Merge。

    Merge函数中,首先构造了辅助空间,其大小与原数据队列相同。

    而后我们确定了,左右数据队列的范围。

    左手的左边界:low1 = 0;   //即为数组最左边元素的位置

    左手的右边界:high1 = low1 + gap - 1;  //右边界的确定与问题规模有关,若规模为1,则high = 0 + 1 - 1 = 0;即左手抓住一个值,以此类推。

    右手的左边界:low2 = high + 1;   //因为左右两个数据队列相邻

    右手的右边界:low2 + gap - 1 < len ? low2 + gap - 1 : len - 1;  //此处与左边空间规则相同,但需要考虑合法性问题,即右边界不可能超过数组。

    在while中我们完成了将归并融合的值放入辅助空间的过程。

    其余问题皆在注释中进行分析,逐句理解即可。

    void Merge(int arr[], int len, int gap)//gap:代表合并的两个组中单独的组个数是多少(几几合并的几)
    {
    	//第一步,先整出来辅助空间brr
    	int* brr = (int*)malloc(len * sizeof(int));
    	assert(brr != NULL);
    	int i = 0; //i是辅助空间brr的下标   代表下一个值插入位置
    
    	int low1 = 0;//左手的左边界
    	int high1 = low1 + gap - 1;//左手的右边界
    	int low2 = high1 + 1;//右手的左边界
    	int high2 = low2 + gap - 1 < len ? low2 + gap - 1 : len - 1;//右手的右边界
    
    	while (low2 <= high2)//确保左手和右手都抓到值(左右手都不空),只要右手还有值,左手肯定抓满值了
    	{
            //代表着,融合比较过程中,左右手还不空
            //有一个空了,就不用比较了,直接向brr挪动另一个手中的数据即可
    		while (low1 <= high1 && low2 <= high2)
    		{
    			if (arr[low1] <= arr[low2])//如果左手的第一个值 <= 右手的第一个值
    			{
    				brr[i++] = arr[low1++];//将左手的第一个值放到brr中
    			}
    			else//如果左手的第一个值 > 右手的第一个值
    			{
    				brr[i++] = arr[low2++];//将右手的第一个值放到brr中
    			}
    		}
    
    		//当内层while循环退出,代表着肯定有一个手空了
    		//这里可以不用判断到底哪个手空了,简单粗暴一点(两个数组都调用一下,将其剩余数据向brr挪动)
    		while (low1 <= high1)//将左手剩余数据向brr中挪动
    		{
    			brr[i++] = arr[low1++];
    		}
    		while (low2 <= high2)//将右手剩余数据向brr中挪动
    		{
    			brr[i++] = arr[low2++];
    		}
    
    		//左手右手数据处理完毕,平移,让左手右手再抓两个组
    		low1 = high2 + 1;
    		high1 = low1 + gap - 1;
    		low2 = high1 + 1;
    		high2 = low2 + gap - 1 < len ? low2 + gap - 1 : len - 1;
    	}
    
    	//此时,代表着处理到最后一组了:这时候退出有两种情况:1.左右手都没有抓到值 2.左手不空,右手空 
    	//会不会存在第三种情况:左手空,右手不空?  这种情况不存在
    	//那么怎么处理上面两种可以出现的情况:第一种皆大欢喜,不用管了
    	//                                    第二种,需要处理一下
    
    	//处理2:左手的值放到brr里,右手肯定为空 不用管
    	while (low1 < len)//将左手剩余数据向brr中挪动  //这里是low1<len
    	{
    		brr[i++] = arr[low1++];
    	}
    
    	//最后一步,brr里放满了值, 这时只需要将brr的值同步到arr里即可
    	for (int k = 0; k < len; k++)
    	{
    		arr[k] = brr[k];
    	}
    
    	free(brr);//释放辅助空间brr
    	brr = NULL;
    
    }
    void MergeSort(int* arr, int len)
    {
        assert(arr != NULL);
    	//i代表几几合并的几   当i小于len时,才有必要进行一次融合
    	//当i大于等于len时,没有必要进行一次融合,因为这时所有的值都在同一个组内
    	for (int i = 1; i < len; i *= 2) //logn
    	{
    		Merge(arr, len, i);
    	}
    }

    2.递归实现

    递归实现中,Merge函数的实现与非递归基本相同,代码量还有些许减少。

    主要问题在于理解MergePass中递归思想,其将整个规模层层剥离减少,到达非递归中的初始,即一个元素为一个队列时开始回归,而后进行与非递归相同操作。

    需要注意的是,递归式中的辅助空间则是在外部申请,因为需要防止在递归中同时申请大量空间的情况。

    void Copy(int* src, int* dest, int left, int right)
    {
    	while (left <= right)
    	{
    		src[left] = dest[left];
    		left++;
    	}
    }
    void Merge(int* src, int* dest, int left, int m, int right)
    {
    	int i = left; //i是辅助空间brr的下标   代表下一个值插入位置
    	int j = m + 1;
    	int k = left;
    	while (i <= m && j <= right)//代表着,融合比较过程中,左右手还不空(有一个空了,就不用比较了,直接向brr挪动另一个手中的数据即可)
    	{
    		if (src[i] <= src[j])//如果左手的第一个值 <= 右手的第一个值
    		{
    			dest[k++] = src[i++];//将左手的第一个值放到brr中
    		}
    		else//如果左手的第一个值 > 右手的第一个值
    		{
    			dest[k++] = src[j++];//将右手的第一个值放到brr中
    		}
    	}
    
    	//当内层while循环退出,代表着肯定有一个手空了
    	//这里可以不用判断到底哪个手空了,简单粗暴一点(两个数组都调用一下,将其剩余数据向brr挪动)
    	while (i <= m)//将左手剩余数据向brr中挪动
    	{
    		dest[k++] = src[i++];
    	}
    	while (j <= right)//将右手剩余数据向brr中挪动
    	{
    		dest[k++] = src[j++];
    	}
    }
    void MergePass(int* src, int* dest, int left, int right)
    {
    	if (left < right)
    	{
    		int mid = (left + right) / 2;
    		MergePass(src, dest, left, mid);
    		MergePass(src, dest, mid + 1, right);
    
    		Merge(src, dest, left, mid, right);
    		Copy(src, dest, left, right);
    	}
    }
    void MergeSort(int* arr, int len)
    {
    	if (len < 2 || arr == NULL)
    	{
    		return;
    	}
    	int* tmp = (int*)malloc(sizeof(int) * len);
    	MergePass(arr, tmp, 0, len - 1);
    	free(tmp);
    }

    总结

    以上就是今天学习的内容,本文介绍了归并排序的排序规则和代码实现,归并排序速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。

    展开全文
  • 数据结构----二路归并排序

    千次阅读 2021-07-06 21:33:43
    二路归并排序的基本思想 设数组a中存放了n个数据元素,初始时把它们看成是n个长度为1的有序子数组,然后从第一个有序子数组开始,把相邻的有序子数组两两合并,得到[n/2]个长度为2的新的有序子数组(当n为奇数时,...
  • 二路归并排序和多路归并排序

    千次阅读 2019-10-03 11:48:14
    其实归并排序挺好理解的,也挺好实现的。其实也挺像我们的平常分工合作的。就像一样事情分成几份,由不同的人去做。再合并起来,采用了分治的思想。 对于一个数列,也同是如此。 我们只需要不断地对着中点切分就...
  • 对于链表的排序问题,想找一种时间复杂度为O(nlogn),空间复杂度O(1)的算法。该问题源自于Leetcode,...思路:和数组的二路归并基本一致。所不同的是:1、要遍历一遍才能找到中间位置。2、首尾位置都要记下来,因...
  • 数据结构与算法:二路归并排序(合并排序)

    千次阅读 多人点赞 2020-05-11 20:38:18
    数据结构与算法:二路归并排序/合并排序概述:图解: 概述: List item 图解: 假设我们有这样一组数据 A[9] = {4,3,6,7,9,1,2},他在内存中这样排序
  • 本文主要介绍了二路归并排序和一些线性时间排序(计数排序、基数排序和桶排序)。
  • #include "stdio.h"#define MAXSIZE 50typedef int RcdType;void Merge(RcdType SR[],RcdType (&TR)[MAXSIZE],int i,int m,int n){int j,k;for(j=m+1,k=i;i<=m&&j<=n;++k)if (SR[i]{TR[k]=SR[i++]...
  • 二路归并排序(基于分治的思想,先分解再合并)   算法思想:先分解,然后两两归并,直到合成一个新的有序表。   相关代码如下: // 归并排序:先分解再合并 void Merge_sort(int[] array, int left, int ...
  • 文章目录二路归并排序一、大概思路二、代码实现2.读入数据下一篇 二路归并排序 一、大概思路 二、代码实现 # -*- coding: utf-8 -*- """ Created on Tue Nov 16 09:34:33 2021 @author: lenovo 转载:...
  • 基于递归调用的二路归并排序的理解与运用
  • 前面有篇文章已经写了选择类排序、交换类排序和插入类排序(传送门),下面将介绍二路归并排序和基数排序。 二路归并排序 1、执行过程        原始序列:45 35 65 95 75 15 25 &...
  • 设定两个指针,最初位置分别为两个已经排序序列的起始位置2.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置3.重复步骤3直到某一指针达到序列尾4.将另一序列剩下的所有元素直接...
  • 满意答案hzysh1970推荐于 2016.08.07采纳率:54%等级:12已...//要排序元素类型void Merge(RecType *R,int low,int m,int high){//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]i...
  • 数组的二路归并排序 python实现
  • C语言二路归并排序算法, 写了个二路归并的归并排序小代码,直接贴上来
  • 二路归并排序Python实现-III 归并排序 是一种 效率比较高并且稳定的算法。时间复杂度 O(NLog(N)),空间复杂度 O(N). 归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,464
精华内容 10,185
关键字:

二路归并排序

友情链接: 图书管理系统.zip