精华内容
下载资源
问答
  • 归并排序(Mergesort,台湾译做:合并排序)是创建在归并操做上的一种有效的排序算法。该算法是采用分治法(DivideandConquer)的一个很是典型的应用。算法算法步骤:数组1.申请空间,使其大小为两个已经排序序列之和,...

    归并排序(Merge sort,台湾译做:合并排序)是创建在归并操做上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个很是典型的应用。算法

    算法步骤:数组

    1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列ide

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

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

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

    5. 将另外一序列剩下的全部元素直接复制到合并序列尾code

    9d6a69c65fef46152e2f53d3737e0018.png

    以上理论归理论,代码要实现其实仍是有难度的,本身搞了好久才基本弄清楚非递归的归并排序的基本思想,查阅许久才看懂代码,本身简单地实现了一下:blog

    #define A_LENGTH 10

    #include

    #include

    int MergeSort(int *a)

    {

    int k = 1;/*k用来表示每次k个元素归并*/

    int *temp = (int *)malloc(sizeof(int) * A_LENGTH);

    while (k < A_LENGTH)

    {

    //k每次乘以2是遵循1->2->4->8->16的二路归并元素个数的原则

    MergePass(a, temp, k, A_LENGTH);/*先借助辅助空间归并*/

    k *= 2;

    MergePass(temp, a, k, A_LENGTH);/*再从辅助空间将排过序的序列归并回原数组*/

    k *= 2;

    }

    }

    int MergePass(int *S, int *T, int times, int length)

    {

    int i = 0, s = times, l;

    while ((i + 2*s - 1) < length)

    {

    Merge(S, T, i, i+s-1, i+2*s-1);

    i += 2*s;

    }/*此处的循环用于遍历数组所有元素并依照k(此处为赋值为s)来归并入辅助的数组空间中*/

    /*if-else用于处理归并剩下的序列,由于已经不知足(i + 2*s - 1) < length的条件

    * 因此须要修改Merge()函数的下标,而若是知足(i + s - 1) < length即表示

    * i 到 i + s - 1 这段序列为归并的第一段,剩下一段为 i + s 到 length - 1,

    * 而若是不知足if条件则说明剩下序列已经有序,直接循环赋值给目标数组便可

    */

    if ((i + s - 1) < length)

    {

    Merge(S, T, i, i+s-1, length-1);

    }

    else

    {

    for (l = i; l < length; l++)

    {

    T[l] = S[l];

    }

    }

    }

    //归并排序最主要实现函数

    int Merge(int *S, int *T, int low, int m, int high)

    {//j在[m+1,high]区间递增,k用于目标T的下标递增, l是辅助变量

    int j, k, l;

    for (k = low, j = m+1;

    low <= m && j <= high;

    k++)

    {

    if (S[low] < S[j])

    {

    T[k] = S[low++];//此处先执行T[k] = S[low],而后low++;

    }

    else

    {

    T[k] = S[j++];//同理

    }

    }

    //for循环事后,必然有low>m 或者 j>high,故分状况处理

    if (low <= m)

    {

    for (l = 0; l <= m-low; l++)

    {

    T[k+l] = S[low+l];

    }

    }

    if (j <= high)

    {

    for (l = 0; l <= high-j; l++)

    {

    T[k+l] = S[j+l];

    }

    }

    }

    int main()

    {

    int i;

    int a[A_LENGTH] = {50, 90, 80, 40, 30,

    120, 150, 200, 70, 60};

    printf("Before sorting:");

    for (i = 0; i < A_LENGTH; i++)

    {

    printf("%d -- ", a[i]);

    }

    MergeSort(a);

    printf("\n\nAfter sorting: ");

    for (i = 0; i < A_LENGTH; i++)

    {

    printf("%d -- ", a[i]);

    }

    return 0;

    }

    d377d51fb64ccffafc8a73cc089f76ad.png

    展开全文
  • 归并排序 ...归并排序非递归实现主要在于子序列的划分; 1、首先需要一个临时数组以及左右两个子序列的区间; 2、从区间长度为1开始(递增两倍)将原数组划分成多对左右两个子序列; 3、依次将多对左

    归并排序

    归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

    一、非递归实现

    1.排序原理

    归并排序的非递归实现主要在于子序列的划分;
    1、首先需要一个临时数组以及左右两个子序列的区间
    2、从区间长度为1开始(递增两倍)将原数组划分成多对左右两个子序列;
    3、依次将多对左右子序列进行比较,并按顺序存入临时数组中
    4、再将临时数组排序好的序列再复制到原数组中
    5、最后区间长度两倍增长,重复以上操作,即归并
    排序过程图示
    在这里插入图片描述

    2.源代码:

    #include<stdio.h>
    #include<stdlib.h>
    #define N 10
    
    void MergeSort(int num[],int len)
    {
    	int i,j;
    	int *sort;
    	int L_start=0,L_end=0;//初始化左区间的起点、终点下标
    	int R_start=0,R_end=0;//初始化右区间的起点、终点下标
    
    	sort=(int*)malloc(N*sizeof(int));//为临时数组分配空间
    
    	for(i=1;i<N;i*=2)//区间长度两倍递增
    	{
    		for(L_start=0;L_start<len-i;L_start=R_end)
    		{
    			//确定左右区间两边的起点、终点下标		
    			L_end   = L_start+i;
    			R_start	= L_start+i;
    			R_end	= R_start+i;
    
    			if(R_end>len)//右区间终点不超过数组长度
    			{
    				R_end=len;
    			}			
    			j=0;	//临时数组初始下标
    
    			while(L_start<L_end && R_start<R_end)
    			{
    				//比较左右起点数据的大小,并将较小的数据依次存入临时数组
    				if(num[L_start]<num[R_start])	
    					sort[j++]=num[L_start++];
    				else
    					sort[j++]=num[R_start++];
    				//同时起点下标递增
    			}
    	
    			while(L_start<L_end)//将比较完剩余的数据存入临时数组
    			{
    				sort[j++]=num[L_start++];
    			}	
    			while(j>0)			//将已排好的临时数组数据录入原数组中
    			{
    				num[--R_start]=sort[--j];
    			}
    
    			//for(int k=0;k<len;k++)
    			//	printf("%d ",num[k]);
    			//printf("\n");
    		}
    	//printf("-------------\n");
    	}
    	free(sort);
    }
    
    int main()
    {
    	int num[N]={5,3,7,1,9,2,0,4,8,6};
    	MergeSort(num,N);
    	for(int i=0;i<N;i++)
    		printf("%d ",num[i]);
    	printf("\n");
    	return 0;
    }
    

    二、递归实现

    1.排序原理

    归并排序的递归实现主要在于递归分治,对于递归算法,我们都能用二叉树来理解,对于一个序列,递归左右子序列,并对其子序列进行合并排序,即可得到排序好的序列
    排序过程图示
    在这里插入图片描述

    2.源代码:

    #include<stdio.h>
    #include<stdlib.h>
    #define N 10
    void Merge(int sort[],int num[],int low,int mid,int high)
    {
    	int i=low;		//左子序列起点下标
    	int j=mid+1;	//右子序列起点下标
    	int k=low;		//临时数组的初始化下标
    	while(i<=mid&&j<=high)//在左右子序列中按从小到大顺序存到临时数组中
    	{
    		if(num[i]<num[j])
    			sort[k++]=num[i++];
    		else
    			sort[k++]=num[j++];
    	}
    	//将左右子序列剩余的数依次存入临时数组
    	while(i<=mid)
    		sort[k++]=num[i++];
    	while(j<=high)
    		sort[k++]=num[j++];
    	//将临时数组的数据按位置复制到原数组对应位置上
    	while(--k>=0)
    		num[k]=sort[k];
    }
    void MergeSort(int sort[],int num[],int low,int high)
    {
    	if(low<high)
    	{
    		int mid=(low+high)/2;			//分为左右子序列的中间下标
    		MergeSort(sort,num,low,mid);	//递归左子序列
    		MergeSort(sort,num,mid+1,high);	//递归右子序列
    		Merge(sort,num,low,mid,high);	//排序
    	}
    }
    int main()
    {
    	int *sort;
    	int num[N]={5,3,7,1,9,2,0,4,8,6};
    	sort=(int*)malloc(N*sizeof(int));
    	MergeSort(sort,num,0,N-1);
    	for(int i=0;i<N;i++)
    		printf("%d ",num[i]);
    	printf("\n");
    	free(sort);
    	return 0;
    }
    
    展开全文
  • 8645 归并排序 (非递归算法).txt
  • 8645 归并排序非递归算法)时间限制:1000MS 内存限制:1000K 提交次数:2398 通过次数:1192题型: 编程题 语言: G++;GCC Description用函数实现归并排序非递归算法),并输出每趟排序的结果 输入格式第一行:键盘...

    8645 归并排序(非递归算法)时间限制:1000MS 内存限制:1000K
    提交次数:2398 通过次数:1192题型: 编程题 语言: G++;GCC
    Description用函数实现归并排序(非递归算法),并输出每趟排序的结果
    输入格式第一行:键盘输入待排序关键的个数n
    第二行:输入n个待排序关键字,用空格分隔数据
    输出格式每行输出每趟排序的结果,数据之间用一个空格分隔
    输入样例
    10
    5 4 8 0 9 3 2 6 7 1
    输出样例
    4 5 0 8 3 9 2 6 1 7
    0 4 5 8 2 3 6 9 1 7
    0 2 3 4 5 6 8 9 1 7
    0 1 2 3 4 5 6 7 8 9

    source—
    #include<stdio.h>
    int f(int a[],int i,int e,int n)
    {
    int j,k,t;
    if(i+e-1<=n)
    {
    for(j=i; j<i+e-1; j++)
    {
    for(k=j+1; k<i+e; k++)
    {
    if(a[k]<a[j])
    {
    t=a[k];
    a[k]=a[j];
    a[j]=t;
    }
    }
    }
    }
    else
    for(j=i; j<n; j++)
    {
    for(k=j+1; k<n+1; k++)
    {
    if(a[k]<a[j])
    {
    t=a[k];
    a[k]=a[j];
    a[j]=t;
    }
    }
    }
    }
    int main()
    {
    int n;
    scanf("%d",&n);
    int a[10000],i,j,k,x;
    for(i=1; i<=n; i++)
    {
    scanf("%d",&a[i]);
    }
    int e;
    e=1;
    if(n>1)
    {
    while(e<n)
    {
    for(i=1; i<=n; i=i+e2)
    {
    f(a,i,e
    2,n);
    }
    for(k=1; k<=n; k++)
                    printf("%d “,a[k]);
                printf(”\n");
                e=e*2;
            }
        }
        else printf("%d",a[n]);
        return 0;
    }

    展开全文
  • 8645 归并排序非递归算法) 时间限制:1000MS 代码长度限制:10KB 提交次数:2398 通过次数:1192 题型: 编程题 语言: G++;GCC Description 用函数实现归并排序非递归算法),并输出每趟排序的结果 输入格式 第...
    8645 归并排序(非递归算法)
    时间限制:1000MS  代码长度限制:10KB
    提交次数:2398 通过次数:1192
    
    题型: 编程题   语言: G++;GCC
    Description
    用函数实现归并排序(非递归算法),并输出每趟排序的结果
    
    
    
    输入格式
    第一行:键盘输入待排序关键的个数n
    第二行:输入n个待排序关键字,用空格分隔数据
    
    
    输出格式
    每行输出每趟排序的结果,数据之间用一个空格分隔
    
    
    输入样例
    10
    5 4 8 0 9 3 2 6 7 1
    
    
    输出样例
    4 5 0 8 3 9 2 6 1 7
    0 4 5 8 2 3 6 9 1 7
    0 2 3 4 5 6 8 9 1 7
    0 1 2 3 4 5 6 7 8 9
    
    

    m表示每一趟排序中归并多少个元素,第一趟为2,然后是4,8…
    d表示有序表分成多少份,比如10个元素第一趟分成5份归并排序,每份m(2)个

    #include <iostream>
    
    using namespace std;
    
    void Merge(int R[],int T[],int low,int mid,int high)//将有序表R[low...mid]和R[mid+1...high]合并成有序表
    {
        int i=low,j=mid+1,k=low;
        while(i<=mid&&j<=high)//将R中记录由小到大并入T中
        {
            if (R[i]<R[j])
            {
                T[k++]=R[i++];
            }
            else T[k++]=R[j++];
        }
        while(i<=mid) T[k++]=R[i++];//将剩余的数据并入T[]中
        while(j<=high) T[k++]=R[j++];//将剩余的数据并入T[]中
    }
    
    void Mergesort(int A[],int n)
    {
        int T[n+5]= {0},i,j,low,mid,high;
        int m=2,d;//m表示每一趟排序中归并多少个元素,第一趟为2,然后是4,8....
        //d表示有序表分成多少份,比如10个元素第一趟分成5份归并排序,每份m(2)个元素
        if (n%2!=0)
        {
            d=n/2+1;
        }else
        {
            d=n/2;
        }
        while(d>1)
        {
            if(m>n)
            {
                high=n;
            }
            else
            {
                high=m;
            }
    //      printf("d=%d m=%d\n",d,m);
            for (low=1; low<=n;)
            {
                mid=(high+low)/2;
                Merge(A,T,low,mid,high);
    //            printf("low=%d mid=%d high=%d\n",low,mid,high);
                low=low+m;
                high=high+m;
                if (high>n)
                {
                    high=n;
                }
            }
            for (i=1; i<=n; i++)//将排序后数据复制到A[]中,以便进行下次排序
            {
                A[i]=T[i];
            }
            for (i=1; i<=n; i++)
            {
                printf("%d ",T[i]);
            }
            printf("\n");
            m=m*2;
            if (n%m!=0)
            {
                d=n/m+1;
            }
            else
            {
                d=n/m;
            }
        }
        Merge(A,T,1,m/2,n);
        for (i=1; i<=n; i++)
        {
            printf("%d ",T[i]);
        }
    }
    
    int main()
    {
        int i,j,n;
        scanf("%d",&n);
        int A[n+5]={0};
        for (i=1; i<=n; i++)
        {
            scanf("%d",&A[i]);
        }
        Mergesort(A,n);
        return 0;
    }
    
    
    展开全文
  • 非递归归并排序 ···
  • 归并排序(非递归) ----- C语言

    千次阅读 2015-11-20 22:38:20
    最近搞了很久才基本弄清楚非递归归并排序的基本思想,查阅许久才看懂代码,自己简单地实现了一下: #define A_LENGTH 10 #include #include int MergeSort(int *a) { int k = 1;/*k用来表示每次k个元素归并*...
  • 插入排序的实现: //插入排序:时间复杂度最大为o(N*N);最小为o(N);不稳定; void insert(int* arr, int n) { for (int i = 1; i < n; ++i) { int end = i - 1; //保存要插入的数据 int data = arr...
  • 对于归并排序的思想,步骤,这篇博客讲的十分清楚排序算法c语言描述—归并排序,我就依自己对这个排序算法的理解尝试着进行一些补充(针对非递归实现归并排序)。 先上代码: 将SR[i…m]和SR[m+1…n]归并成一个有序...
  • } } //合并数组函数,实现自然归并排序 int margeSort(int *s, int n, int *sign, int num) { int jump = 1; int b[N]; while(jump ) { margePass(s, n, b, sign, num, jump); jump+=jump; copySort(s, n, b); } } ...
  • 键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 输入样例 10 5 4 8 0 9 3 2 6 7 1 输出样例 4 5 0 8 3 9 2 6 1 7 0 4 5 8 2 3 6 9 1 7 0 2 3 4 5 6 8 9 1 7 0 1 2 3 4 ...
  • 148. 排序链表 在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。...复杂度nlogn即为归并排序递归方法 分为merge和mergesort两步; (1)merge dummyhead维护归并后的链表,并返回; (2)merg

空空如也

空空如也

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

归并排序c语言非递归

c语言 订阅