-
归并算法
2018-11-04 19:37:33比如说2这个数据在存储上存储的是10,如果现在2变成4,那么存储就变成了100,这个过程需要将2向左移动一位,那么就叫移动一次,如果是2变成8,那么就需要移动2次。在实际运算过程中不会考虑这么细致。 2.归并算法是...归并算法
1.在解释算法优缺点的时候,首先要提到2点,一是比较的次数,二是数据要改变或移动的次数。第一个比较好理解,那什么叫改变和移动的次数呢?比如说2这个数据在存储上存储的是10,如果现在2变成4,那么存储就变成了100,这个过程需要将2向左移动一位,那么就叫移动一次,如果是2变成8,那么就需要移动2次。在实际运算过程中不会考虑这么细致。
2.归并算法是排序算法中的第五种,前四种依次是:冒泡,选择,插入,快速。
3.归并的核心思想是分治。分治顾名思义就是分开治理,假设一个问题,有若干个小问题组成,那么分治就是先逐个击破每个小问题。(有点解高中物理,数学题的感觉)
4.归并算法的解释语言解释:如果你在网上去找一些归并算法的资料学习,那么你可能要茫然到最后不得不靠着阅读代码才能真正理解。所以有必要正真的用文字来描述下归并的全过程,毕竟直接阅读代码是晦涩难懂的。
假设一组数据有8个,一开始将这8个数据两两一组分成4组,然后对每组进行排序,这个地方叫做分治。然后第二次是将8个数据分成两组,每组4个数据,其中这4个数据分别是前两个和后两个已经有序,所以接下来的处理就是按照从左到右的顺序一个一个取出两组有序数据比较排列成一个有序数组,这个数组有4个数据。另外一边4个数据也是同样操作。这样就得到了一个左边和右边都有4个有序数据的数组,再按照以上操作,将这两组数据归并。
5.java代码package algorithm.merge; public class Merge { public static void main(String[] args) { int[] a = new int[]{4, 3, 6, 1, 2, 5, 8, 7}; mergeSort(a, 0, 1); for (int i = 0; i < a.length; ++i) { System.out.print(a[i] + " "); } } /** * 目的是将两个有序列表归并成一个有序表,这是一个分治点 * start 第一个有序表的起始索引 * mid 第二个有序表的起始索引 * end 第二个有序表的结束索引 */ public static void merge(int[] target,int start,int mid,int end){ int[] temp = new int[end-start+1];//一个临时数组,用来存储两个归并好的有序列表 int indexS = start;//第一个有序表的索引 int indexM = mid;//第二个有序表的索引 int indexT = 0;//temp数组的索引 //将两个有序表排列成一个有序表,直到其中的一个表数据取完,这时候将另一个表的剩余数据,一次添加到temp的尾部。 while(indexS<mid && indexM<=end){ if(target[indexS]<target[indexM]){ temp[indexT++] = target[indexS++]; }else{ temp[indexT++] = target[indexM++]; } } //如果第一个表还有数据 while(indexS<mid){ temp[indexT++] = target[indexS++]; } //如果第二个表还有数据 while(indexM<=end){ temp[indexT++] = target[indexM++]; } //将temp替换到原来target数组,从start的往后拷贝temp.length个数据 //这个arraycopy方法是native修饰的,也就是说这个方法是从内存上直接copy的,效率特别高 System.arraycopy(temp, 0, target, start, temp.length); } /** * length 每次归并的列表长度,开始为1 * 从0开始, * 下面的例子按照8个长度数组举例子 */ public static void mergeSort(int[] target,int start,int length){ int size = target.length;//target数组总长度,用于计算分组数 //例如第一次归并长度为1,那么就需要将数组分为4组,每组2个数据归并,所以将length向左移1位,也就是乘以2 int group = size/(length<<1);//向下取整机制,假设是9个数,那么也是4组,就造成第9个数组未参与排序 //当length==8的时候,那么group就等于0,此时结束算法(递归结束); if(group==0){ return; } //循环将group组数据归并 for(int i=0;i<group;++i){ int s = i * 2 * length; //递归调用merge排序 //当i=0时候merge(target,0,1,2); //当i=1时候merge(target,2,3,4); //当i=2时候merge(target,4,5,6); //当i=3时候merge(target,6,7,8); //也就是说当分4组的时候,0-2,2-4,4-6,6-8被分治排序。 merge(target,s,s+length,(length<<1)+s-1); } //用总长度与每组长度取模运算,如果模为0代表数组的长度是2的整数次方,为最乐观情况下 //如果模不为0意味着每次结束的时候余下的数都要与前面所有的数进行一次归并。 //下面注释的代码为常规写法 // int mod = size%(length<<1); // if(mod!=0){ // merge(target,0,(length<<1)*group,target.length-1); // } //下面这段代码功能用途和上面的完全相同 //这段代码运用的是&运算,效率上要高于注释的取模运算(神就在此处体现) //此处的运算,只有当length是2的指数幂时,结果是对的,其他一律错,正好这个地方必然是2的指数幂。 int r = size & ((length << 1) - 1); if (r != 0){ merge(target, size - r - 2 * length, size - r, size - 1); } mergeSort(target,0,length<<1); } }
6.思考的问题 a.当归并的数组长度不是2的指数次幂,是否可以通过补成2的指数次幂运算? b.当归并的数组长度不是2的指数次幂,是否可以去掉多余的数,当其余的归并成功后再插入?
-
python 归并算法
2019-01-13 10:22:17算法和数据结构理解起来是非常痛苦的,而且不是第一次懂了以后还会懂,有可能会忘记!!! 所以先记录一下.防止忘记 def merge_sort( li ): #不断递归调用自己一直到拆分成成单个元素的时候就返回这个元素,不再拆分了 ...算法和数据结构理解起来是非常痛苦的,而且不是第一次懂了以后还会懂,有可能会忘记!!! 所以先记录一下.防止忘记
归并算法 的时间复杂度是n乘以log n 在性能上还算比较优秀的
在理念上就是分封诸侯 ,每个人都给个官当当 然后把所有的官按大小排列def merge_sort( li ): #不断递归调用自己一直到拆分成成单个元素的时候就返回这个元素,不再拆分了 if len(li) == 1: return li #取拆分的中间位置 mid = len(li) // 2 #拆分过后左右两侧子串 left = li[:mid] right = li[mid:] #对拆分过后的左右再拆分 一直到只有一个元素为止 #最后一次递归时候ll和lr都会接到一个元素的列表 # 最后一次递归之前的ll和rl会接收到排好序的子序列 ll = merge_sort( left ) rl =merge_sort( right ) # 我们对返回的两个拆分结果进行排序后合并再返回正确顺序的子列表 # 这里我们调用拎一个函数帮助我们按顺序合并ll和lr return merge(ll , rl) #这里接收两个列表 def merge( left , right ): # 从两个有顺序的列表里边依次取数据比较后放入result # 每次我们分别拿出两个列表中最小的数比较,把较小的放入result result = [] while len(left)>0 and len(right)>0 : #为了保持稳定性,当遇到相等的时候优先把左侧的数放进结果列表,因为left本来也是大数列中比较靠左的 if left[0] <= right[0]: result.append( left.pop(0) ) else: result.append( right.pop(0) ) #while循环出来之后 说明其中一个数组没有数据了,我们把另一个数组添加到结果数组后面 result += left result += right return result if __name__ == '__main__': li = [5,4 ,33 ,2 ,1] li2 = merge_sort(li) print(li2)
-
算法设计与分析-归并算法
2020-08-07 20:34:14归并排序算法是用分支策略对n个元素进项排序的算法,其思想就是对待排序的序列分成最优两个子序列,对左右两个子序列进项排序,一次递归,最后将排好序的左右子序列合并成有序序列。 时间复杂度分析. 算法需要将2个...归并排序算法是用分支策略对n个元素进项排序的算法,其思想就是对待排序的序列分成最优两个子序列,对左右两个子序列进项排序,一次递归,最后将排好序的左右子序列合并成有序序列。
时间复杂度分析.算法需要将2个排好序的数组段到新的数组段中,然后由算法copy将合并后的数组在复制到a数组中,显然都是在O(N)的时间内完成的。故时间复杂度为nlongn。
动画演示排序过程
代码实现
c++版void merge_sort_recursive(int arr[], int reg[], int start, int end) { if (start >= end) return; int len = end - start, mid = (len >> 1) + start; int start1 = start, end1 = mid; int start2 = mid + 1, end2 = end; merge_sort_recursive(arr, reg, start1, end1); merge_sort_recursive(arr, reg, start2, end2); int k = start; while (start1 <= end1 && start2 <= end2) reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]; while (start1 <= end1) reg[k++] = arr[start1++]; while (start2 <= end2) reg[k++] = arr[start2++]; for (k = start; k <= end; k++) arr[k] = reg[k]; } void merge_sort(int arr[], const int len) { int reg[len]; merge_sort_recursive(arr, reg, 0, len - 1); }
java版
public class MergeSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝,不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); if (arr.length < 2) { return arr; } int middle = (int) Math.floor(arr.length / 2); int[] left = Arrays.copyOfRange(arr, 0, middle); int[] right = Arrays.copyOfRange(arr, middle, arr.length); return merge(sort(left), sort(right)); } protected int[] merge(int[] left, int[] right) { int[] result = new int[left.length + right.length]; int i = 0; while (left.length > 0 && right.length > 0) { if (left[0] <= right[0]) { result[i++] = left[0]; left = Arrays.copyOfRange(left, 1, left.length); } else { result[i++] = right[0]; right = Arrays.copyOfRange(right, 1, right.length); } } while (left.length > 0) { result[i++] = left[0]; left = Arrays.copyOfRange(left, 1, left.length); } while (right.length > 0) { result[i++] = right[0]; right = Arrays.copyOfRange(right, 1, right.length); } return result; } }
-
归并算法-MergeSort
2016-12-20 21:17:07归并算法-MergeSort 简单的说就是将要排序的序列分成等量的两份,从中间分开,然后接下来对第一次分出的两个子序列继续按前面的方法分,即对子序列继续用MergeSort的方法递归,然后将两个排序好的子序列通过简单...归并算法-MergeSort简单的说就是将要排序的序列分成等量的两份,从中间分开,然后接下来对第一次分出的两个子序列继续按前面的方法分,即对子序列继续用MergeSort的方法递归,然后将两个排序好的子序列通过简单的比较它们各自的最小值来合并成一个序列,这样就排序好了。编程方面,利用两个函数,一个是用MergeSort方法来递归的mergeSort()函数,一个是讲左右两个子序列进行比较大小并合并成一个序列的Merge()函数。接下来贴上我的C++代码。
注意,如果序列长度不是很大,利用插入排序算法比归并排序算法更快,大约30个数以下用插入排序还是很好的。#include<iostream> #define N 100 void mergeSort(int *a ,int l,int r); void Merge(int *a,int l,int m,int r); int main() { int a[N]; for(int i=0;i<N;i++) { a[i]=rand()%50+1; std::cout<<a[i]<<" "; } std::cout<<std::endl; mergeSort(a,0,N); for(int i=0;i<N;i++) { std::cout<<a[i]<<" "; } std::cout<<std::endl; return 0; } void Merge(int *a, int l, int m, int r) { int n1=m-l+1; int n2=r-m; int *L=new int[n1+1];//+1的含义:放置一个额外的数用来与R比较从而将R剩余比L中都大的数顺利放入a数组中(简称“哨兵”)。 int *R=new int[n2+1];//+1的含义:放置一个额外的数用来与L比较从而将L剩余比R中都大的数顺利放入a数组中(简称“哨兵”)。 int i,j,k; for(i=0;i<n1;i++) { L[i]=a[l+i]; } for(j=0;j<n2;j++) { R[j]=a[m+1+j]; } L[n1]=51;//设置比排序里最大的数还要大就行,这里设置的随机数最大为50,即设置哨兵。 R[n2]=51;//设置比排序里最大的数还要大就行,这里设置的随机数最大为50,即设置哨兵。 for(i=0,j=0,k=l;k<=r;k++){ if(L[i]<R[j]) { a[k]=L[i]; i++; } else { a[k]=R[j]; j++; } } delete [] L; delete [] R; } void mergeSort(int *a,int l,int r) { if(l<r) { int m=(l+r)/2; mergeSort(a, l, m); mergeSort(a, m+1, r); Merge(a,l,m,r); } }
-
算法学习---归并算法简单记录
2020-10-29 23:55:55归并算法思想记录1、核心思想2、应用算法复杂度 1、核心思想 将难以一次性解决的原始问题(大问题),分割为较为容易处理的小问题(此步骤一般递归、迭代均可实现),计算结果; 然后将小问题的计算结果合并(汇聚... -
javaScript归并算法小记
2020-08-04 01:01:491、首先简述一下原理,其实原理就是我们小学学过的分而治之的思想,先将一个大问题分开成很多小问题,然后再将小问题合起来,组成大问题,那么大问题就被...归并排序以程序稳定性为主,因为我们可以提前得知排序的次 -
归并算法与二分排序
2020-09-25 20:58:26一,归并算法 思想:先将原序列经过多次对半,分解为单个元素,每次对半分均分为左边序列与右边序列。然后再将一个个单个元素,合并起来。也采用两两合并的方式,合并过程中由左指针与右指针控制,判断两个指针代表... -
归并排序算法解析
2012-06-25 17:38:29一次归并算法 1、基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回 -
分治法分析归并 算法
2020-03-02 09:04:29分治法的定义 两个注意点 减治法和分治法对比 ...这里合并的最好情况是 左边的一组元素比右边的都小或都大 — 对应比较n/2次 合并的最坏情况是两个序列中交替出现数据大小— 对应比较n-1次 ... -
归并算法Python3.7实现及时间复杂度分析
2019-10-22 20:45:07归并排序是由冯诺依曼首次提出,该算法采取的是分而治之(Divide and Conquer)的思想,速度仅次于快速排序且为稳定算法,适合的排序情况...从上图就可以看出归并算法的流程: 将原始序列分为2个子序列 再将2个子... -
归并选择算法
2020-03-21 19:21:50两列排好序的数据 归并为一列,这边称为归并数,图中每两个红箭头归并为一个归并次数 共有9个归并次数,两次复制 void Merge(T *initList,T *mergeList, const int l ,const int m, const... -
Python算法学习day7:归并排序
2020-01-19 20:11:19归并排序 1. 一次归并 假设现在的列表分两段有序, 如何将其合成为一个...2. 一次归并算法实现 def merge(li, low, mid, high): i = low j = mid + 1 li_tmp = [] while i <= mid and j <= high: if li[... -
自顶向下分治实现的归并算法
2016-06-28 11:28:56归并排序在排序算法中对于较大数组是复杂度低于插入排序等算法,代码中merge为一趟归并,合并两个已排序好的子数组,即将两个待排序数组作比较,依次将较小的数放入新的数组,重复此步骤直到一个子数组为空,然后... -
归并排序算法解析(转)
2013-01-15 21:42:14归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,...一次归并算法 1、基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low -
归并排序算法
2019-08-03 14:09:23归并排序算法 1. 分阶段: ...再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1, 2... -
海量数据排序,多路平衡归并算法及实现(外部文件排序算法)
2015-04-14 21:49:42外部文件多路平衡归并类似于内部排序的归并算法。可知增加分段个数k可以减少归并次数s,从而减少外存读写次数,但是单纯增加k将会导致增加内部归并的时间。 对于k-路归并,令u个记录分布在k个归并段上,显然,归并... -
算法之归并排序算法
2015-05-23 17:23:38许多有用的算法在数据结构上市递归的:为了解决一个给定的问题,算法一次或多次用其自身来解决紧密相关的若干子问题。这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归的... -
二分归并排序算法_排序算法:归并排序
2020-12-06 13:01:45概述 上一次介绍了排序算法中效率很高的“快速排序”。本文将继续介绍另一个高效的排序算法——“归并排序”。基本思想归并排序的主要思想是分治法。主要过程是:将n个元素从中间切开,分成两部分。(左边可能比右边... -
排序算法之四归并排序
2013-04-17 21:18:141:归并排序算法 #include ...//1一次归并算法 void Merge(int r[],int s,int m,int t) { int i,j,k,n1,n2; n1=m-s+1; n2=t-m; int *left=NULL, *right=NULL; left = (int *)malloc(sizeof(i -
算法分析与设计第四次作业-二分归并排序算法
2020-03-22 14:00:34有序归并算法递归实现 1. 问题 2. 解析 1、首先我们有一个将两段有序序列合并起来的函数Merge;类似链表的有序链表的合并,我们用L(初始化传入为左边起点索引)代表目前所指向左边序列的位置,R同理。我们用while... -
C语言归并排序算法.docx
2020-01-08 07:38:08C语言归并排序算法 用归并排序法对一组数据由小到大进行排序数据分别为 69545836278912 15163232986 实现过程 (1) 自定义函数 merge)实现一次归并排序 (2) 自定义函数 merge_sort)实现归并排序 (3) 程序代码如下 #... -
【算法知识】详解归并排序算法
2020-04-29 11:00:00已发布:【算法知识】详解选择冒泡算法【算法知识】详解选择排序算法【算法知识】详解插入排序算法【算法知识】详解快速排序算法基本思想 归并排序的基本思想是:先将序列一次次分成子序列,直到子序... -
python3利用归并算法对超过内存限制的超大文件进行排序
2020-07-19 12:36:17所谓的大文件就是无法一次性全部读到内存中的文件。 为了操作不真的把我机器的内存都榨干,这里假设机器的内存是300MB,刨除一些系统占用,规定每次读到内存的文件大小不能超过200MB。 我又用下面的程序创建了一个... -
归并排序算法分析
2020-10-25 10:36:39 利用分治的思想,每一次把原数组分为两份,再进行对子数组进行排序,最后对排好序的数组进行合并,形成一个新的有序序列。 1.1执行过程 2、实现步骤 2.1 mergeSort()方法 public static void mergeSort(int... -
二分归并排序算法_排序算法之归并排序
2020-12-06 01:28:00一、分治模式许多有用的算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但类似于原问题的... -
归并算法的改进与简化设计与实现
2012-09-30 13:12:19归并算法的思想是把待排序的数逐级递归拆分成一棵树然后在从根像上合并,但是每次合并的过程都需要进行一次排序。因此我想到一个方法,在原来拆分的基础上加以改进,让合并过程去掉排序步骤,最后直接合并得到排好序...