杨陵区住房和城乡建设局网站,网站网页区别是什么意思,湖北省住房部城乡建设厅网站,php企业门户网站目录 1. 归并排序的原理
1.1 二路归并排序执行流程
2. 代码分析
2.1 代码设计
3. 性能分析
4. 非递归版本 1. 归并排序的原理
“归并”一词的中文含义就是合并、并入的意思#xff0c;而在数据结构中的定义是将两个或者两个以上的有序表组合成一个新的有序表。
归并排序…目录 1. 归并排序的原理
1.1 二路归并排序执行流程
2. 代码分析
2.1 代码设计
3. 性能分析
4. 非递归版本 1. 归并排序的原理
“归并”一词的中文含义就是合并、并入的意思而在数据结构中的定义是将两个或者两个以上的有序表组合成一个新的有序表。
归并排序(Merging Sort)就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录则可以看成是n个有序的子序列每个子序列的长度为1然后两两归并得到[n/2]表示不小于x的最小整数个长度为2或1的有序子序列再两两归并……如此重复直至得到一个长度为n的有序序列为止这种排序方法成为2路归并排序。
1.1 二路归并排序执行流程
原始序列49 38 65 97 76 13 27
1将原始序列看成7个只含有一个关键字的子序列显然这些子序列都是有序的。
子序列149子序列238子序列365子序列497子序列576子序列613子序列727 2两两归并形成若干有序二元组即49和38归并成{38 49}65和97归并成{65 97}76和13归并成{13 76}27没有归并对象保持原样{27}。第一趟二路归并排序结束结果如下
{38 49}{65 97}{13 76}{27} 3再将这个序列看成若干二元组子序列
子序列138 49子序列265 97子序列313 76子序列427
最后一个子序列长度可能是1也可能是2。 4继续两两归并形成若干有序四元组同样最后的子序列中不一定有4个关键字即{38 49}和{65 97}归并形成{38 49 65 97}{13 76}和{27}归并形成{13 27 76}。第二趟二路归并排序结束结果如下
{38 49 65 97}{13 27 76} 5最后只有两个子序列了再进行一次归并就可完成整个二路归并排序结果如下
13 27 38 49 65 76 97 2. 代码分析
大家先看看有没有思路 3,2,1 开始我的表演哈哈哈 请看图解 2.1 代码设计
根据图解我们要怎么设计方法呢
我打算把分解功能写成一个方法合并功能写成一个方法。具体实现如下 public static void mergeSort1(int[] array){mergeSortDivide(array,0, array.length - 1);}//分解private static void mergeSortDivide(int[] array,int left,int right){//终止条件left rightwhile(left right){return;}int mid (leftright)/2;//递归左子序列mergeSortDivide(array,left,mid);//递归右子序列mergeSortDivide(array,mid1,right);//合并merge(array,left,right,mid);}//合并private static void merge(int[] array,int start,int end,int mid){//左子序列从start开始int s1 start;//右子序列从mid1开始int s2 mid 1;//新建一个数组作为复制数组int[] tmp new int[end - start 1];//k表示中间数组的元素下标int k 0;//开始比较while(s1 mid s2 end){if(array[s1] array[s2]){//将小的值赋值给tmp[k]//小伙伴们这可以思考一下为什么不能先写array[s2] array[s1]?//等下看我下面的解析tmp[k] array[s1];} else{//array[s2] array[s1]的情况tmp[k] array[s2];}}//有剩余的数组//左子序列while(s1 mid){tmp[k] array[s1];}//右子序列while(s2 end){tmp[k] array[s2];}//将tmp数组的值赋值给array数组for(int i 0;itmp.length;i){array[istart] tmp[i];}} 回答问题为什么不能先写array[s2] array[s1] 答归并排序是稳定的。如果先写array[s2] array[s1]那么在s2开始的元素与s1开始的元素相等的话例如11那么本该在后面的1就会移到前面导致这段代码实现的归并排序不稳定了 3. 性能分析
时间复杂度空间复杂度O(n*log(n))O(n) 4. 非递归版本
上面的版本是递归版本接下来是非递归版本。 private static void merge(int[] array,int start,int end,int mid) {int s1 start;//int e1 mid;int s2 mid1;//int e2 end;int[] tmp new int[end-start1];int k 0;//tmp数组的下标while (s1 mid s2 end) {if(array[s1] array[s2]) {tmp[k] array[s1];}else {tmp[k] array[s2];}}while (s1 mid) {tmp[k] array[s1];}while (s2 end) {tmp[k] array[s2];}for (int i 0; i tmp.length; i) {array[istart] tmp[i];}}public static void mergeSort(int[] array) {int gap 1;while (gap array.length) {// i gap * 2 当前gap组的时候去排序下一组for (int i 0; i array.length; i gap * 2) {int left i;int mid leftgap-1;//有可能会越界if(mid array.length) {mid array.length-1;}int right midgap;//有可能会越界if(right array.length) {right array.length-1;}merge(array,left,right,mid);}//当前为2组有序 下次变成4组有序gap * 2;}}
