-
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++){ 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; }
如有不足,欢迎各位大佬指正
更多相关内容 -
048 归并排序 C语言 归并排序 C语言
2022-06-01 00:19:55048 归并排序 C语言 -
归并排序c语言
2016-02-18 19:17:36归并排序C语言实现,这里提供给大家分享,很好用! -
归并排序 C语言实现
2012-05-03 18:07:03好用的归并排序算法用C语言实现,欢迎下载 -
C语言实现排序算法之归并排序详解
2020-12-25 16:08:18排序算法中的归并排序(Merge Sort)是利用”归并”技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。 一、实现原理: 1、算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的... -
归并排序C语言实现
2011-12-03 16:28:33归并排序C语言实现 -
分治——归并排序c语言
2022-01-12 22:24:42归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补...概念:
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。
分治算法
分阶段 可以理解为就是递归拆分子序列的过程,递归深度为log2n。
治阶段 合并相邻有序子序列,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。
所以本质是先分:递归拆成2个2个的比较排序,再治:再相邻两个为单位排好序放入一个新的数组。要求两组排序每组内本身要排好序
C语言代码
#include<stdio.h> #define len 10000 int temp[len]; //临时数组用来存放有序数列部分 void merge(int [],int,int,int); //分治思想的“治”部分,将有序的两个部分合并成一个有序部分 void mergesort(int [],int,int); int main() { int n,a[1000],i; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); //主函数输入 mergesort(a,0,n-1); //归并函数(merge sort)处理 for(i=0;i<n;i++) //输出 printf("%d ",a[i]); return 0; } ///分治思想的“治”部分,将有序的两个部分合并成一个有序部分 void merge(int a[],int start,int mid,int end) { int i,j,k=0; i=start;j=mid+1; while(i<=mid && j<=end) { if(a[i]<a[j]) temp[k++]=a[i++]; else temp[k++]=a[j++]; } if(j==end+1) { while(i<=mid) temp[k++]=a[i++]; } if(i==mid+1) { while(j<=end) temp[k++]=a[j++]; } for(i=0,j=start;i<k;i++,j++) a[j]=temp[i]; } //递归调用 void mergesort(int a[],int start,int end) { if(start>=end) return; int mid=(start+end)/2; mergesort(a,start,mid); mergesort(a,mid+1,end); //先分 merge(a,start,mid,end); //再治 }
输出结果
-
归并排序 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语言实现
2015-03-05 16:42:24归并排序算法C语言实现,以比较为基础的时间复杂度下限 -
C语言数据结构 链表与归并排序实例详解
2020-08-31 16:22:31主要介绍了C语言数据结构 链表与归并排序实例详解的相关资料,需要的朋友可以参考下 -
排序算法之——归并排序 C语言实现
2020-12-20 19:11:58一 、归并排序的思路: 归并排序采用的是分治的思想,就是将数组进行分隔,直到最小的单位(两个元素),然后对最小的单位进行排序。 最后将排好序的单位依次遍历到数组中。 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语言版
2014-03-08 23:10:20C语言版归并排序算法完整代码,欢迎交流讨论。 -
冒泡排序,快速排序,希尔排序,归并排序C语言实现
2020-12-08 17:23:45图形实例4.C语言代码实现四、归并排序1.简单介绍2.算法原理3.图形实例4.C语言代码实现 一、冒泡排序 1.简单介绍 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列... -
归并排序c语言版
2021-11-21 17:23:05归并排序 ...2路归并排序代码(c语言) 思路:使用分治和递归的思想,Merge()函数负责将两段元素合并为一段元素,MergeSort()函数代表了归并排序,我们的基本思想是将整段元素分为两段: low-mid;mid+1 -
归并排序C语言
2019-11-19 10:52:36# include using namespace std ; int a [ 10 ] = { 13 , 27 , 19 , 2 , 8 , 12 , 2 , 8 , 30 , 89 } ; int b [ 10 ] ; void Merge ( int a [ ] , int ...//归并排序复杂度nlogn -
归并排序 C语言描述
2022-02-17 20:50:54利用递归进行对算法的...然后我在下面展示归并排序的算法模板: void m(int q[], int l, int r) { if (l >= r) return; //递归必备的终末状态 int mid = l + r >> 1; m(q, l, mid), m(q, mid + 1, r -
基础算法3——归并排序 c语言
2022-02-05 14:56:553.归并排序 主要思想:分治。 步骤: 1.确定分界点:mid=(left+right)/2; 2.分别递归排序right and left; 3.归并左右两边。 归并方法:1)两指针分别指向两数组的第一个数,数列最小值是两者其中... -
归并排序(C语言完整代码)
2022-04-19 21:45:36归并排序是建立在归并操作上的一种有效的算法,该算法是采用分治法的一个非常典型的应用, 是一种稳定的排序算法。 将已有的子序列合并,得到完全有序的的序列;即先使每个子序列有序,再使子序列段间有序。 若将... -
归并排序C语言代码
2017-02-27 19:19:58归并排序C语言代码 -
C语言归并排序详解
2021-05-25 03:36:34C语言归并排序详解发布日期:2015-12-31 11:16来源:标签:编程语言C教程C语言归并排序C语言归并排序算法本章我们主要学习C语言实现排序算法之归并排序,对归并排序的原理及实现过程做了非常详细的解读,下面我们就做... -
归并排序(C语言)详解
2020-05-04 10:30:32今天记录一下归并排序,因为在csdn里面没有找到特别清楚的解析,所以想自己写的认真一点,也查阅了一些资料,通过这篇博客记录一下; 归并排序,光看字面,归并,似乎是把两个合并到一起,也是由此我们也就先来说... -
三路归并_C语言_三路归并排序_三路归并_
2021-10-03 04:31:20每次将待排序数组分为大致相等的三部分分别进行排序,然后再进行归并。 -
C语言——归并排序
2021-12-09 21:56:42C语言——归并排序 归并排序用到了分治思想,借助递归的方式对一串数字进行排序,整个过程分为分开和合并两个过程。其实归并排序的思想并不难理解,但是用代码实现它却并不容易,我们要写两个函数去分别实现这个过程... -
归并排序(C语言简单实现)
2020-11-29 16:31:49归并排序(C语言简单实现) 归并排序(Merging Sort)利用的就是归并的思想实现的排序方法。原理是:假设初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2]个长度为2... -
C语言实现归并排序算法
2021-05-19 12:59:13C语言实现归并排序算法归并排序是创建在归并操作上的一种有效的排序算法。下面小编为大家整理了C语言实现归并排序算法,希望能帮到大家!归并排序(Merge sort)是创建在归并操作上的一种有效的排序算法。该算法是采用...
收藏数
13,155
精华内容
5,262