归并排序(MergeSort)(防止标题重复)

我会带着你远行 2022-12-27 07:58 148阅读 0赞

归并排序(MergeSort)  
1 归并排序原理  
分解成最小的记录块(长度为0或1),必须要排序,就是有序块  
然后再归并  
2 归并排序算法的实现

//归并的实现
    //有序子序列R[low...mid]与R[mid + 1...high]归并到S[low...high]
    void Merge(Rcd R[], int low, int mid, int high, Rcd &S[])
    {
        
    	P_left = low;
    	P_right = mid + 1;
    	P_result = low;
    	while (P_left <= mid && P_right <= high)
    	{
        
    		if (R[P_left] <R[P_right])
    		{
        
    			S[P_result] = R[P_left];
    			P_result++;
    			P_left++;
    		}
    		else 
    		{
        
    			S[P_result] = R[P_right];
    			P_result++;
    			P_right++;
    
    		}
    	}
    	while (P_left <= mid)
    	{
        
    		S[P_result] = R[P_left];
    		P_result++;
    		P_left++;
    	}
    	while (P_right <= high)
    	{
        
    		S[P_result] = R[P_right];
    		P_result++;
    		P_right++;
    	}
    }
    //归并排序的对外封装
    void MergeSort(Rcd R[], int low, int high, Rcd &T[])
    {
        
    	//只有一个结点的序列
    	if (low == high) T[low] = R[low];
    	else 
    	{
        
    		mid = (low + high)/2;
    		MergeSort(R, low, mid, S);
    		MergeSort(R, mid + 1, high, S);
    		Merge(S, low, mid, high, T);
    	}
    }

3 总结与推广

发表评论取消回复

表情：

评论列表（有 0 条评论，148人围观）

还没有评论，来说两句吧...

相关阅读

相关作业24-归并排序与基数排序(防止题目重复)

1-3 对N个记录进行归并排序，归并趟数的数量级是O(NlogN)。() \[解析\]归并的数量级在O(logN)? 每上下相邻的两层之间,从上层到下层的过程就是一

太过爱你忘了你带给我的痛/ 2022年12月28日 00:44/ 0 赞/ 194 阅读

相关作业22--插入类与交换类排序(防止标题重复)

1-1 对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。(F) \[解析\]当序列本身就是从大到小排列的时候, 冒泡排序不需

ゝ一世哀愁。/ 2022年12月27日 14:11/ 0 赞/ 119 阅读

相关作业14-Huffman树及其应用(防止标题重复)

1-1 对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。(T) \[解析\]我会想到 \{1,1,3,5\}

r囧r小猫/ 2022年12月27日 09:30/ 0 赞/ 149 阅读

相关 dijkstra算法求最短路(防止标题重复)

1 Dijkstra算法思想首先找距离源点最近的点此点必然是与源点直接相连的点借助邻接矩阵S对应的行, 找最小值即得距离源点最近的点接下来找距

悠悠/ 2022年12月27日 08:42/ 0 赞/ 192 阅读

相关归并排序(MergeSort)(防止标题重复)

归并排序(MergeSort) 1 归并排序原理分解成最小的记录块(长度为0或1),必须要排序,就是有序块然后再归并 2 归并排序算法的实现 //

我会带着你远行/ 2022年12月27日 07:58/ 0 赞/ 149 阅读

相关堆排序-笔记(防止标题重复)

选择类排序简单选择排序:每一趟选出当前最小的记录, 将其交换到无序块的最前面. 如此,无序块逐渐变小,N-1 趟完成 (贪心,递归,动态规划) 引入:每一趟选择

迈不过友情╰/ 2022年12月27日 07:57/ 0 赞/ 130 阅读

相关快速排序-笔记(防止题目重复)

快速排序冒泡排序每次循环,相邻两元素两两比较,不符合则交换,最大元素沉底 //随便写的,好像不对 void BmbleSort(SqList &L)

野性酷女/ 2022年12月27日 07:50/ 0 赞/ 103 阅读

相关【模板】快速排序与归并排序——Template，QuickSort&MergeSort

快速排序 include<iostream> using namespace std; int n,a[1000001]; void qsor

秒速五厘米/ 2022年11月12日 02:51/ 0 赞/ 236 阅读

相关 JavaScript实现MergeSort归并排序算法（附完整源码）

JavaScript实现MergeSort归并排序算法（附完整源码） Comparator.js完整源代码 Sort.js完整源代码 MergeSort

桃扇骨/ 2022年09月07日 09:55/ 0 赞/ 211 阅读

相关 MergeSort

从上往下的归并排序：它与"从下往上"在排序上是反方向的。它基本包括3步： ① 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;

向右看齐/ 2022年06月02日 04:18/ 0 赞/ 102 阅读