首页 > 代码库 > 例24:归并排序
例24:归并排序
在之前算法考试之前看过归并排序,当时觉得好难啊,卧槽怎么会有这么难的排序算法啊什么的。但是如今再一看其实略一眼就明白了,其原理非常简单,就是通过分成两个已排序的数组合并到一块而已,合并的时候也没有什么特别的技巧,也就是一个个比较而已额。其步骤大概是(个人算法的步骤,还有其他的如多路归并排序或者细节有些不同,但我个人是这样写的):
1.将给定数组递归不断的分成两半,直到数组元素只有一个为止。
2.认为一个元素的数组是已排序的数组,此时数组已不能再分,开始合并。
3.两个数组合并时,元素由前到后有序一一进行比较,大者不动,小者添加到新的数组中并使数组遍历的下标i加一,直到两者其中一者元素遍历完成为止。
4.由于合并的两个数组都是有序的,将俩者中未完成的一组直接按顺序添加到新数组中,将新数组赋入原数组中,结束此轮递归进入上一轮,直到最初的递归函数为止,排序结束。
代码如下:
1 #include<stdio.h> 2 #include<stdlib.h> 3 4 void MergeArraySort(int a[],int first,int mid,int last,int temp[]) 5 { 6 int i = first,n = mid; 7 int j = mid+1,m = last; 8 int k = 0; 9 while(i<=n && j<=m) 10 { 11 if(a[i] < a[j]) 12 { 13 temp[k++] = a[i++]; 14 } 15 else 16 { 17 temp[k++] = a[j++]; 18 } 19 } 20 while(i<=n) 21 { 22 temp[k++] = a[i++]; 23 } 24 while(j<=m) 25 { 26 temp[k++] = a[j++]; 27 } 28 for(i = first; i<=last; i++) 29 { 30 a[i] = temp[i-first]; 31 } 32 } 33 34 void MergeSort(int a[],int first,int last,int temp[]) 35 { 36 if(first < last) 37 { 38 int mid = (first + last)/2; 39 MergeSort(a,first,mid,temp); 40 MergeSort(a,mid+1,last,temp); 41 MergeArraySort(a,first,mid,last,temp); 42 } 43 } 44 int main() 45 { 46 int pArray[20],nCount,tempArray[20]; 47 while(~scanf("%d",&nCount) && nCount) 48 { 49 for(int i = 0;i<nCount;i++) 50 { 51 scanf("%d",&pArray[i]); 52 } 53 MergeSort(pArray,0,nCount-1,tempArray); 54 for(int i = 0;i<nCount;i++) 55 { 56 printf("%d ",pArray[i]); 57 } 58 printf("\n"); 59 } 60 61 return 0; 62 }
例24:归并排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。