排序算法之——归并排序分析

排序算法之——归并排序分析

引言

思路

基本操作时合并两个已排序的序列，若将输出放到第3个序列中，则该算法可以通过对输入数据一趟排序来完成。

序列一分为二子序列递归排序合并有序子序列

整个流程如下图所示：

其中，最复杂的是合并有序子序列这一步骤。为了简单，我们就拿上图逐层合并中倒数第二步来分析。

合并2,3,4,6和1,5,7,8这两个有序子序列。

我们只需要关注这两个序列的首元素，从中挑选出较小的那一个元素放入辅助数组中。 此步将元素1移出原序列，放入辅助数组。

上图最下方的元素1位于辅助数组中。继续比较，将2放入辅助数组

接下来直接贴一个完整的图：

可以看到当某个子序列变空之后，直接将另一个子序列追加到辅助数组即可。

代码

public static > void mergeSort(E[] array) { mergeSort(array,0,array.length - 1);}private static > void mergeSort(E[] array,int left,int right) { if (left < right) { int mid = left + (right - left) / 2;// (left + right)/2 /** * 序列一分为二 * mid属于左边的数组，mid+1属于右边的数组 */ mergeSort(array,left,mid);//对左子序列排序 mergeSort(array,mid + 1,right);//对右子序列排序 //优化：如果array[mid]小于array[mid+1],则不需要进行归并了 if (array[mid].compareTo(array[mid+1]) < 0) { return; } // 归并 // 注意，传入的是mid+1 merge(array,left,mid+1,right); }}/** * * @param array * @param left 指向左边数组，左边数组开始位置 * @param right 指向右边数组，右边数组开始位置 * @param rightEnd 右边数组最后一个元素位置 */private static > void merge(E[] array,int left, int right, int rightEnd) { E[] aux = (E[]) new Comparable[array.length];//辅助数组 int leftEnd = right - 1;//左边数组最后位置 int auxIndex = left;//辅助数组开始位置 int num = rightEnd - left + 1;//元素总数 while (left <= leftEnd && right <= rightEnd) { //比较两个序列的首元素 if (array[left].compareTo(array[right]) <0) { aux[auxIndex++] = array[left++]; } else { aux[auxIndex++] = array[right++]; } } /** * 拷贝剩下的元素 * 以下两个while循环，只有一个会执行 */ while (left <= leftEnd) { aux[auxIndex++] = array[left++]; } while (right <= rightEnd) { aux[auxIndex++] = array[right++]; } //将辅助数组拷贝回原数组，注意是逆序的方式 for (int i = 0; i < num; i++,rightEnd --) { array[rightEnd] = aux[rightEnd]; }}

复杂度和稳定性

时间复杂度

稳定性

因为交换元素时，大小相等的情况下可以不交换，所以归并排序是稳定的；

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。