排序算法

您所在的位置：网站首页 › 递归的流程图怎么画 › 排序算法

排序算法

#排序算法| 来源: 网络整理| 查看: 265

归并排序：

采用了分治策略就是将原问题分解为一些规模较小的相似子问题，然后递归解决这些子问题，最后合并其结果作为原问题的解。

归并的核心思想将两个有序的数组合并成一个大的有序的数组，通过递归把待排序数组变成完全有序数组。

归并的核心算法就是如何将2个数组合并

算法思想：

将待排序数组一直往下分解直到不可分解为止也就是一个数为一个子数组

然后对这些子数组层层合并(合并里有排序的过程)得到最后的有序数组

分解的过程很简单就是一直递归向下分解直到一个元素一组为止

合并原理：

其实就是合并2个有序数组的算法:

首先要有一个临时数组temp 以及2个索引分别指向2个数组的首地址让2个索引对应的值进行比较谁对应的值小把值小的放入temp 然后当前索引++ 再循环比较肯定会有一个数组索引先到头在对另一个数组剩下的元素遍历放入temp即可

然后再把合并好的数组放会原数组对应的为止就算完成此次合并

以 {3,4,6,10} {2,5,7,8} 为例作图给大家演示下：

两个数组索引对应的值进行比较小的放进临时数组索引++ 然后继续比较

↓ ↓ 34610 2578 temp2

↓ ↓ 34610 2578 temp23

↓ ↓ 34610 2578 temp234

↓ ↓ 34610 2578 temp2345

↓ ↓ 34610 2578 temp23456

↓ ↓ 34610 2578 temp234567

↓ ↓34610 2578 temp2345678

此时其中一个数组索引已经到头了然后直接对另一个数组剩余元素进行遍历放入temp即可

可能有些童鞋会有疑问为什么剩下的直接放进去就行？

因为2个数组都是有序数组此数组当前索引对应的值比另一个数组最大值都大此数组剩余元素值肯定大于另一个数组而且还是从小到大排列的所以直接放入temp就可以了麻

temp234567810

动图展示：

算法代码: public class Sort { public static void main(String[] args) { int[] a={10,4,6,3,8,2,5,7}; //归并排序 mergeSort(a,0,a.length-1); } private static void mergeSort(int[] a, int left, int right) { if(left

【本文地址】

排序算法

排序算法

今日新闻

推荐新闻