归并排序C语言,归并排序算法代码C语言

记录学习第五天
今天记录一下归并排序，因为在csdn里面没有找到特别清楚的解析，所以想自己写的认真一点，也查阅了一些资料，通过这篇博客记录一下；

归并排序，光看字面，归并，似乎是把两个合并到一起，也是由此我们也就先来说一下归并排序的基本原理。
如果有两个已经排序好的数组
{1,4,6,8}，{2,7,9,12}；
我们要把这两个数组合并再排序；
目标数组应该是{1,2,4,6,7,8,9,12}；
那是不是说，我们要把{1,4,6,8,2,7,9,12}这个数组，给按从小到大排序成为这个目标数组；
现在我们来实现一下；

我们用 i 来表示{1,4,6,8}中的第一个元素1；
用 j 来表示{2,7,9,12}中的第一个元素2；
用 k 来表示新数组也就是待排序的数组的第一个元素；
然后，重要的来了！

判断 i 和 j的大小；
如果i<j，那么就让k=i；i++，k++；
如果i>j，那么就让k=j；j++，k++；
最后，一定会有一个数组里面留下元素，例如上面这个；
{2,7,9,12}中会有9和12留下，最后再把9和12放在待排序的数组里面就好了！

所以如果有一个数组是{1,4,6,8,2,7,9,12}；
要对它进行排序，是不是应该给它分成两半分别是{1,4,6,8}和{2,7,9,12}；
在进行上面的操作；
其实很简单，我们设三个变量left代表1，mid代表8，right代表12；
left 到 mid 就是{1,4,6,8}，mid+1到 right 就是{2,7,9,12}

思路就是这样
接下来用代码实现一下

int merge(int r[],int s[],int left,int mid,int right){ int i,j,k; i=left; j=mid+1; k=left; while((i<=mid)&&(j<=right)) if(r[i]<=r[j]) { s[k] = r[i]; i++; k++; } else { s[k]=r[j]; j++; k++; } while(i<=mid) s[k++]=r[i++]; while(j<=right) s[k++]=r[j++]; return 0;}

这部分呢就是对{1,4,6,8,2,7,9,12}这样的数组进行排序的功能；

那会有同学问了，难道归并排序只能对这样的两个已经排序好的数组操作吗。
那他好垃圾啊；

不不不，当然不是这样的。
如果给一个数组{4,12,8,9,6,2,7}；
咱归并是毫不抗拒的，不过呢，只靠上面的代码显然是实现不出来的。
那怎么办呢，加东西喽！

这就要用到一个叫做分治法的一个思想；
怎么回事呢；
就是把{4,12,8,9,6,2,7}分成两半，去执行上面的排序功能，哎我发现分割后；
{4,12,8}和{9,6,2,7}这两个也不满足我排序功能的条件啊！

哎，那我就吧{4,12,8}和{9,6,2,7}都再次分成两半；再去归并排序；
啊？你说还不满足，那就再给我分！最后分成一堆就剩两个元素的数组，一定满足了吧！

现在，我们用递归的方法把这个给实现出来；

int merge_sort(int r[],int s[],int left,int right){ int mid; int t[20]; if(left==right) s[left]=r[right]; else { mid=(left+right)/2; merge_sort(r,t,left,mid); merge_sort(r,t,mid+1,right); merge(t,s,left,mid,right); } return 0;}

完全ojbk，归并排序的两个功能块我们就全实现出来了，现在我们来用主函数测试一下！

int main(){ int a[10]; int i; for(i=0;i<10;i++) scanf("%d",&a[i]); merge_sort(a,a,0,9); for(i=0;i<10;i++) printf("%d ",a[i]); return 0;}

然后再附上我的运行结果：

ok，今天的就到此结束了！
给自己点一个赞；
啊啊哈哈哈
归并排序就这样！
end。

UCloud云社区见缝插针游戏的实现途径UsinguseState()withanobjectasstate