精华内容
下载资源
问答
  • 归并排序 详解

    万次阅读 多人点赞 2018-05-30 13:38:53
    下面我们来看归并排序的思路(先讲思路再来具体讲归并的细节): 归并排序(Merge Sort) 当我们要排序这样一个数组的时候,归并排序法首先将这个数组分成一半。如图: 然后想办法把左边的数组给排序,右边的数组给...

    注:内容,图片来自于慕课网liuyubobobo老师的课程。

    官方代码链接:https://github.com/liuyubobobo/Play-with-Algorithms

    算法复杂度:O(nlogn)

    也许有很多同学说,原来也学过很多O(n^2)或者O(n^3)的排序算法,有的可能优化一下能到O(n)的时间复杂度,但是在计算机中都是很快的执行完了,没有看出来算法优化的步骤,那么我想说有可能是你当时使用的测试用例太小了,我们可以简单的做一下比较:

     

    当数据量很大的时候 nlogn的优势将会比n^2越来越大,当n=10^5的时候,nlogn的算法要比n^2的算法快6000倍,那么6000倍是什么概念呢,就是如果我们要处理一个数据集,用nlogn的算法要处理一天的话,用n^2的算法将要处理6020天。这就基本相当于是15年。一个优化改进的算法可能比一个比一个笨的算法速度快了许多,这就是为什么我们要学习算法。

    核心思想:分治。

    下面我们来看归并排序的思路(先讲思路再来具体讲归并的细节)

     

    归并排序(Merge Sort)

     

     

     

     

    当我们要排序这样一个数组的时候,归并排序法首先将这个数组分成一半。如图:

     

     

     

    然后想办法把左边的数组给排序,右边的数组给排序,之后呢再将它们归并起来。当然了当我们对左边的数组和右边的素组进行排序的时候,再分别将左边的数组和右边的数组分成一半,然后对每一个部分先排序,再归并。如图:

     

     

     

    对于上面的每一个部分呢,我们依然是先将他们分半,再归并,如图:

     

     

     

    分到一定细度的时候,每一个部分就只有一个元素了,那么我们此时不用排序,对他们进行一次简单的归并就好了。如图:

     

     

     

    归并到上一个层级之后继续归并,归并到更高的层级,如图:

     

     

     

    直至最后归并完成。

     

     

     

    那么如何归并呢?我们是否可以用O(n)的算法将两个数组归并到一起形成一个数组呢?如果可以的话,我们将可以用递归的过程来实现整个归并。这是你想起来很简单但是操作起来并不是那么简单的问题。

     

     

    归并细节:

    比如有两个已经排序好的数组,如何将他归并成一个数组?

    我们可以开辟一个临时数组来辅助我们的归并。也就是说他比我们插入排序也好,选择排序也好多使用了存储的空间,也就是说他需要o(n)的额外空间来完成这个排序。只不过现在计算机中时间的效率要比空间的效率重要的多。无论是内存也好还是硬盘也好可以存储的数据越来越多,所以设计一个算法,时间复杂度是要优先考虑的。

     

     

     

    整体来讲我们要使用三个索引来在数组内进行追踪。

     

     

     

     

     

     

    蓝色的箭头表示最终选择的位置,而红色的箭头表示两个数组当前要比较的元素,比如当前是2与1比较,1比2小,所以1放到蓝色的箭头中,蓝色的箭头后移,1的箭头后移。

     

     

     

     

     

    然后2与4比较,2比4小那么2到蓝色的箭头中,蓝色箭头后移,2后移,继续比较.......

     

     

    归并思路就是这样了,最后唯一需要注意的是那个先比较完的话,那么剩下的直接不需要比较,把后面的直接移上去就可以了,这个需要提前判定一下。

     

    归并排序代码如下:

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    
    void merge(int a[],int l,int r,int mid)
    {
      int aux[r-l+1],i,j,k;
      
      for(k=l;k<=r;k++)
      aux[k-l]=a[k];
      
      i=l;
      j=mid+1;
      for(k=l;k<=r;k++)
      {
      	if(i>mid)
      	{
      		a[k]=aux[j-l];
      		j++;
    	  }
    	else if(j>r)
    	{
    		a[k]=aux[i-l];
    		i++;
    	  }
    	else if(aux[i-l]>aux[j-l])
    	{
    		a[k]=aux[j-l];
    		j++;
    		}
    	else
    	{
    		a[k]=aux[i-l];
    		i++;
    			}
    				    
      	
    	  }	
    	
    }
    
    void merge_sort(int a[],int l,int r)
    {
        if(l>=r)
    	return ;
    	
    	int mid=(l+r)/2;
    	
    	merge_sort(a,l,mid);
    	merge_sort(a,mid+1,r);
    	merge(a,l,r,mid);	
    	
    }
    
    
    void mergesort(int a[],int l,int r)
    {
    	merge_sort(a,l,r-1);
    }
    
    int main()
    {
    	int a[105],n,i;
    	scanf("%d",&n);
    	
    	for(i=0;i<n;i++)
    	scanf("%d",&a[i]);
    	
    	mergesort(a,0,n);
    	
    	for(i=0;i<n;i++)
    	printf("%d ",a[i]);
    	
    	
    	return 0;
     } 

     

     

     

    展开全文
  • 归并排序

    万次阅读 2018-05-17 23:00:25
    归并排序归并排序(MERGE-SORT) 是一种分治算法,是建立在归并操作上的一种有效的排序算法。常用的 2 路归并排序假设初始序列有 n 个记录,可以看成是 n 个长度为 1 的子序列,进行两两归并,可以得到 n / 2 个长度为...

    归并排序

    归并排序(MERGE-SORT) 是一种分治算法,是建立在归并操作上的一种有效的排序算法。常用的 2 路归并排序假设初始序列有 n 个记录,可以看成是 n 个长度为 1 的子序列,进行两两归并,可以得到 n / 2 个长度为 2 或 1 的子序列;再两两归并,******,直到得到一个长度为 n 的有序序列为止。

    归并排序的时间复杂度是 O(nlogn),是一种效率高且稳定的算法。

     

     

    基本思想

     

      归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

    分而治之

       可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。

     

    合并相邻有序子序列

     

      再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

     

    具体代码实现:

     

     

    import java.util.Arrays;
    
    public class SortTest {
    
        public static void main(String[] args) {
            int[] arr = {14, 12, 4, 6, 9, 16, 11, 8, 3, 1,18};
            /* 在排序前。先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间 */
            int[] tmp = new int[arr.length];
            mergeSort(arr,0,arr.length-1,tmp);
            for (int x : arr){
                System.out.print(x+", ");
            }
        }
        /*
            归并排序(从小到大)
        */
        public static void mergeSort(int[] array, int start, int end,int[] tmp) {
            if (start >= end){
                return;
            }
            int middle = ((end + start) >> 1);
            /* 左边归并排序,使得左子序列有序 */
            mergeSort(array, start, middle, tmp);
            /* 右边归并排序,使得右子序列有序 */
            mergeSort(array, middle + 1, end, tmp);
            /* 对有序的两个数组进行合并成一个有序的数组 */
            mergeArray(array, start, middle, end, tmp);
        }
    
        private static void mergeArray(int[] array, int start, int middle, int end,int[] tmp) {
    
            int first = start;
            int second = middle + 1;
            int index = start;
            while ((first <= middle) && (second <= end)) {
                if (array[first] >= array[second])
                    tmp[index++] = array[second++];
                else
                    tmp[index++] = array[first++];
            }
            while (first <= middle){
                tmp[index++] = array[first++];
            }
            while (second <= end){
                tmp[index++] = array[second++];
            }
            for (first = start; first <= end; first++){
                array[first] = tmp[first];
            }
            System.out.println("merge is "+Arrays.toString(array));
        }
    
        /*
            交换角标为x,y在数组的位置
         */
        private static void swap(int[] arr, int x, int y){
            int temp;
            temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;
        }
    }
    

     

     

     

    展开全文
  • 归并算法归并算法

    2012-04-17 00:48:19
    归并算法
  • 归并排序,同样是利用分治思想的典型算法例子,下面简单总结下归并排序。一、归并的概念归并是这样一种概念,它针对两个或者多个有序的数组,是合并这多个有序数组并进行排序的一种手段,它的主要处理方法是每次都找...

    归并排序,同样是利用分治思想的典型算法例子,下面简单总结下归并排序。

    一、归并的概念

    归并是这样一种概念,它针对两个或者多个有序的数组,是合并这多个有序数组并进行排序的一种手段,它的主要处理方法是每次都找出比较各个数组的首个元素(假设从左边开始排序而且是升序的方式),找出他们之间的最小值,将其拷贝到一个新的数组上,依次类推直到所有元素处理完,看说明图:

    90637faf0578def77f6bf6bf11e3fbb1.png

    归并很好地利用了两个数组均是有序的这个条件,合并两个数组,大概只需要2n次比较即可(n是较小数组的长度),下面贴上归并的算法代码:

    //归并方法

    public static void mergeAB(int [] arrA,int [] arrB,int[] arrC){

    //循环遍历两个需要归并的数组

    for(int a=0,b=0,c=0;c

    //判断两个数组是否对应遍历完成

    if(a==arrA.length){

    //遍历完成A数组,则对应B中的元素只需要直接复制到C数组中

    arrC[c++] = arrB[b++];

    continue;

    }

    if(b==arrB.length){

    arrC[c++] = arrA[a++];

    continue;

    }

    //如果两个数组都没有遍历完,则进行比较操作

    arrC[c++] = arrA[a]

    }

    }

    二、归并排序

    归并排序是利用分治的思想进行递归归并的过程,递归过程不断对数组进行拆分,直到可以直接归并为止(可以认为是要处理的元素只有两个元素的时候,也可以认为是一个元素的时候)。其实理解了分治思想,归并排序理解起来还是挺简单的,下面简单贴上算法:

    //归并排序方法

    public static int [] guiBingSort(int [] arr,int l,intr){

    //确定递归停止条件

    if(l==r){

    return new int[]{arr[r]};

    }

    //分两部分进行递归操作

    int [] result1 = guiBingSort(arr, l, l+(r-l)/2);

    int [] result2 = guiBingSort(arr, l+(r-l)/2+1, r);

    //result1和result是已经排好序的数组,进行归并操作即可

    int [] rtn = new int[result1.length +result2.length];

    mergeAB(result1, result2, rtn);//调用归并方法

    //返回归并结果

    returnrtn;

    }

    三、归并排序的特征

    归并排序大概有一下特征:

    1、它是稳定的排序算法,不改变元素之间的相对位置;

    2、归并排序的比较次数和元素的初始顺序无关,而且都是nlogn次;

    3、归并排序需要的内存空间是N的常数倍,所以它比较消耗内存空间。

    展开全文
  • 白话经典算法系列之五 归并排序的实现

    万次阅读 多人点赞 2011-08-11 11:01:05
    归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取...

     归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

    首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

    //将有序数组a[]和b[]合并到c[]中
    void MemeryArray(int a[], int n, int b[], int m, int c[])
    {
    	int i, j, k;
    
    	i = j = k = 0;
    	while (i < n && j < m)
    	{
    		if (a[i] < b[j])
    			c[k++] = a[i++];
    		else
    			c[k++] = b[j++]; 
    	}
    
    	while (i < n)
    		c[k++] = a[i++];
    
    	while (j < m)
    		c[k++] = b[j++];
    }

    可以看出合并有序数列的效率是比较高的,可以达到O(n)。

    解决了上面的合并有序数列问题,再来看归并排序,其的基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了?

    可以将A,B组各自再分成二组。依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。这样通过先递的分解数列,再合数列就完成了归并排序。

    //将有二个有序数列a[first...mid]和a[mid...last]合并。
    void mergearray(int a[], int first, int mid, int last, int temp[])
    {
    	int i = first, j = mid + 1;
    	int m = mid,   n = last;
    	int k = 0;
    	
    	while (i <= m && j <= n)
    	{
    		if (a[i] <= a[j])
    			temp[k++] = a[i++];
    		else
    			temp[k++] = a[j++];
    	}
    	
    	while (i <= m)
    		temp[k++] = a[i++];
    	
    	while (j <= n)
    		temp[k++] = a[j++];
    	
    	for (i = 0; i < k; i++)
    		a[first + i] = temp[i];
    }
    void mergesort(int a[], int first, int last, int temp[])
    {
    	if (first < last)
    	{
    		int mid = (first + last) / 2;
    		mergesort(a, first, mid, temp);    //左边有序
    		mergesort(a, mid + 1, last, temp); //右边有序
    		mergearray(a, first, mid, last, temp); //再将二个有序数列合并
    	}
    }
    
    bool MergeSort(int a[], int n)
    {
    	int *p = new int[n];
    	if (p == NULL)
    		return false;
    	mergesort(a, 0, n - 1, p);
    	delete[] p;
    	return true;
    }

     

    归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度可以记为O(N),故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在O(N*logN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)也是效率比较高的。

     

    在本人电脑上对冒泡排序,直接插入排序,归并排序及直接使用系统的qsort()进行比较(均在Release版本下)

    对20000个随机数据进行测试:

    对50000个随机数据进行测试:

    再对200000个随机数据进行测试:

     

    注:有的书上是在mergearray()合并有序数列时分配临时数组,但是过多的new操作会非常费时。因此作了下小小的变化。只在MergeSort()中new一个临时数组。后面的操作都共用这一个临时数组。

     

     

    展开全文
  • 一、归并排序 1、介绍。 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每...
  • 本篇文章讲解三个高级排序算法,分别为希尔排序、归并排序、快速排序。虽然它们的思想很复杂,但真的运用得非常得巧妙,我会用丰富的例子以及动图来让大家轻松地理解并掌握。
  • C语言实现数据结构之归并排序

    万次阅读 2018-09-19 09:48:21
    C/C++实现数据结构之2路-归并排序 归并排序和交换排序、选择排序的思想不一样,归并的含义是将两个或两个以上的有序表组合成一个新的有序表。假定待定排序表含有n个记录,则可以看成是N个有序的子表。每个子表长度为...
  • 归并归并排序

    2017-05-17 14:37:28
    归并排序,同样是利用分治思想的典型算法例子,下面简单总结下归并排序。 一、归并的概念  归并是这样一种概念,它针对两个或者多个有序的数组,是合并这多个有序数组并进行排序的一种手段,它的主要处理方法...
  • 归并排序 改进归并

    2018-11-13 16:09:16
    归并排序 归并排序的主要思想是:分治(divide-and-conquer)策略,首先是分,先把问题拆分成规模很小的问题;然后是治,将子问题的答案合并成一个更大的小问题的答案,直到合并成问题本身的答案。 分解的过程就是...
  • 归并归并排序

    千次阅读 2015-03-29 18:22:33
    归并操作:是将两个有序独立的文件合并成为一个有序文件的过程。 归并排序:和快速排序的过程相反,它是两个递归调用(排序子文件)后是一个归并的过程。 快速排序时,先分解成两个子问题后是两个递归调用(排序子...
  • 排序9.5 归并排序9.5.1 归并9.5.2 两路归并排序9.5.3 递归的归并排序总结 9.5 归并排序 9.5.1 归并 所谓归并,就是将两个或两个以上的有序表合并成一个新的有序表。有两个已经排好序的有序表A[1]~ A[n]和 B[1]~ B[m...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 56,060
精华内容 22,424
关键字:

归并