精华内容
下载资源
问答
  • 归并排序 C语言实现

    2011-09-16 13:26:26
    归并排序 C语言实现 归并排序 C语言实现 归并排序 C语言实现
  • 归并排序C语言实现

    2011-12-03 16:28:33
    归并排序C语言实现
  • 归并排序c语言实现

    2015-03-05 16:42:24
    归并排序算法C语言实现,以比较为基础的时间复杂度下限
  • 归并排序 c语言实现

    2021-01-11 23:42:53
    归并排序 归并排序(Merge Sort)是建立在归并操作上的一种.../* 归并排序 - 递归实现 */ #include <stdio.h> #include<stdlib.h> #define ElementType int /* L = 左边起始位置, R = 右边起始位置,

    归并排序

    归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法
    算法复杂度:O(nlogn)
    就是将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
    在这里插入图片描述
    递归实现

    /* 归并排序 - 递归实现 */
    
    #include <stdio.h>
    #include<stdlib.h> 
    #define ElementType int
    
    
    
    /* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
    void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
    { /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
         int LeftEnd, NumElements, Tmp;
         int i;
         
         LeftEnd = R - 1; /* 左边终点位置 */
         Tmp = L;         /* 有序序列的起始位置 */
         NumElements = RightEnd - L + 1;
         
         while( L <= LeftEnd && R <= RightEnd ) {
             if ( A[L] <= A[R] )
                 TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
             else
                 TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
         }
    
         while( L <= LeftEnd )
             TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
         while( R <= RightEnd )
             TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
             
         for( i = 0; i < NumElements; i++, RightEnd -- )
             A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
    }
    
    void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
    { /* 核心递归排序函数 */ 
         int Center;
         
         if ( L < RightEnd ) {
              Center = (L+RightEnd) / 2;
              Msort( A, TmpA, L, Center );              /* 递归解决左边 */ 
              Msort( A, TmpA, Center+1, RightEnd );     /* 递归解决右边 */  
              Merge( A, TmpA, L, Center+1, RightEnd );  /* 合并两段有序序列 */ 
         }
    }
    
    void MergeSort( ElementType A[], int N )
    { /* 归并排序 */
         ElementType *TmpA;
         TmpA = (ElementType *)malloc(N*sizeof(ElementType));
         
         if ( TmpA != NULL ) {
              Msort( A, TmpA, 0, N-1 );
              free( TmpA );
         }
         else printf( "空间不足" );
    }
    
    
    int main()
    {
    	int A[5]={4,5,3,3,2};
    	MergeSort(A,5);
    	for(int i=0;i<5;++i)
    	{
    		printf("%d ",A[i]);
    	}
    	return 0;
    }
    

    迭代实现

    #include <stdio.h>
    #include<stdlib.h> 
    #define ElementType int
    
    /* 归并排序 - 迭代实现 */
    
    /* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
    void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
    { /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
         int LeftEnd, NumElements, Tmp;
         int i;
         
         LeftEnd = R - 1; /* 左边终点位置 */
         Tmp = L;         /* 有序序列的起始位置 */
         NumElements = RightEnd - L + 1;
         
         while( L <= LeftEnd && R <= RightEnd ) {
             if ( A[L] <= A[R] )
                 TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
             else
                 TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
         }
    
         while( L <= LeftEnd )
             TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
         while( R <= RightEnd )
             TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
             
         for( i = 0; i < NumElements; i++, RightEnd -- )
             A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
    }
    
    
    /* length = 当前有序子列的长度*/
    void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length )
    { /* 两两归并相邻有序子列 */
         int i, j;
          
         for ( i=0; i <= N-2*length; i += 2*length )
             Merge( A, TmpA, i, i+length, i+2*length-1 );
         if ( i+length < N ) /* 归并最后2个子列*/
             Merge( A, TmpA, i, i+length, N-1);
         else /* 最后只剩1个子列*/
             for ( j = i; j < N; j++ ) TmpA[j] = A[j];
    }
    
    void Merge_Sort( ElementType A[], int N )
    { 
         int length; 
         ElementType *TmpA;
         
         length = 1; /* 初始化子序列长度*/
         TmpA = malloc( N * sizeof( ElementType ) );
         if ( TmpA != NULL ) {
              while( length < N ) {
                  Merge_pass( A, TmpA, N, length );
                  length *= 2;
                  Merge_pass( TmpA, A, N, length );
                  length *= 2;
              }
              free( TmpA );
         }
         else printf( "空间不足" );
    }
    
    int main()
    {
    	int A[5]={4,5,3,3,2};
    	Merge_Sort(A,5);
    	for(int i=0;i<5;++i)
    	{
    		printf("%d ",A[i]);
    	}
    	return 0;
    }
    
    展开全文
  • 归并排序C语言实现与分析

    千次阅读 2019-06-05 15:38:32
    归并排序C语言实现与分析

    具体代码

    #include<stdio.h>
    
    //将两个有序数组合并的过程
    void Merge(int* R, int start, int mid, int end)
    {
    	//需要把元素全誊到这个新数组去
    	int A[end-start+1];
    	//i代表第一个有序数组的起始位置
    	int i = start;
    	//j代表第二个有序数组的起始位置
    	int j = mid+1;
    	//k用来逐个表示A数组中的元素
    	int k = 0;
    
    	//从这两个有序数组中找出小的,逐个放入A数组
    	while(i<=mid && j<=end)
    	{
    		//j的小就放j
    		if(R[i]>R[j])
    		{
    			A[k] = R[j];
    			j++;
    		}
    		else
    		{
    			A[k] = R[i];
    			i++;
    		}
    		k++;
    	}
    	
    	//当出现某个数组放完了之后,直接把另一个数组剩下的全放入A即可
    	//其实下面那两个if可以不写,只不过这里只是增强可读性而已....
    	if(i>mid)
    	{
    		while(j<=end)
    		{
    			A[k] = R[j];
    			j++;
    			k++;
    		}		
    	}
    	if(j>end)
    	{
    		while(i<=mid)
    		{
    			A[k] = R[i];
    			i++;
    			k++;
    		}		
    	}
    	
    	//然后再把已经有序了的元素装回到原来啊的R数组
    	for(int m = 0;m<k;m++)
    	{
    		R[start] = A[m];
    		start++;
    	}
    }
    
    //归并排序
    void MergeSort(int* R, int start, int end) 
    {
    	//如果没把数组分到单个元素,就一直分治
    	if(start<end)
    	{
    		//一分为二
    		int mid = (start+end)/2;
    		//左右两边排好序
    		MergeSort(R,start,mid);
    		MergeSort(R,mid+1,end);
    		//拼接到一起
    		Merge(R,start,mid,end);
    	}
    }
    
    int main()
    {
    	int M[6] = {1,5,3,7,8,2};
    	MergeSort(M,0,5);
    	for(int i=0;i<6;i++)
    	{
    		printf("%d  ", M[i]);	
    	}
    }
    
    

    过程分析

    这是冯诺依曼大佬提出的算法,利用了分治的思想,各层分治递归可以同时进行。所以我连分步解释的图都不好画了。。。。。。
    不过总体流程大概是这样:
    在这里插入图片描述
    这个算法的主体思路就是把一个数组全部划分成单个元素,单个元素进行比较后合并。由于是递归,多个比较同时发生,所以会更快。每次在比较完后,会得到两个有序数组,只需要将有序数组合并即可(对于只用单个元素的情况,就是直接比大小了)。
    我这里就只讲一下合并步骤的思路了。

    合并步骤

    1.得到两个有序数组,但是他们在空间上是连在一起的,他们以你之前划分的标准mid元素来分界。
    2.所以两个数组的空间位置分别是
    start—mid, mid+1—end-1
    准备好指针,开始排序即可
    3.由于他们的都是有序数组,从头逐个比较,取走小的那个即可。
    比如:
    A数组-----------1,6,7,9,9
    B数组-----------2,3,4,5,8
    那么我们先从A中取走1,再比较A的第二个元素和B的第一个元素,取走2,同理,继续比较,取走B中的3,然后4,然后5,然后再取A中的7,再取B中的。
    4.这时,B数组已经取完了,只需要把剩下的A中的两个9全部放到数组里即可。
    5.最后注意我们是把数组先有序地誊到一个空的数组里了,还要放回来,完成。

    性能分析

    在这里插入图片描述

    展开全文
  • 归并排序 算法思想:假定无序序列中有n个元素,则可以看成是n个有序的子序列,每个子序列长度为1.然后两两合并,得到n/2个长度为2或1的有序序列,再两两归并…如此重复之下,直到合并成长度为n的有序序列为止。 形如...

    归并排序

    算法思想:假定无序序列中有n个元素,则可以看成是n个有序的子序列,每个子序列长度为1.然后两两合并,得到n/2个长度为2或1的有序序列,再两两归并…如此重复之下,直到合并成长度为n的有序序列为止。
    形如无序序列{88,34,65,78,49,23,90,12,17,76},两两归并如下图:
    归并排序
    C语言代码:

    #include<stdio.h>
    #include<string.h>
    #define len 10
    //进行归并 
    void merge(int a[], int low, int mid, int high)
    {
    	int i,j,b[len],k;
    	//将a中的元素复制到b中
    	for(k=low;k<=high;k++)
    	{
    		b[k] = a[k];
    	}
    	for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++)
    	{
    		//比较b中左右两端中的元素,将较小值赋值到a中
    		a[k] = b[i] < b[j] ? b[i++]:b[j++];
    	}
    	while(i <= mid)
    	{
    		//若第一个表中未检查完,则复制
    		a[k++] = b[i++];
    	}
    	while(j <= high)
    	{
    		//若第二个表中未检查完,则复制
    		a[k++] = b[j++]; 
    	}
    }
    
    //归并排序
    void mergeSort(int a[], int low, int high)
    {
    	if(low<high)
    	{
    		//获取中间值
    		int mid = (low+high)/2;
    		//对左侧子序列进行递归排序
    		mergeSort(a, low, mid);
    		//对右侧子序列进行递归排序
    		mergeSort(a, mid+1, high);
    		//最后归并
    		merge(a, low, mid, high);
    	}
    }
    int main()
    {
    	int a[] = {88,34,65,78,49,23,90,12,17,76};
    	int i;
    	printf("未排序前:\n"); 
    	for(i=0;i<len;i++)
    	{
    		printf("%d  ", a[i]);
    	}
    	printf("\n经过排序后:\n"); 
    	mergeSort(a, 0, len-1);
    	for(i=0;i<len;i++)
    	{
    		printf("%d  ", a[i]);
    	}
    }
    

    如果以上程序或解释有问题,请务必指出互相交流。

    展开全文
  • 一 、归并排序的思路: 归并排序采用的是分治的思想,就是将数组进行分隔,直到最小的单位(两个元素),然后对最小的单位进行排序。 最后将排好序的单位依次遍历到数组中。 1 将数组进行分隔,直到不能再分的最小...

    一 、归并排序的思路:

    归并排序采用的是分治的思想,就是将数组进行分隔,直到最小的单位(两个元素),然后对最小的单位进行排序。最后将排好序的单位依次遍历到数组中。

    1 将数组进行分隔,直到不能再分的最小单位(两个元素)。
    2 将最小单位排序
    3 将最小单位遍历到数组中
    

    二、代码

    #include <stdio.h>
    void merge_part(int arr[], int l, int m, int r)
    {
    	// 此处应该用 malloc
    	int tmp[256] = { 0 };
    	int idx = l, i = l, j = m + 1, ii = l;
    	for (; i <= m && j <= r;)
    	{
    		if (arr[i] < arr[j])
    			tmp[idx++] = arr[i++];
    		else
    			tmp[idx++] = arr[j++];
    	}
    
    	if (i <= m) {
    		for (; i <= m; ++i)
    			tmp[idx++] = arr[i];
    	}
    
    	if (j <= r) {
    		for (; j <= r; ++j)
    			tmp[idx++] = arr[j];
    	}
    
    	for (; ii <= r; ++ii)
    		arr[ii] = tmp[ii];
    }
    
    void merge_sort(int arr[], int l, int r)
    {
    	int mid = ((r - l) / 2) + l;
    
    	if (l >= r) return;
    	merge_sort(arr, l, mid);
    	merge_sort(arr, mid + 1, r);
    	merge_part(arr, l, mid, r);
    }
    
    int main()
    {
    	int arr[] = { 8, 36, 23, 2, 17, 6, 59, 20, 13, 28, 14, 83, 9};
    	//int arr[] = { 8, 36, 23, 2, 17, 6 };
    
    	int N = sizeof(arr) / sizeof(int), i = 0;
    	for (i = 0; i < N; ++i) {
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	merge_sort(arr, 0, N - 1);
    	for (i = 0; i < N; ++i) {
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	return 0;
    }
    

    三、排序流程

    在这里插入图片描述
    从上到下,从左到右是程序的执行流。

    归并排序的复杂度:

    时间复杂度:
     - 平均情况:O(nlogn)
     - 最好情况:O(nlogn)
     - 最坏情况:O(nlogn)
    
    空间复杂度:
    
     - 辅助空间:O(n)
     
    稳定性: 稳定
    

    这个是递归形式的写法,还有非递归形式的。

    *注: 个人笔记只用,如果不妥,还望不吝赐教。

    展开全文
  • 二路归并排序c语言实现

    千次阅读 2017-10-16 16:07:05
    二路归并排序 c 语言实现
  • 图形实例4.C语言代码实现四、归并排序1.简单介绍2.算法原理3.图形实例4.C语言代码实现 一、冒泡排序 1.简单介绍 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列...
  • 归并排序 对一个元素个数为20个的随机数组进行快速排序 #include <stdio.h> #include <stdlib.h> #include <time.h> void Display(int *arr, int n){ for (register int i = 0; i < n; i++){...
  • #include<stdio.h> #include<stdlib.h> #include<string.h> int* margesort(int *s, int *t, int slength, int tlength) ... int *list = (int *)malloc(sizeof(int)*(slength+tl...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 818
精华内容 327
关键字:

归并排序c语言实现

c语言 订阅