小学校园网站建设方案工作职责,加强政协网站建设,兰州网站关键字优化,十大产品设计公司1. 归并排序原理 归并排序#xff08;MERARE-SORT#xff09;简单来说就是将大的序列先视为若干个比较小的数组#xff0c;分成比较小的结构#xff0c;然后是利用归并的思想实现的排序方法#xff0c;该算法采用经典的分治策略#xff08;分就是将问题分成一些小的问题分…1. 归并排序原理 归并排序MERARE-SORT简单来说就是将大的序列先视为若干个比较小的数组分成比较小的结构然后是利用归并的思想实现的排序方法该算法采用经典的分治策略分就是将问题分成一些小的问题分别求解而治则将分的阶段得到的各答案“合”在一起。 归并排序算法就是应用归并思想的一个典型例子。在归并排序中我们首先将未排序的数组不断地划分成两个子数组直到子数组的长度为1。然后我们合并子数组使得子数组按照排序规则排列最后得到排序完成的数组。 分治法可以看作是分而治之的意思也就是把一个复杂的问题分成两个或更多的相同或相似的子问题直到最后子问题可以简单的直接求解从而使得原问题的解即子问题的解的合并。 都需要递归地解决子问题并在最后合并子问题的解。 上图就是将 一个大的数组二分成一个个小的数组知道最后每个划分的数组只有一个元素的时候开始进行合并这种操作就是分阶段可以理解为递归拆分子序列的过程递归的深度为logn。治阶段将两个已经有序的子序列合并成一个有序序列。
遍历时处理元素的过程 总结归并排序的思路 首先将原数组二分的拆分直到最后问题变成最小的时候也就是每个子数组只有一个元素开始进行第二步。将两个子数组合并按照合并两个有序数组的方式进行按照图中每个左右子树从下往上然后再将左右子树合并每个子树最后都是一个有序数组。 public static void mergeSort(int[] array, int start, int end, int temp[]){if (start end){return;}mergeSort(array, start, (start end) / 2,temp);mergeSort(array, (start end) / 2 1, end,temp);merge(array, start, end, temp);}public static void merge(int[] array, int start, int end, int[] temp){int middle (start end) /2;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];}//将temp中的元素依次转到array中for (int i start; i end; i){array[i] temp[i];}}
