精华内容
下载资源
问答
  • 二路归并排序代码
    2021-05-24 05:19:49

    /***********************************************************************************************

    1.设定两个指针,最初位置分别为两个已经排序序列的起始位置

    2.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

    3.重复步骤3直到某一指针达到序列尾

    4.将另一序列剩下的所有元素直接复制到合并序列尾

    归并排序:

    归并排序具体工作原理如下(假设序列共有n个元素):

    1.将序列每相邻两个数字进行归并操作,形成floor(n / 2)个序列,排序后每个序列包含两个元素

    2.将上述序列再次归并,形成floor(n / 4)个序列,每个序列包含四个元素

    3.重复步骤2,直到所有元素排序完毕

    归并排序是稳定的,它的最差,平均,最好时间都是O(nlogn)。但是它需要额外的存储空间.

    归并排序法(Merge Sort,以下简称MS)是分治法思想运用的一个典范。

    其主要算法操作可以分为以下步骤:

    Step 1:将n个元素分成两个含n/2元素的子序列

    Step 2:用MS将两个子序列递归排序(最后可以将整个原序列分解成n个子序列)

    Step 3:合并两个已排序好的序列

    ************************************************************************************************/

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    using namespace std;

    void Random(int a[],int n)

    {

    int i=0;

    srand( (unsigned)time( NULL ) );

    while(i

    {

    a[i++]=rand();

    }

    }

    void merge(int *a, int low, int mid, int high) //归并操作

    {

    int k, begin1, begin2, end1, end2;

    begin1 = low;

    end1 = mid;

    begin2 = mid + 1;

    end2 = high;

    int *temp = (int *) malloc((high - low + 1) * sizeof(int));

    for(k = 0; begin1 <= end1 && begin2 <= end2; k++) //自小到大排序

    {

    if(a[begin1] <= a[begin2])

    temp[k] = a[begin1++];

    else

    temp[k] = a[begin2++];

    }

    if(begin1 <= end1) //左剩

    memcpy(temp + k, a + begin1, (end1 - begin1 + 1) * sizeof(int));

    else //右剩

    memcpy(temp + k, a + begin2, (end2 - begin2 + 1) * sizeof(int));

    memcpy(a + low, temp, (high - low + 1) * sizeof(int)); //排序后复制到原数组

    free(temp); //释放空间

    }

    void merge_sort(int *a, unsigned int begin, unsigned int end)

    {

    int mid;

    if(begin < end)

    {

    mid=begin+(end-begin)>>1;

    //mid = (end + begin) / 2; 防止数据加法溢出

    merge_sort(a, begin, mid); //分治

    merge_sort(a, mid + 1, end); //分治

    merge(a, begin, mid, end); //合并两个已排序的数列

    }

    }

    int main()

    {

    int a[20];

    Random(a,20);

    for(int i=0;i<20;i++)

    {

    cout<

    }

    merge_sort(a, 0, 20-1);

    for(int i=0;i<20;i++)

    {

    cout<

    }

    return 0;

    }

    更多相关内容
  • 二路归并模式:每次仅作两个文件的归并;当有多个文件时,采用两两归并的模式,最终得到一个完整的记录文件。 二元归并树:二路归并模式的归并过程可以用一个二元树的形式描述,称之为二元归并树。 贪心求解: 任意...
  • **二路归并排序代码**

    2018-10-05 15:35:20
    二路归并排序代码 归并排序说简单也简单,说不简单呢,如果不专心好好理解,直接看代码可能会比较懵,但是如果你仅仅通过代码就看透了算法的精髓,那真的就很厉害了,如果真是这样,请在这篇文章下留言,我十分想...

    二路归并排序代码
    归并排序说简单也简单,说不简单呢,如果不专心好好理解,直接看代码可能会比较懵,但是如果你仅仅通过代码就看透了算法的精髓,那真的就很厉害了,如果真是这样,请在这篇文章下留言,我十分想知道你是怎么做到的,望不吝赐教。
    归并算法的原理其实很简单,就是通过递归不断的将待排序数组拆为我们设定的N个数组,而后对这N个数组分别进行排序,最后再将这N个数组合并起来,而二路归并排序就是将N设置为2.
    我们可以用二叉树来解释这个过程,同时来计算二路归并排序的时间复杂度
    二路归并排序
    从图中我们可以看出,整个流程还是很清晰的嘛,而我们需要做啥才能写出代码呢?这里分为两步:
    第一:写出合并函数,即把分割的两个子数组有序的合并到一起
    第二:递归分割待排序数组,调用合并函数进行合并
    具体代码如下:
    1.合并两个相邻子数组函数Merge
    int Sort_Fun::Merge(int *a, int n, int *b, int k)//a是需要归并的数组,b用来存放归并好的数组,m为需要归并的数组长度,k为需要归并的子数组长度
    {
    int i,j;//遍历所需
    int low1,low2,up1,up2;//两个有序数组的边界
    low1=0;//第一个有序子数组起始边界为0
    int m=0;//b数组下标
    while(low1+k<=n-1)
    {
    low2=low1+k;//确定第二个有序子数组下界
    up1=low2-1;//确定第一个有序子数组上界
    if(low2+k<=n)
    {
    up2=low2+k-1;
    }
    else
    {
    up2=n-1;//如果需要归并数组中余下的元素不足K个,则不必继续进行归并
    }
    for(i=low1,j=low2;i<=up1&&j<=up2;m++)//两个相邻子数组的归并开始
    {
    if(a[i]<a[j])
    {
    b[m]=a[i];
    i++;
    }
    else
    {
    b[m]=a[j];
    j++;
    }
    }
    while(i<=up1)
    {
    b[m++]=a[i++];
    }
    while(j<=up2)
    {
    b[m++]=a[j++];
    }//两个相邻子数组的归并结束
    low1=up2+1;//确定下一轮归并第一个子数组的下标
    }
    for(i=low1;i<m;i++)//将归并好的数组放在b中
    {
    b[m++]=a[i];
    }
    return 1;
    }
    2,二路归并排序
    int Sort_Fun::Merge_sort(int *array, int length)
    {
    int i,k=1;
    int copy=new int[length];//申请备用数组内存
    while(k<length)
    {
    Merge(array,length,copy,k);//合并有序数组
    for(i=0;i<length;i++)
    {
    array[i]=copy[i];//将排序好的数组挪回原数组
    }
    k=k
    2;//设定为二路归并排序
    }
    delete[] copy;//释放掉备用数组内存
    return 1;
    }
    是不是很简单呢?
    说是的人请留言,我想和你聊聊。
    最后放一个我之前做的排序算法性能测试,测试了冒泡排序和快速排序以及归并排序的速度,待排序数组为相同的数组,长度为10W,排序结果如下:
    性能测试
    差距是不是很大?如果到了百万千万级,那么差距就更大了,感兴趣的自己测试吧,也是因为这次测试让我对排序算法产生了浓厚的兴趣。
    至于我为什么写这些呢?是因为国庆假期太无聊,单身狗没人约,闲的没事干吗?
    不是的,是因为我热爱排序,我还会写自然归并排序,随机化快排呢?当然前提是那时哥还是单身狗。

    展开全文
  • 二路归并排序 基本思想 二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并:两个有序表放在同一数组的相邻位置上,arr[left]到arr[center-1]为第一个有序表,arr[center]到arr[right]...
  • 主要介绍了java二路归并排序示例,需要的朋友可以参考下
  • 二路归并排序(基于分治的思想,先分解再合并)   算法思想:先分解,然后两两归并,直到合成一个新的有序表。   相关代码如下: // 归并排序:先分解再合并 void Merge_sort(int[] array, int left, int ...

    二路归并排序(基于分治的思想,先分解再合并)

      算法思想:先分解,然后两两归并,直到合成一个新的有序表。
      相关代码如下:

    	// 归并排序:先分解再合并
    	void Merge_sort(int[] array, int left, int right) {
    		if (left >= right)
    			return;
    		// 1.分解
    		int mid = (left + right) / 2; // 从中间划分成两个待排子序列
    		Merge_sort(array, left, mid); // 对左侧序列进行递归排序left~mid
    		Merge_sort(array, mid + 1, right); // 对右侧序列进行递归排序(mid+1)~right
    		// 2.合并
    		Merge(array, left, mid, right); // 把左右两边的子序列合并在一起
    	}
    
    	// 合并算法
    	void Merge(int[] array, int left, int mid, int right) {
    		// 分别用s1、s2标记两个待排子序列的起始下标位置
    		int s1 = left;
    		int s2 = mid + 1;
    
    		// 用len表示array数组的长度
    		int len = right - left + 1;
    
    		// 设置一个临时数组,存放排好的序列
    		int[] ret = new int[len];
    		int i = 0; // i表示ret数组的下标
    
    		// 两边子序列都有元素时
    		while (s1 <= mid && s2 <= right) {
    			if (array[s1] <= array[s2]) {
    				// 左边序列元素的值小于右边的,就把左边元素的值放到ret中,并更新i和s1
    				ret[i++] = array[s1++];
    			} else {
    				// 反之,就把右边元素的值放到ret中,并更新i和s2
    				ret[i++] = array[s2++];
    			}
    		}
    		// 处理剩下有元素的待排子序列
    		while (s1 <= mid) {
    			ret[i++] = array[s1++];
    		}
    		while (s2 <= right) {
    			ret[i++] = array[s2++];
    		}
    		// 把排好的序列放回到原数组中
    		for (int j = 0; j < ret.length; j++) {
    			array[left + j] = ret[j]; // array数组的起始下标为left
    		}
    	}
    
    	/*
    	 * 归并排序 
    	 * 时间复杂度:O(nlogn) 
    	 * 空间复杂度:O(n) 
    	 * 稳定性:稳定
    	 */
    
    展开全文
  • //归并函数 void merge(int *R, int low, int high) { int mid = (low + high) / 2; //需要定义一个额外的数组,临时存放归并的结果 int maxSize = high - low + 1; int temp[maxSize]; int k = 0; int i = ...

    在这里插入图片描述

    #include <iostream>
    using namespace std;
    //归并函数
    void merge(int *R, int low, int high)
    {
    	int mid = (low + high) / 2;
    	//需要定义一个额外的数组,临时存放归并的结果
    	int maxSize = high - low + 1;
    	int temp[maxSize];
    	int k = 0;
    	int i = low;
    	int j = mid + 1;
    	while (i <= mid && j <= high)
    	{
    		if (R[i] < R[j])
    			temp[k++] = R[i++];
    		else
    			temp[k++] = R[j++];
    	}
    	while (i <= mid)
    		temp[k++] = R[i++];
    	while (j <= high)
    		temp[k++] = R[j++];
    	
    	//需要把临时数组里面的元素重新放回目标数组
    	for (int i = low, j = 0; i <= high && j < k; ++i, ++j)
    		R[i] = temp[j];
    }
    void mergeSort(int *R, int low, int high)
    {
    	if (low >= high)
    		return;
    	int mid = (low + high) / 2;
    	mergeSort(R, low, mid);
    	mergeSort(R, mid + 1, high);
    	merge(R, low, high);
    }
    
    int main()
    {
    	int R[] = {49, 36, 24, 65, 97, 6, 25};
    	int n = 7;
    	mergeSort(R, 0, n-1);
    	for (int i = 0; i < n; ++i)
    		cout << R[i] << endl;
    	return 0;
    }
    

    归并排序的时间复杂度平均情况下,最好情况下,最坏情况下均为O(nlog2n),空间复杂度O(n)

    展开全文
  • #include<stdio.h> #include<stdlib.h> #define maxSizw 100 void merge(int a[],int low,int mid,int high) { int i,j,k; int n1=mid-low+1; int n2=high-mid; int L[n1],R[n2];...i=
  • 二路归并排序的C++实现 #include<iostream> #include<vector> using namespace std; typedef int elem; void mergeArray(vector<elem>&, int, int, int, int (*)(elem, elem)); void ...
  • 二路归并排序: 时间复杂度:O(nlogn) 外层函数需要遍历的次数与2的指数次有关(外层的时将复杂度为O(logn)),内层函数需要完全遍历所有数据(内层的时间复杂度为O(n)),两个相乘整体的时间复杂度为O(nlogn) 空间...
  • 排序算法之归并排序 上学期的数据结构已经讲过归并排序了,但是上学期太懒了,所以没有动手把代码写出来2333。...以下是我写的归并排序代码 #include <iostream> #include <cstdlib>
  • 目录 前言 两两融合规则 ...若将两个有序表合并成一个有序表,称为二路归并。 这些子问题解决的方法都是类似的,解决掉这些小的问题之后,归并子问题的结果,就得到了“大”问题的解。 时间复杂度:..
  • C++实现二路归并排序算法

    千次阅读 2020-11-05 22:21:20
    归并类:二路归并排序 基数类:多关键字排序 九种算法的时间复杂度、空间复杂度和稳定性小结如下: 本文放出二路归并算法的排序算法代码二路归并排序 void merge(int R[], int low, int mid, int high) { int ...
  • 这里写自定义目录标题前言归并算法简介归并算法实现1、二路归并原理2、java代码实现3、测试结果 前言 算法是迷人的,但通常也相当抽象。我在学习的时候,看了很多博客,教程,发现往往他们的代码都不太一样。这对我...
  • 排序算法中的归并排序(Merge Sort)是利用”归并”技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。 一、实现原理: 1、算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的...
  • 本文实例为大家分享了C语言实现归并排序的具体代码,供大家参考,具体内容如下 归并排序的基本思想: 将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并...
  • 二路归并排序和多路归并排序

    千次阅读 2019-10-03 11:48:14
    其实归并排序挺好理解的,也挺好实现的。其实也挺像我们的平常分工合作的。就像一样事情分成几份,由不同的人去做。再合并起来,采用了分治的思想。 对于一个数列,也同是如此。 我们只需要不断地对着中点切分就...
  • 前置知识 归并排序是建立在归并操作...若将两个有序表合并成一个有序表,称为二路归并。 —百度百科 实现代码 #include<iostream> #include<string> #include<stack> #include<algorithm> usin
  • C语言实现二路归并排序
  • C语言递归实现二路归并排序

    千次阅读 2018-08-15 04:56:27
    二路归并意即需要将一个数组分成两个有序部分再归并,分成的两个部分再各自分成两个部分并有序化后再归并,如此往复直到最后每个部分只有1个元素,自然就有序了。这里,我们可以先将一个数组分为两个部分--左半部分...
  • 二路归并排序 子序列长度从1到n/2(把数组划分为2个子序列) 从左往右一次比较2个子序列 非递归实现 子序列长度,h从1开始到?,作2倍变化2h 子序列个数,根据剩余子序列的个数执行相应的操作(剩余子序列个数大于2...
  • 二路归并排序总结

    2022-07-15 14:21:36
    二路归并排序总结(面试常考)
  • 数据结构----二路归并排序

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

    2021-09-28 11:58:38
    若将两个有序表合并成一个有序表,称为2-路归并。 算法描述 把长度为n的输入序列分成两个长度为n/2的子序列; 对这两个子序列分别采用归并排序; 将两个排序好的子序列合并成一个最终的排序序列。 动态演示 代码...
  • C语言二路归并排序算法, 写了个二路归并的归并排序小代码,直接贴上来
  • C++排序算法:归并排序详解

    千次阅读 多人点赞 2022-07-16 12:11:37
    C++排序算法:归并排序详解
  • 直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
  • 本文主要介绍了二路归并排序和一些线性时间排序(计数排序、基数排序和桶排序)。
  • 排序算法之——二路归并排序 二路归并排序的思想: 一次排序过程,将已经各自有序的两个段的数据合并一个段,并且合并后依旧有序 开始,我们认为单个数据是有序的,一个数据就是一个段,一次排序之后,两个数据就是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,629
精华内容 6,251
关键字:

二路归并排序代码