归并排序
基本原理
归并排序运用了分治的思想,先将数组二分成一个元素(一个元素时看为有序),然后将这些元素不断合并,每合并一次排一次序,最后就可以得到有序的数组。
比如说一个序列:12 ,23,1,44,233,10,9,8。我们先分成两段:12 ,23,1,44 和 233,10,9,8,
发现还能再分成4段:12 ,23 和 1,44———233,10 和 9,8。
再分成8段:12—23—1—44 和233—10—9—8。
这时候开始把子序列进行排序合并,一个元素就是有序的。所以不用排序。
合并成2个一组排序得到:12,23——1,44—-10,233—-8,9。
再合并成4个一组排序得到:1,12,23,44—-8,9,10,233。
最后合并得到最终结果:1,8,9,10,12,23,44,233。
合并过程看代码
链接:https://www.jianshu.com/p/b50a6034eb90
图解
这个图片蓝色部分就是拆的过程,而绿的部分为并的过程
代码实现
void paixu(int first,int mid,int last,int a[],int temp[])//这是合并过程 |
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Comment