湛江免费建站公司,可以做伦铜的网站,四川住房和城乡建设局网站,免费注册qq号文章目录 前言并归排序的原理总结 前言 提示#xff1a;有时我会担心你们发现我其实很普通。爱并不需要你与众不同。--查理麦克西《男孩、鼹鼠、狐狸和马》 并归排序算是经典的分治思想中的问题#xff0c;这个非常典型的题目。 并归排序的原理
并归排序#xff0c;简单来说… 文章目录 前言并归排序的原理总结 前言 提示有时我会担心你们发现我其实很普通。爱并不需要你与众不同。--查理·麦克西《男孩、鼹鼠、狐狸和马》 并归排序算是经典的分治思想中的问题这个非常典型的题目。 并归排序的原理
并归排序简单来说就是将大的序列先视为若干个比较小的数组份成几个比较小的结构然后是利用并归的思想实现的排序方式该算法采用经典的分治策略分就是将问题分divide成一些小的问题分别求解而治conquer)则将分的阶段得到的各个答案“合”在一起。 可以看到这种结构很想两个套在一起的满二叉树分的阶段可以理解为就是递归差分子序列的过程递归的深度为logn。也就是上图中的满二叉树。
再看看治的过程我们将两个已经有序的子序列合并成一个有序序列就是下面的满二叉树。比如上图中的最后一次合并就是将[4,5,7,8]和[1,2,3,6]两个已有的子序列合并成为最终序列[1,2,3,4,5,6,7,8]这个操作和合并两个有序数组完全一样不同的是这里将数组的两部分合并。
我们看下遍历处理元素的过程 试着分析下代码怎么写 /*** 并归排序 相当重要的* param array* param start* param end* param temp*/public void mergeSort(int[] array, int start, int end, int[] temp) {if (start end) {return;}// 左边mergeSort(array, start, (start end) 1, temp);// 右边mergeSort(array, ((start end) 1) 1, end, temp);merge(array, start, end, temp);}private void merge(int[] array, int start, int end, int[] temp) {// 取中间int middle (start end) 1;// 左边一半int left start;// 右边一半int right middle 1;int index left;// 循环赋值while(left middle right end){if (array[left] array[right]){temp[index] array[left];}else{temp[index] array[right];}}while(left middle){temp[index] array[left];}while(right end){temp[index] array[right];}// 重新赋值for(int i start; i end; i){array[i] temp[i];}}总结
提示并归排序手撕并归分治思想满二叉树排序算法 博主创作不易如果感觉文章内容对你有所帮助的话不妨三连一下再走呗。你们的支持就是我更新的动力
送上我从秋叶大佬哪里拿来的图表示感谢
