精华内容
下载资源
问答
  • 归并排序 递归算法

    千次阅读 2018-10-23 22:51:49
    利用递归思想将数组一直划分为要排序的另一半,最后就回将问题化简为相邻两个数的排序,然后将排好序的数组归并到一个数组中,然后继续向上递归直至排序完成。   int a[10]={15, 18, 45, 96, 23, 58, 75, 1, ...

    数组排序任务可以如下完成:

    (1):将前一半排好序

    (2):将后一半排好序

    (3):把两半归并到一个新的有序数组中,然后再拷贝回原来的数组,排序完成

    利用递归思想将数组一直划分为要排序的另一半,最后就回将问题化简为相邻两个数的排序,然后将排好序的数组归并到一个数组中,然后继续向上递归直至排序完成。

     

    int a[10]={15, 18, 45, 96, 23, 58, 75, 1, 52, 69};

    将排好序的数组先存储在b数组中,然后将b数组中的数字按顺序放入a数组中。
    int b[10];

    int main()
    {
        int size = sizeof(a) / sizeof(int);
        
        Mergesort(a, 0, size - 1, b);
        
        for(int i = 0; i < size; i++)
        { 
            cout << a[i] << ",";
        } 
        cout << endl;
        return 0;
    }


    将两个排好序的数组归并到一个数组中


    void Merge(int a[], int s, int m, int e, int tmp[])
    {//将数组a的局部a[s,m]和a[m+1,e]合并到tmp,并保证tmp有序,然后再拷贝回a[s,m]
     //归并操作时间复杂度:O (e-m+1),即 O(n) 
        
        int pb = 0;
        int p1 = s, p2 = m+1;
        
        while(p1 <= m && p2 <= e)
        {
            if(a[p1] < a[p2])
            { 
               tmp[pb++] = a[p1++];
            } 
            else
            { 
               tmp[pb++] = a[p2++];
            } 
        }
        
        while(p1 <= m)
        {
            tmp[pb++] = a[p1++];
        }
        while(p2 <= e)
        {
            tmp[pb++] = a[p2++];
        }
        
        for(int i = 0; i < e - s + 1; i++)
        {    
            a[s + i] = tmp[i];
        }
    }


    void Mergesort(int a[], int s, int e, int tmp[])
    {
        if(s < e)
        {
            int m = s + (e-s) / 2;
            
            Mergesort(a, s, m, tmp);
            Mergesort(a, m+1, e, tmp);
            Merge(a, s, m, e, tmp); 
        }  
    }
     

    展开全文
  • 归并排序递归算法

    千次阅读 2014-02-02 16:02:13
    归并排序的思想: 假设初始序列含有n个记录,则可以看成是n个 有序的子序列,每个子序列的长度为1,然后两两 归并,得到n/2个长度为1或者2的有序子序列 在两两归并,如此重复,直到一个长度为n的有序 序列为止...

    归并排序递归算法

    /*
     归并排序的思想:
     假设初始序列含有n个记录,则可以看成是n个
     有序的子序列,每个子序列的长度为1,然后两两
     归并,得到n/2个长度为1或者2的有序子序列
     在两两归并,如此重复,直到一个长度为n的有序
     序列为止
     */
    #include<cstdio>
    #define MAX 1000
    
    typedef struct seeqlist
    {
    	int Array[MAX];
    	int length;
    }SeqList;
    
    void Merge(int S[],int T[],int i,int m,int n)
    {
    	int j,k;
    	for(j=m+1,k=i;i<=m&&j<=n;k++)
    	{
    		if(S[i]<S[j])
    			T[k]=S[i++];
    		else
    			T[k]=S[j++];
    	}
    	if(i<=m)//将剩余的S[i..m]合并到T中
    	{
    		for(;i<=m;i++)
    			T[k++]=S[i];
    	}
    	if(j<=n)//将剩余的S[j..n]合并到T中
    	{
    		for(;j<=n;j++)
    			T[k++]=S[j];
    	}
    }
    
    void Msort(int S[],int T[],int s,int t)
    {
    	int T2[MAX];
    	int m;
    	if(s==t)
    		T[s]=S[s];
    	else
    	{
    		m=(s+t)/2;//将S[s..t]平分成S[s..m]和S[m+1..t]
    		Msort(S,T2,s,m);//递归将S[s..m]归并为T2[s..m]
    		Msort(S,T2,m+1,t);///递归将S[m+1..t]归并为T2[m+1..t]
    		Merge(T2,T,s,m,t);//合并
    	}
    }
    
    void MergeSort(SeqList *L)//只是为了保持传参的一致性
    {
    	Msort(L->Array,L->Array,1,L->length);
    }
    
    int main(int argc,char *argv[])
    {
    	int i;
    	SeqList L;
    	scanf("%d",&L.length);
    	for(i=1;i<=L.length;i++)
    		scanf("%d",&L.Array[i]);
    	MergeSort(&L);
    	printf("After Sort:\n");
    	for(i=1;i<=L.length;i++)
    		printf("%4d",L.Array[i]);
    	printf("\n");
    
    	return 0;
    }
    
    



    展开全文
  • //归并排序前半个子序列 MergeSort(r, r2, r1, m+1, t); //归并排序后半个子序列 Merge(r2, r1, s, m, t); //将两个已排序的子序列归并 } } void Merge(int r[],int r1[],int s,int m,int t) { int i; int...
    #include <stdio.h>
    #define M  5
    void MergeSort(int r[],int r1[],int r2[],int s,int t);
    void Merge(int r[],int r1[],int s,int m,int t);
    
    int main()
    {
    
     int i;
     int r[M];
     int r1[M];
     int r2[M];
    
     for(i = 0; i < M; i ++)
     {
      scanf("%d",&r[i]);
     }
    
        MergeSort(r,r1,r2,0,M-1);
    
    
     for(i = 0; i < M; i ++)
     {
      printf("%d/n",r1[i]);
     }
    
     return 0;
    }
    
    void MergeSort(int r[],int r1[],int r2[],int s,int t)
    {
     if(s == t)
     {
      r1[s] = r[s];
     }
     else
     {
      int m;
      m = (s + t)/2;
      MergeSort(r, r2, r1, s, m);        //归并排序前半个子序列  
            MergeSort(r, r2, r1, m+1, t);      //归并排序后半个子序列
            Merge(r2, r1, s, m, t);             //将两个已排序的子序列归并
      
     }
    }
    
    void Merge(int r[],int r1[],int s,int m,int t)
    {
     int i;
     int j;
     int k;
     i = s;
     j = m + 1;
     k = s;
     while(i <= m && j <= t)
     {
      if(r[i] <= r[j])
      {
       r1[k] = r[i];
       k++;
       i++;
      
      }
      else
      {
       r1[k] = r[j];
                k++;
       j++;
      
      }
    
    
     }
    
     if(i <= m)
     {
      while(i <= m)
      {
       r1[k] = r[i];
       k++;
       i++;
      }
     }
     else
     {
      while(j <= t)
      {
       r1[k] = r[j];
       k++;
       j++;
    
       
      }
     }
     
    }
    


     

    展开全文
  • 下面是用Java实现的归并排序算法,参考了Thomas H. Cormen著写的Algorithms Unlocked我看了一些其他博主的博文,我觉得有些细节是可以优化的,比如说避免数组长度过长发生溢出,在求mid的时候可以用 mid = low + ...

    下面是用Java实现的归并排序算法,参考了Thomas H. Cormen著写的Algorithms Unlocked

    我看了一些其他博主的博文,我觉得有些细节是可以优化的,比如说避免数组长度过长发生溢出,在求mid的时候可以用 mid = low + (high - low) / 2

    再比如说创建临时数组的时候可以不用创建一个(high - low + 1)长的数组,而可以只创建长度为一半的前一半 array[low…mid]

    这些小细节优化以后可以扩大计算的上限,并减少一半的空间使用。

    package sort_and_search;

    import java.util.Random;

    public class MergeSort {

    public static void mergeSort(int[] array, int low, int high) {

    int mid = low + (high - low) / 2;// mid = (high + low)/2的另一种算法,避免溢出

    if(low < high) {

    mergeSort(array, low, mid); // 对array[low…mid]归并排序

    mergeSort(array, mid+1, high); // 对array[mid+1…high]归并排序

    mergeArray(array, low, mid, high);// 融合

    }

    return;

    }

    public static void mergeArray(int[] array, int low, int mid, int high) {

    int[] temp = new int[mid-low+1]; //创建临时数组,只需要创建前一半即可

    for(int i = 0, j = low; i < temp.length; i++, j++) {

    temp[i] = array[j]; //对临时数组进行赋值

    }

    int i = 0, j = mid+1, m = low;

    while(i < temp.length && j <= high) { //将两个有序数组归并

    if(temp[i] <= array[j]) { //小于等于是为了维持稳定性

    array[m] = temp[i];

    i++; m++;

    continue;

    }

    else {

    array[m] = array[j];

    m++; j++;

    continue;

    }

    }

    while(i < temp.length) //最后将剩余的元素填充

    array[m++] = temp[i++];

    /*while(j <= high)

    array[m++] = array[j++];

    这一步其实可以不用做,因为此时array[j]==array[m]

    */

    }

    public static void main(String[] args) {

    Random random = new Random();

    int []array = new int[50];

    System.out.println("We randomly create an array, the array is below: ");

    for (int i = 0; i < array.length; i++) {

    array[i] = random.nextInt(500);//生成500以内的随机数

    System.out.print(array[i]+" ");

    }System.out.println();

    System.out.println("After selection sort, the answer is: ");

    mergeSort(array, 0, array.length-1);

    for (int i : array) {

    System.out.print(i+" ");

    }System.out.println();

    }

    }

    初学算法,水平有限,有错误还请指正。

    展开全文
  • 文章目录1. 基本思想2. 代码实现2.1 递归实现2.2 优化—非递归实现3...归并排序与快速排序的思想基本一致,唯一不同的是归并排序的基准值是数组的中间元素 快排 Link:[排序算法] 6. 快速排序多种递归、非递归实现及性能
  • 最近梳理了下归并排序递归、非递归、以及自然归并排序算法归并排序的基础:将两个有序数组合并为一个有序数组,需要O(n)的辅助空间。 图片来自:https://www.cnblogs.com/chengxiao/p/6194356.html ...
  • 归并排序递归算法原理上看, 对排序数组不断递归两分,当递归到最底层时,实质上是把数据分成两个或单个的组,对两个一组的数据又分成左右两半,然后合并排序,这样凡是两个一组的元素都成排序状态.至于单个数据...
  • 思想: 归并排序用的思想是分治法,不治为治,即将待排序的数组分开,当最后基数为一个元素之后再进行治,治理的时候使用临时空间数组来辅助排序,比如:两个元素判断大小,小的放在左边,排序好了之后以基数为两个...
  • 归并排序非递归 二分思想,从归并两个长度为1的开始,向上递归2 4 8...public class 归并排序递归 { static int n; static final int max=100; static int[] a=new int[max]; static int[] b=new int[max]; st...
  • 归并排序递归递归算法 merge算法及辅助空间优化 原地排序算法详解 运行效率分析 1、归并排序递归&非递归算法 递归 先划分,再合并 private void mergeByRecursion(int[] array,int begin,int end){ if(begin...
  • 文章目录1.选择排序2....归并排序4.递归排序算法 1.选择排序 时间复杂度:T(N)=O(N^2) 2.堆排序 对选择排序的改进。 3.归并排序 4.递归排序算法 利用了有序子列的归并 时间复杂度:T(N)=O(N logN) ...
  • 归并排序递归算法

    千次阅读 2014-02-02 16:05:05
    归并排序递归算法 #include #include #define MAX 1000 typedef struct seeqlist { int Array[MAX]; int length; }SeqList; void Merge(int S[],int T[],int i,int m,int n) { int j,k; for(j=m+1,k=i;i;k+
  • 文章目录快速排序原理代码优化方法归并排序原理代码优化方法 快速排序 不稳定 原理 从待排序区间选择一个数,作为基准值(pivot); Partition: 遍历整个待排序区间,将比基准值小的(可以包含相等的)放到基准值的...
  • 我们这么理解,我们知道当一个列表越长我们进行排序消耗就越大,那么我们把这个列表分为无数个小的列表,然后对他们进行排序,然后再组合,那么也会节省不少精力 我们直接看代码 首先我们的第一步是 分: merger...
  • 基本思路: 归并排序(MERGE-SORT)... //归并排序递归体,把整个序列递归分为两个长度为1的子序列,然后对其子序列进行比较归并。得到有序子序列 public static void MergeSort(int []array,int left,int right){ if
  • 8645归并排序(非递归算法) 时间限制:1000MS 内存限制:1000K 题型: 编程题语言: 无限制 Description 用函数实现归并排序(非递归算法),并输出每趟排序的结果 Input 第一行:键盘输入待排序关键的...
  • 归并排序递归详解

    2020-07-24 11:37:12
    归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 分治法将问题分(divide)成一些小的问题利用递归求解,治(conquer)是将分的阶段...
  • 归并排序递归算法

    千次阅读 2012-01-10 16:49:07
    递归算法有个关键就是递归结束的条件。代码如下:  //bugs:算法中有个小bug,就是我没有考虑到(n+1)/2时,n+1为奇数的情况。 #include #include #define MAX 1000 //函数原型 void swap(int *a,int *b); void ...
  • 名称:归并排序 递归调用 自顶向下 描述:将数组arr的从p到r进行排序. merge负责进行将两个已经排序的函数进行归并 flag=0 从小到大排序 flag=非0 从大到小排序 算法复杂度: n*logn 时间:15.7.11 Jason Zhou 热爱你...
  • 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段...
  • 递归算法相对来讲更好理解些,采用分治法进行实现,在拆分的元素个数小于三个的时候进行排序。这里first,last和mid都为数组元素的下标值。 private void mergeSort1(int[] src, int temp[], int first, int last) {...
  • 主要介绍了C#递归算法中的归并排序,需要的朋友可以参考下。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,120
精华内容 2,048
关键字:

归并排序递归算法