团购网站前景,263企业邮箱报价,如何建设社区网站,即将上市的手机目录 什么是递归排序#xff1a; 图解#xff1a;
递归方法#xff1a; 代码实现#xff1a; 思路分析#xff1a; 非递归方法#xff1a; 思路#xff1a; 代码实现#xff1a; 思路分析#xff1a; 什么是递归排序#xff1a; 先将数据分解成诺干个序列#xff0…目录 什么是递归排序 图解
递归方法 代码实现 思路分析 非递归方法 思路 代码实现 思路分析 什么是递归排序 先将数据分解成诺干个序列将子序列合并排序得到有序的序列再与旁边子序列合并即先使每个子序列有序再使子序列段间有序。最后将两个有序表合并成⼀个有序表。 图解 递归方法 代码实现
public static void mergeSort(int[] arr) {mergeSortChild(arr,0,arr.length-1);}private static void mergeSortChild(int[] arr,int left,int right) {if(left right) {return;}int mid (left right) / 2;mergeSortChild(arr,left,mid);mergeSortChild(arr,mid 1,right);//开始合并merge(arr,left,mid,right);}private static void merge(int[] arr, int left, int mid, int right) {//临时数组int[] tmpArr new int[right - left 1];int k 0;int s1 left;int e1 mid;int s2 mid 1;int e2 right;while(s1 e1 s2 e2) {if(arr[s1] arr[s2]) {tmpArr[k] arr[s1];}else {tmpArr[k] arr[s2];}}while(s1 e1) {tmpArr[k] arr[s1];}while(s2 e2) {tmpArr[k] arr[s2];}//拷贝临时数组给到arrfor (int i 0; i k; i) {arr[i left] tmpArr[i];}} 思路分析 与快速排序类似结合上图定义一个 mid 作为 一段数据的中间下标然后依次往下分左边的新 left 和 right 为上一个段数据的 left 和 mid 右边的新 left 和 right 为上一个段数据的 mid 1 和 right。分解结束条件为 当 left 与 right 相遇了。 对于merge方法结合此图 此图是原数据的左边的一段数据定义一个临时数组把下面的两个已经有序的 一段数据合并成给到临时数组方法是s1 与 s2 比较哪个小先给到临时数组直到一方为放完。之后把没放完的一方全部给到临时数组。k就得到临时数组的元素个数。 最后通过for循环把临时数组的数据拷贝到原始数组里但是有个要注意的地方 看蓝色圈出来的区域3 9 4 2 的那段数据的 3 和 9 一段小数据如果merge方法 的for循环是这样的 for (int i 0; i k; i) {arr[i] tmpArr[i];} 那么将临时数组的数据拷贝到原始数组里会出现问题。 原始数组的 元素3 下标应该是 4如果按照从 0 下标开始 会给到原始数组 0 下标位置这样是不对的但如果加上了 left for (int i 0; i k; i) {arr[i left] tmpArr[i];} 这样就能确保 元素3 给到了 原始数组 4 下标的位置。 非递归方法 思路 上图对于8个原数据我们先把数据从 1个1个有序6和101和73和92和4一直到 2个2个 有序6 10和1 7 3 9 和 2 4 来进行排序那么最后 4个4个 有序6 10 1 7 和3 9 2 4就能完成排序了。 首先定义了 i 作为遍历数组使用l 作为 左边起始r 作为结束位置m 是 他们的中间位置。 定义一个 gap 作为 临界值初始化为1循环结束 gap 每次 乘以 2 当 gap 为 数组长度时不进入循环。 上图是 gap 为 2 的时候其他参数赋值如上图。 代码实现
public static void feidigui(int[] arr) {int gap 1;while(gap arr.length) {for (int i 0; i arr.length; i i 2*gap) {int left i;int mid left gap - 1;if(mid arr.length) {mid arr.length-1;}int right midgap;if(right arr.length) {right arr.length-1;}merge(arr,left,mid,right);}gap * 2;}}private static void merge(int[] arr, int left, int mid, int right) {//临时数组int[] tmpArr new int[right - left 1];int k 0;int s1 left;int e1 mid;int s2 mid 1;int e2 right;while(s1 e1 s2 e2) {if(arr[s1] arr[s2]) {tmpArr[k] arr[s1];}else {tmpArr[k] arr[s2];}}while(s1 e1) {tmpArr[k] arr[s1];}while(s2 e2) {tmpArr[k] arr[s2];}//拷贝临时数组给到arrfor (int i 0; i k; i) {arr[i left] tmpArr[i];}} 思路分析 结合代码和此图当 gap 为 2 时i 下一次取值为 i 2*gap确保后面的3 9 2 4也能进行有序排列。 要注意的是 过程可能会出现上面三种情况当 mid 超过了 数组长度 就越界了就要把 mid 设置为数组的最后一个位置right 同理。此过程不会影响 merge 方法的出现错误。相当于处理边界值 归并排序是稳定的。 七大算法的总结图
