精华内容
下载资源
问答
  • 二路归并模式:每次仅作两个文件的归并;当有多个文件时,采用两两归并的模式,最终得到一个完整的记录文件。 二元归并树:二路归并模式的归并过程可以用一个二元树的形式描述,称之为二元归并树。 贪心求解: 任意...
  • 主要介绍了java二路归并排序示例,需要的朋友可以参考下
  • 通过建立单链表实现对一元多项式的相加,充分体现单链表的运用及有序表的运用
  • 二路归并

    千次阅读 2021-02-21 10:09:30
    二路归并 题目描述 编写一个程序,使用分治策略实现二路归并排序(升序)。 (图源网络,我忘了哪儿存的了。。。侵删) 输入 多组输入,每组第一个数字为数组长度,然后输入一个一维整型数组。 输出 输出排序之后...

    二路归并

    题目描述

    编写一个程序,使用分治策略实现二路归并排序(升序)。

    (图源网络,我忘了哪儿存的了。。。侵删)
    这里写图片描述

    img

    输入

    多组输入,每组第一个数字为数组长度,然后输入一个一维整型数组。

    输出

    输出排序之后(升序)的一维整型数组,每组输出占一行。

    样例输入

    6 1 8 6 5 3 4
    5 12 42 2 5 8
    

    样例输出

    1 3 4 5 6 8
    2 5 8 12 42
    

    了解算法

    一、将一个数组拆分为两个部分,一般取数组长度一般的位置为界,分为两个子数组,再分别对这两个子数组进行递归归并排序。

    ​ 二、我们确信在进行完递归排序之后,原两数组都会分别变为各自排好序的两个数组,于是接下来我们进行将这两个子数组合并为一个数组的操作;对于最上层,这是最后一步完成排序的操作.

    ​ 三、对于每一次分解出来的子数组,进行归并操作。

    归并排序(Merge Sort)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个有序的子序列,再把有序的子序列合并为整体有序序列。

    归并排序的具体做法:

    1. 把原序列不断地递归等分,直至每等份只有一个元素,此时每等份都是有序的。
    2. 相邻等份合并,不断合并,直至合并完全。

    二路归并

    归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序最常用的是二路归并,即把两个小的有序的序列和并成一个大的有序序列:合二为一。

    一个二路归并的流程图是这样的:

    依次比较两个数组的元素,首先是第一个数组的第一个元素和第二个数据的第一个元素比较并排序,依次类推。

    img

    多路归并无非是多个有序的小序列合并成一个大的有序序列,道理和二路归并一样。

    算法分析:

    1.算法的复杂度

    img

    对数组长度为n的序列进行归并排序,则大约要进行logn次归并,每一次合并都是线性时间O(n)。故粗略的计算出归并排序的时间复杂度是O(nlogn)(最好、最差都是这样)。空间复杂度是O(n)。详细的时间复杂度分析是这样的:

    对长度为n的序列归并排序,需要递归的对长度为n/2的子序列进行归并排序,最后把两段子序列二路归并。递推关系是这样的:T(n)=2T(n/2)+O(n),显然T(1)=O(1),解得T(n)=o(nlogn)。

    2.稳定性

    归并排序是稳定的,并且是时间复杂度为o(nlogn)的几种排序[快速排序、堆排序中唯一稳定的排序算法。

    3.存储结构

    顺序存储和链式存储都行。

    另外,归并排序多用于外排序中。

    Code

    package Week8;
    
    import java.util.Scanner;
    //归并排序
    public class QA {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){
                int num = sc.nextInt();
                int[] arr = new int[num];
                for(int i=0;i<arr.length;i++){
                    arr[i] = sc.nextInt();
                }
                mergeSort(arr,0,num-1);
                //System.out.println(arr);
                for(int i=0;i<arr.length;i++){
                    System.out.print(arr[i]+" ");
                }
                System.out.println();
            }
        }
        public static void mergeSort(int[] arr,int begin,int end){
            if(begin >= end){
                return;
            }
            int mid = (begin+end)/2;
            mergeSort(arr,begin,mid);
            mergeSort(arr,mid+1,end);
            Merge(arr,begin,mid,end);
        }
        //将左右两边分成两个数组进行归并
        public static void Merge(int[] arr,int begin,int mid,int end){
            //int mid = (begin+end)/2;
            //定义一个临时数组
            int[] temp = new int[end-begin+1];
            //数组起点到终点,给临时数组赋值。
            for(int i=begin;i<=end;i++){
                temp[i-begin] = arr[i];
            }
            //i,j分别为左右两边数组元素的起始下标
            int i = begin;
            int j = mid+1;
            for(int k=begin;k<=end;k++){
                if(i>mid){
                    //检查左半边下标是否越界,若越界就是右边
                    arr[k] = temp[j-begin];
                    j++;
                } else if(j > end) {
                    //检查右边下标是否越界
                    arr[k] = temp[i-begin];
                    i++;
                } else if(temp[i-begin] <= temp[j-begin]) {
                    //判断左右两边元素的大小
                    arr[k] = temp[i-begin];
                    i++;
                } else {
                    arr[k] = temp[j-begin];
                    j++;
                }
            }
        }
    }
    
    
    展开全文
  • 主要介绍了c++实现二路归并排序的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • 二路归并排序

    2015-06-06 23:21:31
    编写程序对{75.,87,68,92,88,61,77,96,80,72}进行二路归并排序
  • 简单的二路归并实现

    2018-10-19 09:02:38
    能实现C语言简单的二路归并法,两条链表建立后,在进行合并排序
  • 二路归并排序和多路归并排序

    千次阅读 2019-10-03 11:48:14
    其实归并排序挺好理解的,也挺好实现的。其实也挺像我们的平常分工合作的。就像一样事情分成几份,由不同的人去做。再合并起来,采用了分治的思想。 对于一个数列,也同是如此。 我们只需要不断地对着中点切分就...

     

    添加微信公众号可以索取资料
    添加QQ群一起分享技术:895467044

     

    啥也先不说,先上图

     

     

    ,上图最好理解

    其实归并排序挺好理解的,也挺好实现的。其实也挺像我们的平常分工合作的。就像一样事情分成几份,由不同的人去做。再合并起来,采用了分治的思想。

    对于一个数列,也同是如此。

    我们只需要不断地对着中点切分就可以了。

     

     

     

     

    就这样类似的下去,针对每一个每次分割的取键合并

    总共可以分两个过程,一个cut,一个merge

    cut:对数列进行分割。

    merge:这个过程就是两个区间进行合并,可以新建要给数组,然后从两个已排序的数组依次比较,这样就可以将小的或者大的先放进新的数组。

     

    具体可以看看代码实现:

    public int[] sort(int[] nums,int start,int end) {
            //如果只有一个节点了(start=end)没必要排序,直接将这个元素作为新数组返回就是了
    		if(nums==null||start==end) return new int[] {nums[start]};
    //cut过程
    		//计算中点
    		int mid = (start+end)/2;
            //这个包含了cut过程,就是将左半边和右半边分开
    		int[] left = sort(nums, start, mid);//计算左半部分,从start------mid
    		int[] right = sort(nums, mid+1, end);//计算右半部分,从mid+1------end
    		
    //merge过程
    		//新建一个数组,用来保存合并后的元素
    		int[] retu = new int[left.length+right.length];
            //i是left的索引,j是right的索引,p是新数组索引
    		int i=0,j=0,p=0;
    
    		while(i<left.length&&j<right.length) {
                //哪个小就先放入新数组,这是从小到大排序
    			if(left[i]<right[j]) {
    				retu[p]=left[i];
    				i++;
    			}else {
    				retu[p]=right[j];
    				j++;
    			}
    			p++;
    		}
            //如果某一个数组比另一个数组长,那么它的索引肯定没有到最后,那么从它的索引到以后的全都是顺序的,那么直接顺序添加进去就行
    		if(i<left.length) for(;i<left.length;i++,p++) retu[p]=left[i];
    		else if(j<right.length) for(;j<right.length;j++,p++) retu[p]=right[j];
    		return retu;
    		
    	}

     

    当然这是一个数组的情况

    前一天在leetcode发现了要给题目,是对链表进行排序,采用归并排序;

    https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/

    可以去做做

    public ListNode sortList(ListNode head) {
            if (head == null || head.next == null)
                return head;//判断是不是已经没了,只剩一个节点,或者没有节点了,就不用排序
    //cut过程
            //下面就是利用物理中的快慢速度,来找到中点
            //一个是一次跳一个节点,另一个跳两个节点,同样的速度,不同的步长,当第二个到了终点,第一个还在正中心
            ListNode fast = head.next, slow = head;
            while (fast != null && fast.next != null) {//如果是偶数个的话(1234),fast==null;;;;;如果是奇数个的话(12345),fast.next=null
                slow = slow.next;
                fast = fast.next.next;
            }        
            ListNode tmp = slow.next;//tmp保存后半部分链表的头节点
            slow.next = null;//将前半部分与后半部分链表切开
            ListNode left = sortList(head);//求的前半部分链表
            ListNode right = sortList(tmp);//求的后半部分链表
    
    //merge过程
            ListNode h = new ListNode(0);//新的头节点,来讲left和right合并
            ListNode res = h;
            while (left != null && right != null) {
                if (left.val < right.val) {
                    h.next = left;
                    left = left.next;
                } else {
                    h.next = right;
                    right = right.next;
                }
                h = h.next;
            }
            h.next = left != null ? left : right;//将剩下的连接起来
            return res.next;
        }

    这个链表的形式虽然找中心节点比较麻烦了,但是在每次新排序的节点中,空间开销不用新建整个数组,而是只需要头节点和一个索引指针(跟随新来的节点)就行。

     

    所以对比上面两种,要知道归并排序的核心过程就是cutmerge

     

    非递归实现

     

     

    复杂度分析

    关于时间复杂度很明显

    我们一共要分为log n层

    每一层,我们需要将每一个元素都放进一个新的数组里面去,也就是说每一层都会对所有的元素进行操作,复杂度n

    总共就是nlog n

    空间复杂度:

    因为新建了一个数组,所以空间复杂度为O(n),但是对于链表因为只需要一个头节点和索引指针,它的空间复杂度是常数级别的

    多路归并排序

     

    归并排序思想使用

     

    归并的思想主要用于外部排序

    外部排序可分两步

    • 待排序记录分批读入内存,用某种方法在内存排序,组成有序的子文件,再按某种策略存入外存。
    • 子文件多路归并,成为较长有序子文件,再记入外存,如此反复,直到整个待排序文件有序。

    外部排序可使用外存、磁带、磁盘,最初形成有序子文件长取决于内存所能提供排序区大小和最初排序策略,归并路数取决于所能提供排序的外部设备数。比如在mapreduce里面,就有个排序过程,当许多小文件溢写到磁盘时,多个小文件进行归并排序。

    展开全文
  • 算法篇:二路归并

    2020-08-30 18:55:46
    目录二路归并开辟新数组并进行归并写法1写法2归并至原空间普通归并哨兵牌法 文章最后修改时间:2020-08-30 18:55 二路归并   将两个有序数列组成一个新的有序数列。   从最小端开始,哪边小就取哪边放入新序列中...


    文章最后修改时间:2020-08-30 18:55

    二路归并

      将两个有序数列组成一个新的有序数列。
      从最小端开始,哪边小就取哪边放入新序列中,最后得到的序列依然是有序的。
      若两个有序数列长度分别为N和M, 则归并的时间复杂度为   O ( N + M ) \ O(N+M)  O(N+M), 空间复杂度   O ( N + M ) \ O(N+M)  O(N+M)

    开辟新数组并进行归并

      假设两个有序数列分别在数组a和数组b中,合并后保存到另一个数组c。中

    写法1

    • 重点在归并时的判断,当数组b已完成,或者数组a未完成且数组a这边比较小时选择数组a
    • (ib >= lenB) 需放在 (ia < lenA) && (a[ia] <= b[ib]) 前面, 不可交换。如果放在后面,当 ib == lenBia < lenA 时,(a[ia] <= b[ib]) 将会越界访问数组b
    • 当两边都相等时,a优先。
    int* merge(int a[], int lenA, int b[], int lenB)
    {
    	int len = lenA + lenB;
    	int* c = (int*)std::malloc(len * sizeof(int));
    	int ia = 0, ib = 0;
    	for (int ic = 0; ic < len; ic++) {
    		if ((ib >= lenB) || (ia < lenA) && (a[ia] <= b[ib]))
    			c[ic] = a[ia++];
    		else
    			c[ic] = b[ib++];
    	}
    	return c;
    }
    

    写法2

    • 先归并直到有一路完成,然后再将另一路剩余部分直接放在末尾
    • 代码比上面那种多一些
    int* merge(int a[], int lenA, int b[], int lenB)
    {
    	int len = lenA + lenB;
    	int* c = (int*)std::malloc(len * sizeof(int));
    
    	int ia = 0, ib = 0, ic = 0;
    	//归并直到有一路完成
    	while (ia < lenA && ib < lenB) {
    		if (a[ia] <= b[ib])
    			c[ic++] = a[ia++];
    		else
    			c[ic++] = b[ib++];
    	}
    	//剩余部分直接加入末尾
    	while (ia < lenA)
    		c[ic++] = a[ia++];
    	while (ib < lenB)
    		c[ic++] = b[ib++];
    
    	return c;
    }
    

    归并至原空间

    假设两个都在数组a中,且内存连续,分别为a[left] ~ a[m]和a[m+1] ~ a[right],要将数组归并后保存到原来的位置,则需要额外的空间。

    普通归并

    • 归并到一个临时数组中,再将新序列复制回原来的位置
    void merge(int a[], int left, int m, int right)
    {
    	int lenA = m - left + 1, lenTemp = right - left + 1;
    	//开辟临时数组
    	int* temp = (int*)std::malloc(lenTemp * sizeof(int));
    
    	//归并到临时数组中
    	int ia = left, ib = m + 1;
    	for (int k = 0; k < lenTemp; k++) {
    		//不越界并且小于另一边,或者另一边越界
    		if ((ib > right) || (ia <= m) && (a[ia] <= a[ib]))
    			temp[k] = a[ia++];
    		else
    			temp[k] = a[ib++];
    	}
    
    	//拷贝回数组a
    	for (int i = 0; i < lenTemp; i++)
    		a[i + left] = temp[i];
    
    	free(temp);
    }
    

    哨兵牌法

    • 开辟临时数组,将两个有序数列复制过去,并在末尾放置哨兵牌(无穷大)。
    • 然后再将两个有序数列归并到原来的数组中。
    • 因为原数列是非降序的,末尾的哨兵牌为无穷大,所以归并时不会取到哨兵牌,不用担心数组越界的问题,所以无需越界的判断。
    void merge(int a[], int left, int m, int right)
    {
    	int lenA = m - left + 1, lenB = right - m;
    	//开辟临时数组,比原数组多1(用来放哨兵牌),并将数据拷贝过去
    	int* L = (int*)std::malloc((lenA + 1) * sizeof(int));
    	int* R = (int*)std::malloc((lenB + 1) * sizeof(int));
    	for (int i = 0; i < lenA; i++)
    		L[i] = a[i + left];
    	for (int i = 0; i < lenB; i++)
    		R[i] = a[i + m + 1];
    
    	//放置无穷大哨兵牌,可简化代码(不用担心有数组越界, 少了一些判断)
    	L[lenA] = R[lenB] = INT_MAX;
    
    	int i = 0, j = 0;
    	for (int k = left; k <= right; k++) {
    		if (L[i] < R[j])
    			a[k] = L[i++];
    		else
    			a[k] = R[j++];
    	}
    
    	free(L);
    	free(R);
    }
    
    展开全文
  • 二路归并排序C++实现

    千次阅读 2019-07-13 11:20:21
    二路归并排序 基本思想 二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并:两个有序表放在同一数组的相邻位置上,arr[left]到arr[center-1]为第一个有序表,arr[center]到arr[right...

    二路归并排序

    1. 基本思想

      二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并:两个有序表放在同一数组的相邻位置上,arr[left]到arr[center-1]为第一个有序表,arr[center]到arr[right]是第二个有序表。每次从两端中取出一个进行比较,小的先放在一个temp数组,最后将比较剩下的直接放到temp中去,最后将temp又复制回arr。这是“治”。
      所谓“分”,就是递归地将前半部分和后半部分的数据各自归并排序即可。

    2. 算法分析
      每一趟归并的时间复杂度为O(n),共需要进行⌈log2n⌉趟。对应的算法的时间复杂度为O(nlog2n)。归并排序的空间复杂度O(n)。另外,归并排序中归并的算法并不会将相同关键字的元素改变相对次序,所以归并排序是稳定的。
      二路归并排序的前提是两个序列本身有序。

    void Merger(int *arr, int len, int width)
    {
    	int *temp =(int *)malloc(sizeof(int) * (len));
    	//首先对两路下标分别进行初始化
    	int l1 = 0;
    	int h1 = l1 + width - 1;
    	int l2 = h1 + 1;
    	int h2 = l2 + width - 1 < len - 1 ? l2 + width - 1 : len - 1;
    	int temppos = 0;
    	//判断所在下标位置的值
    	while (l1 < len && l2 < len)
    	{
    		while (l1 <= h1 && l2 <= h2)
    		{
    			if (arr[l1] < arr[l2])
    			{
    				temp[temppos++] = arr[l1++];
    			}
    			else
    			{
    				temp[temppos++] = arr[l2++];
    			}
    		}
    		//l1有剩余
    		while (l1 <= h1)
    		{
    			temp[temppos++] = arr[l1++];
    		}
    		//l2有剩余
    		while (l2 <= h2)
    		{
    			temp[temppos++] = arr[l2++];
    		}
    		//l1 l2向后移动
    		l1 = h2 + 1;
    		h1 = (l1 + width - 1) < (len - 1) ? (l1 + width - 1) : (len - 1);
    		l2 = h1 + 1;
    		h2 = (l2 + width - 1) < (len - 1) ? (l2 + width - 1) : (len - 1);
    	}
    	//奇数归并块 剩下的一个单都块操作
    	while (l1 <len)
    	{
    		temp[temppos++] = arr[l1++];
    	}
    	//用temp覆盖arr
    	for (int i = 0; i < len ; ++i)
    	{
    		arr[i] = temp[i];
    	}
    //	free(temp);
    }
    void MergeSort(int *arr, int len)
    {
    	for (int i = 1; i < len; i *= 2)
    	{
    		Merger(arr, len, i);
    	}
    }
    void show(int *arr, int len)
    {
    	for (int i = 0; i < len; ++i)
    	{
    		cout << arr[i] << " ";
    	}
    }
    int main()
    {
    	int array[] = { 12, 51, 1, 36, 98, 21, 38, 47 };
    	int len = sizeof(array) / sizeof(array[0]);
    	MergeSort(array, len);
    	show(array, len);
    	system("pause");
    	return 0;
    }
    
    展开全文
  • C语言二路归并排序算法, 写了个二路归并的归并排序小代码,直接贴上来
  • 链表二路归并排序

    2020-12-19 17:52:57
    } } 归并排序的含义 将两个或者两个以上的有序表组合成一个新的有序表 该题使用的是二路归并,即 两个有序表组合成一个新的有序表,如果还是不理解归并排序,查看我的另一篇博客排序图接 现在解决问题的思路有了...
  • 二路归并算法

    2021-05-23 11:34:05
    二路归并1.基本思想2.举例说明3.方法实现4.性能分析 1.基本思想 二路归并排序就是将两个有序子表归并成一个有序表,归并排序是“分治法”的一个非常典型的应用,同时它也是递归算法的一个好的实例。它将问题分成...
  • 二路归并排序Python实现-III 归并排序 是一种 效率比较高并且稳定的算法。时间复杂度 O(NLog(N)),空间复杂度 O(N). 归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法...
  • 基于链表的二路归并排序和基于数组的二路归并排序的总体实现思想是一样的,同样是基于分治法。在递归算法结构下体现的是切分(相对比较常见的切分方法是对半切分),到分无可分时,切分函数调用逐个退栈继而进行合并...
  • 另外,链表的二路归并比数组的二路归并还要简单,因为后半部分不需要额外的while循环。 代码 class Solution { public ListNode mergeTwoLists(ListNode node1, ListNode node12) { ListNode dummy = new ListNode(-...
  • 数据结构-二路归并及归并排序

    万次阅读 多人点赞 2017-12-08 12:47:42
    一、介绍:归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。...二、二路归并介绍在归并的过程中步骤如下:①设定两个指针(不一定非是指针,只需要记住对应开始下标即可),最初位置分别为两个已
  • 二路归并排序的基本思想 设数组a中存放了n个数据元素,初始时把它们看成是n个长度为1的有序子数组,然后从第一个有序子数组开始,把相邻的有序子数组两两合并,得到[n/2]个长度为2的新的有序子数组(当n为奇数时,...
  • 二路归并排序(基于分治的思想,先分解再合并)   算法思想:先分解,然后两两归并,直到合成一个新的有序表。   相关代码如下: // 归并排序:先分解再合并 void Merge_sort(int[] array, int left, int ...
  • C++实现二路归并排序算法

    千次阅读 2020-11-05 22:21:20
    归并类:二路归并排序 基数类:多关键字排序 九种算法的时间复杂度、空间复杂度和稳定性小结如下: 本文放出二路归并算法的排序算法代码。 二路归并排序 void merge(int R[], int low, int mid, int high) { int ...
  • 递归实现的二路归并排序算法,其中对结构体按其内部一个关键字(本例是对一个任务结构体,按其收益排序)进行排序
  • C语言实现二路归并算法 #include<stdio.h> //将有序的sr[i...m]和sr[m+1...n]归并为有序的tr[i...n] void merge(int sr[],int tr[],int i,int m,int n) { int j,k; for(j=m+1,k=i;i<=m&&j<=n;...
  • 数组的二路归并排序 python实现
  • 以单链表为存储结构, 实现二路归并排序的算法, 要求链表不另外占用存储空间, 排序过程中不移动结点中的元素, 只改各链结点中的指针
  • 有序表的二路归并

    2020-02-17 22:49:40
    在中国大学MOOC上学习了分别用单链表和顺序表实现有序表的二路归并,为加深印象与理解,自己操作了一下。 有序表中所有有序表以递增或递减的方式有序排列。 两个有序表L1和L2合并成一个有序表L3。 用单链表实现 #...
  • 数据结构与算法:二路归并排序(合并排序)

    千次阅读 多人点赞 2020-05-11 20:38:18
    数据结构与算法:二路归并排序/合并排序概述:图解: 概述: List item 图解: 假设我们有这样一组数据 A[9] = {4,3,6,7,9,1,2},他在内存中这样排序

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 23,557
精华内容 9,422
关键字:

二路归并