精华内容
下载资源
问答
  • 归并排序c语言代码
    千次阅读
    2022-04-19 21:45:36

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

    是一种稳定的排序算法。

    将已有的子序列合并,得到完全有序的的序列;即先使每个子序列有序,再使子序列段间有序。

    若将两个有序表合并成一个有序表,成为二路归并

    代码实现如下:

    #include "stdio.h"
    #include "malloc.h"
    #include "string.h"
    
    void PrintfArray(int* ar, int left,int right)
    {
    	for (int i = left; i < right; i++)
    		printf("%d ", ar[i]);
    }
    
    void _MergeSort(int* ar, int left, int right,int *tmp)
    {
    	if (left >= right)
    		return;
    	int mid = (right + left) / 2;
    	_MergeSort(ar, left, mid, tmp);
    	_MergeSort(ar, mid + 1, right, tmp);
    
    	int begin1 = left, end1 = mid;
    	int begin2 = mid + 1, end2 = right;
    	int k = left;
    	while (begin1 <= end1 && begin2 <= end2)
    	{
    		if (ar[begin1] < ar[begin2])
    			tmp[k++] = ar[begin1++];
    		else
    			tmp[k++] = ar[begin2++];
    	}
    	while (begin1 <= end1)
    		tmp[k++] = ar[begin1++];
    	while (begin2 <= end2)
    		tmp[k++] = ar[begin2++];
    	memcpy(ar + left, tmp + left, sizeof(int)*(right - left + 1));
    
    }
    
    void MergeSort(int* ar, int left, int right)
    {
    	int n = right - left;
    	int* tmp = (int*)malloc(sizeof(int)*n);
    	_MergeSort(ar, left, right - 1, tmp);
    	free(tmp);
    	tmp = NULL;
    
    }
    
    int main()
    {
    	int ar[] = {13,37,34,78,90,88,12 };
    	int n = sizeof(ar) / sizeof(ar[0]);
    	PrintfArray(ar, 0, n);
    	MergeSort(ar,0,n);
    	printf("\n");
    	PrintfArray(ar, 0, n);
    }
    

    更多相关内容
  • 排序算法中的归并排序(Merge Sort)是利用”归并”技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。 一、实现原理: 1、算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的...
  • 归并排序C语言代码

    2017-02-27 19:19:58
    归并排序C语言代码
  • 归并排序 c语言实现

    2021-01-11 23:42:53
    归并排序 归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法 算法复杂度:O(nlogn) 就是将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序...

    归并排序

    归并排序(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语言实现

    2011-12-03 16:28:33
    归并排序C语言实现
  • 归并排序C语言实现(源代码)

    千次阅读 2020-10-18 20:51:39
    归并排序 对一个元素个数为20个的随机数组进行快速排序 #include <stdio.h> #include <stdlib.h> #include <time.h> void Display(int *arr, int n){ for (register int i = 0; i < n; i++){...

    归并排序

    对一个元素个数为20个的随机数组进行快速排序

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    void Display(int *arr, int n){
    	for (register int i = 0; i < n; i++){
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    }
    
    void merge(int *arr, int L, int M, int R){
    	int LEFT_SIZE = M - L;
    	int RIGHT_SIZE = R - M + 1;
    	int left[LEFT_SIZE];
    	int right[RIGHT_SIZE];
    	int i, j, k;
    	
    	//将原数组左边分到一个新数组left中
    	for(i = L; i < M; i++){
    		left[i - L] = arr[i]; 
    	} 
    	//将原数组右边分到一个新数组right中
    	for(i = M; i <= R; i++){
    		right[i - M] = arr[i]; 
    	}
    	i = 0; j = 0; k = L;
    	while(i < LEFT_SIZE && j < RIGHT_SIZE){
    		//如果left数组的第一个数字比right数组第一个数字小就把它放到新数组里 
    		if(left[i] < right[j]){
    			arr[k] = left[i];
    			i++;
    			k++;
    		}else{
    			arr[k] = right[j];
    			j++;
    			k++;
    		}
    	}
    	while(i < LEFT_SIZE){
    		arr[k] = left[i];
    		i++;
    		k++;
    	}
    	while(j < RIGHT_SIZE){
    		arr[k] = right[j];
    		j++;
    		k++;
    	}
    	 
    }
     
    
    void mergesort(int *arr, int L, int R){
    	int M = (L + R)/2;
    	if(L == R){
    		return;
    	}else{
    		printf("归并排序中:");
    		Display(arr, 20);
    		mergesort(arr, L, M);
    		mergesort(arr, M+1, R);
    		merge(arr, L, M+1, R);		
    	}
    }
    
    
    		
    int main(){
    	int arr[20] = {6,5,4,3,2,1,8,7,0,9,11,33,22,55,77,44,66,99,888,90};;
    	//生成一个有20个元素的随机数组
    	srand((unsigned int)time(0));//修改种子
    	for (register int i = 0; i < 20; i++){	
    		arr[i] = rand();
    	}
    	printf("原数组为:\n");
    	Display(arr, 20);
    	printf("\n");
    	int L = 0;
    	int R = 19;
    	mergesort(arr, L, R);
    	printf("\n归并排序后:\n");
    	Display(arr, R+1);
    	return 0;
    }
    
    

    如有不足,欢迎各位大佬指正

    展开全文
  • 下面是编程之家 jb51.cc 通过网络收集整理的代码片段。编程之家小编现在分享给大家,也给大家做个参考。// Mix two sorted tables in one and split the result into these two tables.int *Mix(int *tab1,int *tab2...

    下面是编程之家 jb51.cc 通过网络收集整理的代码片段。

    编程之家小编现在分享给大家,也给大家做个参考。

    // Mix two sorted tables in one and split the result into these two tables.

    int *Mix(int *tab1,int *tab2,int count1,int count2)

    {

    int i,i1,i2;

    i = i1 = i2 = 0;

    int * temp = (int *)malloc(sizeof(int)*(count1+count2));

    while((i1

    {

    while((i1

    {

    *(temp+i++) = *(tab1+i1);

    i1++;

    }

    if (i1

    {

    while((i2

    {

    *(temp+i++) = *(tab2+i2);

    i2++;

    }

    }

    }

    memcpy(temp+i,tab1+i1,(count1-i1)*sizeof(int));

    memcpy(tab1,temp,count1*sizeof(int));

    memcpy(temp+i,tab2+i2,(count2-i2)*sizeof(int));

    memcpy(tab2,temp+count1,count2*sizeof(int));

    // These two lines can be:

    // memcpy(tab2,i2*sizeof(int));

    free(temp);

    }

    // MergeSort a table of integer of size count.

    // Never tested.

    void MergeSort(int *tab,int count)

    {

    if (count==1) return;

    MergeSort(tab,count/2);

    MergeSort(tab+count/2,(count+1)/2);

    Mix(tab,tab+count/2,count/2,(count+1)/2);

    }

    以上是编程之家(jb51.cc)为你收集整理的全部代码内容,希望文章能够帮你解决所遇到的程序开发问题。

    如果觉得编程之家网站内容还不错,欢迎将编程之家网站推荐给程序员好友。

    总结

    以上是编程之家为你收集整理的C语言实现归并排序算法代码全部内容,希望文章能够帮你解决C语言实现归并排序算法代码所遇到的程序开发问题。

    如果觉得编程之家网站内容还不错,欢迎将编程之家网站推荐给程序员好友。

    本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。

    小编个人微信号 jb51ccc

    喜欢与人分享编程技术与工作经验,欢迎加入编程之家官方交流群!

    展开全文
  • 归并排序 C语言实现

    万次阅读 多人点赞 2019-04-20 13:05:45
    1. 归并排序(排序的方法一种,速度比选择排序、插入排序等快很多)适合较多数据排序 ...3. c语言代码实现 #include<stdio.h> #define ArrLen 20 void printList(int arr[], int len) { int i; for...
  • 排序完成: 时间复杂度:o(nlog(2)n) 核心代码: void Merge( int A[], int Temp[], int L, int R, int RightEnd) //合并两个有序序列 { int LeftEnd=R- 1 ; int p=L,i; int num=RightEnd-L+ ...
  • 归并排序 C语言

    2014-03-08 23:10:20
    C语言归并排序算法完整代码,欢迎交流讨论。
  • 图形实例4.C语言代码实现四、归并排序1.简单介绍2.算法原理3.图形实例4.C语言代码实现 一、冒泡排序 1.简单介绍 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列...
  • 归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 算法步骤: 1. 申请空间,使其大小为两个已经排序序列之...
  • C语言归并排序(完整代码版)

    千次阅读 2021-09-11 18:59:21
    归并排序代码如下: #include<stdio.h> #include<stdlib.h> void Merge(int arr[], int tmp[], int start,int mid, int end)//合并小组并排序 { int i = start;//i标识//左小组的第一个元素位置 ...
  • C语言实现归并排序

    千次阅读 2022-04-07 12:46:43
    归并排序每次递归的动作: 将给定数组以中点为界,分为左右两部分,且左右两边的数字分别有序。(至于如何将它做到分别有序,则需使用递归实现) 使用两个指针 L(初始值为左边界) 和 R(初始值为中点右侧的第一个...
  • C语言——归并排序

    千次阅读 2021-12-09 21:56:42
    C语言——归并排序 归并排序用到了分治思想,借助递归的方式对一串数字进行排序,整个过程分为分开和合并两个过程。其实归并排序的思想并不难理解,但是用代码实现它却并不容易,我们要写两个函数去分别实现这个过程...
  • 归并排序(递归)——C语言实现

    千次阅读 热门讨论 2022-04-11 11:39:43
    文章目录一、归并排序定义二、图解归并过程三、动图展示四、分治递归五、归并排序代码 一、归并排序定义 归并排序:是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide andConquer)的一个...
  • 归并排序c语言

    2021-11-21 17:23:05
    归并排序 ...2路归并排序代码c语言) 思路:使用分治和递归的思想,Merge()函数负责将两段元素合并为一段元素,MergeSort()函数代表了归并排序,我们的基本思想是将整段元素分为两段: low-mid;mid+1
  • 归并排序的核心思想可以概括为将亮前后相连的有序表归并为一个有序表。归并的过程就是每次从两个有序表中选取最小的那个加入到新的有序表中,直到把两个表并成一个。将一个数组的值复制到另一个时可以让 a[ i++ ] = ...
  • 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补...
  • 归并排序(C语言)

    千次阅读 2022-04-25 19:23:12
    归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序...
  • 归并排序(非递归)——C语言实现

    千次阅读 多人点赞 2022-04-14 16:48:56
    一、递归实现归并排序的问题 递归实现快速排序一样,递归实现归并排序一样需要在栈上建立栈帧,消耗栈空间,当提柜深度过深时,就会出现栈溢出的现象。为了解决这个缺陷,本文将带来非递归实现归并排序的算法。 二、...
  • C语言中数据结构之链表归并排序实例代码 问题  设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增排序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中...
  • 分治法归并排序(C语言)

    千次阅读 多人点赞 2019-11-24 11:28:27
    前言: 分治法归并排序原理: 将一个乱序数组分治为两部分,再分别在这两...从上述的基本思想我们可以大概了解了我们代码的框架,首先我们定义一个归并排序的算法,再定义一个分治的函数即可。 代码: #include<s...
  • 归并排序算法(C语言实现)

    千次阅读 2021-03-01 10:43:06
    归并排序的步骤: 1.将序列分成左右两部分 2.排序左序列,排序右序列 3.合并两个有序的序列 需要申请额外的空间放临时的有序序列 #include<stdio.h> #include<string.h> #include<stdlib.h> ...
  • 归并排序——c语言实现

    千次阅读 2020-07-14 17:09:02
    文章目录归并排序的一般过程归并排序过程样例图解c语言代码 归并排序的一般过程 归并排序也是利用分治技术的一种排序算法。 归并算法就是将要排序的数组切成两半,,然后递归继续切,直到最后切成单个元素。然后重新...
  • 本文实例为大家分享了C语言实现归并排序的具体代码,供大家参考,具体内容如下 归并排序的基本思想: 将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,444
精华内容 3,377
关键字:

归并排序c语言代码