精华内容
下载资源
问答
  • 归并排序(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

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

    2020-08-17 19:27:35
    归并排序 C语言 思路:分治 先分原数组左半边 再分原数组右半边,最终层层递归治实现排序;图片来自https://blog.csdn.net/baidu_15547923/article/details/89742717 归并与逆序对的关系:待补充 #include<stdio...

    归并排序 C语言

    思路:分治 先分原数组左半边 再分原数组右半边,最终层层递归治实现排序;图片来自https://blog.csdn.net/baidu_15547923/article/details/89742717
    归并与逆序对的关系:以分治的某一个阶段为例
           [下标]   0123     4567 
           [数组]   4578     1236
           ( start=0, mid=3, end=7 )
      左半边 4 > 1就代表一对逆序对,而左半边已经排序完成,即(4,1)、(5,1)、(7,1)、(8,1)都是逆序对,
      同理4>2,逆序对有(4,2)、(5,2)、(7,2)、(8,2)…(4,3)、(5,3)、(7,3)、(8,3)…(7,6)、(8,6);最终当左侧大于右侧时,逆序对个数可表达mid-i+1(i为左侧索引,mid为左侧索引的结尾)
      LeetCode题型:
      LeetCode 493 翻转对
      https://blog.csdn.net/qq_40405527/article/details/108074965
      LeetCode 327 区间和的个数
      https://blog.csdn.net/qq_40405527/article/details/108085048
    归并排序

    #include<stdio.h>
    #include<stdlib.h>
    #define ArrLen 20
    void printList(int *nums, int len) {
    	int i;
    	for (i = 0; i < len; i++) {
    		printf("%d ", nums[i]);
    	}
    }
    void merge(int *nums, int start, int mid, int end) {//治
    	int len=end-start+1;
        int * temp=(int *)malloc(sizeof(int)*len);
    	int k = 0;
    	int i = start;
    	int j = mid + 1;
    	while (i <= mid && j <= end) {//注意区间的连贯性0~mid mid+1~end
    		if (nums[i] < nums[j]){    //或i=start;j=mid; while(i<mid && j<=end)
    			temp[k++] = nums[i++];
            }
    		else{
    			temp[k++] = nums[j++];
            }
    	}
    	if (i == mid + 1) {
    		while(j <= end)
    			temp[k++] = nums[j++];
    	}
    	if (j == end + 1) {
    		while (i <= mid)
    			temp[k++] = nums[i++];
    	}
    	for (j = 0, i = start ; j < k; i++, j++) {
    		nums[i] = temp[j];
    	}
        free(temp);
        temp=NULL;
    }
     
    void mergeSort(int *nums, int start, int end) {
    #if 0	
        if (start >= end)
    		return;
    	int mid = ( start + end ) / 2;
    	mergeSort(nums, start, mid);//分 递归划分原数组左半边
    	mergeSort(nums, mid + 1, end);//递归划分右半边if
    	merge(nums, start, mid, end);//合并
    #endif
        if(start<end){
             int mid = (start + end)/2;
             mergeSort(nums,start,mid);
             mergeSort(nums,mid+1,end);
             merge(nums,start,mid,end);
        }
    } 
    void main(){
    	int nums[] = {4, 7, 6, 5, 2, 1, 8, 2, 9, 1};
        int len=sizeof(nums)/sizeof(int);
    	mergeSort(nums, 0, len);
    	printList(nums, len);
    }
    
    展开全文
  • 归并排序 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.最后注意我们是把数组先有序地誊到一个空的数组里了,还要放回来,完成。

    性能分析

    在这里插入图片描述

    展开全文
  • 对于归并排序的思想,步骤,这篇博客讲的十分清楚排序算法c语言描述—归并排序,我就依自己对这个排序算法的理解尝试着进行一些补充(针对非递归实现归并排序)。 先上代码: 将SR[i…m]和SR[m+1…n]归并成一个有序...
  • 排序理念比较:归并排序merge sort思路:归并排序中间劈一刀,两边再排序,然后把左右两个合并。就是先局部有序,再整体有序。快速排序思路:随便选择一个数字作为中间点,小于放在左边,大于放在右边。递归对左右两...
  • 归并排序 C语言实现

    2020-11-20 21:55:03
    归并排序 ( Merging Sort )就是将两个或两个以上的有序表合并成一-个有序表的过程。将两个有序表合并成个有序表的过程称为2-路归并,2-路归并最为简单和常用。 算法思想: 假设初始序列含有n个记录,则可看成是n个...
  • 归并排序C语言实现

    2021-06-07 15:45:02
    归并排序参考:归并排序介绍: 参考: 归并排序介绍: 排序算法有多种,一般经常使用的是快速排序,因为在C语言的<stdlib.h>有快速排序函数 ‘’’ void qsort(void , size_t, size_t, int ()(const void *, ...
  • 思想 将两个有序的队列合并成一个大的有序的序列,反复操作,直到合并成一个有序的队列。 思路 一个大的无序队列,采用分治法进行排序。先将无序队列一分为二再一分为二...图解排序算法(四)之归并排序 实现 ...
  • C语言 算法与数据结构 二路归并排序递归实现 #include<stdio.h> #include<stdlib.h> #include<time.h> typedef int sorttype; void mergesort(sorttype * arr,int count); void merge(sorttype...
  • 归并排序C语言

    2018-10-28 19:57:52
    归并排序的基本思想: 将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并为一个子序列,经过多次合并后整合为一张有序表。 归并排序是稳定排序,它也是...
  • 一 、归并排序的思路: 归并排序采用的是分治的思想,就是将数组进行分隔,直到最小的单位(两个元素),然后对最小的单位进行排序。 最后将排好序的单位依次遍历到数组中。 1 将数组进行分隔,直到不能再分的最小...
  • 归并排序是一种稳定的排序算法,其时间复杂度为:O(nlogn) 本图片来源:https://blog.csdn.net/Silence_R/article/details/86524975 代码如下: #include<stdio.h> #define M 1000 int a[M],b[M]; void merge...
  • printf("排序后数组:"); printList(list,len); printf("\n"); return 0; } int printList(int* list,int len){ int i; for(i=0;i;i++){ printf("%d->",list[i]); } printf("\n\n"); return 0; } int ...
  • 归并排序 归并排序呢!原理是相对比较简单,但是实现时细节比较难理解的一种排序算法,建议自己写一写就知道哪里是难点。 大致思路:其的基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就...
  • 二路归并排序c语言实现

    千次阅读 2017-10-16 16:07:05
    二路归并排序 c 语言实现。
  • 话说这个东西写到凌晨3点27分,都没有写好.刚才睡醒了写完的.主要遇到的问题就是当数组大小不是2的幂的时候发生的 right_end 越界的时候.我的逻辑起初偏于复杂,后来重新...这貌似加深了我对归并排序的理解./*7-14-11-...
  • #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; int MergeSort(int sourceArr[], int tempArr[], int low, int high);...int Merge(int tempArr[], int sourceArr[], int low, int mid, int high);...
  • 前言:理论很枯燥、文字更烦人,但是这里将理论知识告诉大家并不是让大家一上来就看干巴巴的文字,因为我在代码中能注释的地方都进行了注释希望大家先跟着注释打一遍...归并排序:1.归并排序(merge sorting)简单地...
  • // L = 左边起始位置,R = 右边起始位置,RightEnd = 右边终点...{ // 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 int LeftEnd, NumElements, Tmp; int i; LeftEnd = R - 1; // 左边终点位置 ...
  • 两个版本的归并排序,仅在mergeSort函数的实现上有区别。 非递归版本需要考虑当前mid、r的值是否超出了数组右边界,若超出则取值为n-1。有可能出现mid、r均为n-1的情况,此时调用merge,临时数组R[]的大小 n2 = r - ...
  • 归并排序 算法思想:假定无序序列中有n个元素,则可以看成是n个有序的子序列,每个子序列长度为1.然后两两合并,得到n/2个长度为2或1的有序序列,再两两归并…如此重复之下,直到合并成长度为n的有序序列为止。 形如...
  • 归并排序C语言代码

    千次阅读 2013-09-07 13:23:29
    #include #include void merge(int *A,int p,int q,int r);//合并 void merge_sort(int *...//归并排序递归 int get_length(int *A);//获取数组长度 int main() { int n=0; int A[100]={1,45,9,90,46,456,3,78,234
  • 归并排序就是利用归并的思想实现的排序方法,原理是假设初始序列含有n个记录,则可以看出是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到n/2个长度为2或者1的有序子序列;再两两归并。。。。如此反复,...

空空如也

空空如也

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

归并排序c语言递归

c语言 订阅