一、引言
我们知道,java中泛型排序使用归并排序或TimSort。归并排序以O(NlogN)最坏时间运行,下面我们分析归并排序过程及分析证明时间复杂度;也会简述为什么java选择归并排序作为泛型的排序算法。
二、图解归并排序过程
- 算法思想:采用分治法:
- 分割:递归地把当前序列平均分割成两半。
- 集成:在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)。
- 归并操作:指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
- 归并过程:取两个输入数组A、B和一个输出数组C以及3个索引index1,index2,index3分别指向三个数组开始端。并在A[index1]、B[index2]中较小者拷贝到数组C中的下一个位置,相关的索引+1。当A、B中有一个数组走完时,将另一个数组中的元素全部拷贝到数组C中。
假设输入数组A[1、7、9、13],B[5、8、15、17],算法过程如下。1与5比较,1存入数组C中;接下来7与5比较,5存入C中。
接着7与8比较,7存入C中;9与8比较,8存入C中。
接着这样的过程进行比较,直到13与15比较,13存入C中。
这时候A已经用完,将B中剩余的元素全部拷贝到C中即可。
从图中可以看出,合并两个排序表是线性的,最多进行N-1次比较(可以改变输入序列,使得每次只有一个数进入数组C,除了最后一次,最后一次至少有两个元素进入C)。对于归并排序,N=1的时候,排序结果是显然的;否则,递归将前半部分与后半部分分别归并排序。这是使用分治的思想。
三、java实现归并排序
public class MergeSort {
public static void main(String[] args) {
Integer[] integers = {7, 1, 13, 9, 15, 5, 8,17};
System.out.println(\"原序列:\" + Arrays.toString(integers));
mergeSort(integers);
System.out.println(\"排序后:\" + Arrays.toString(integers));
}
public static <T extends Comparable<? super T>> void mergeSort(T[] a) {
//因为merge操作是最后一行,所以任何时候只需要一个临时数组
T[] tmpArray = (T[]) new Comparable[a.length];
mergeSort(a, tmpArray, 0, a.length - 1);
}
private static <T extends Comparable<? super T>> void mergeSort(T[] a, T[] tmpArray, int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(a, tmpArray, left, center);
mergeSort(a, tmpArray, center + 1, right);
merge(a, tmpArray, left, center + 1, right);
}
}
/**
* 合并左右数据方法
*
* @param a :原数组
* @param tmpArray : 临时数组
* @param leftPos :左边开始下标
* @param rightPos:右边开始下标
* @param rightEnd:右边结束下标
* @param <T>:元素泛型
*/
private static <T extends Comparable<? super T>> void merge(T[] a, T[] tmpArray, int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
//合并操作
while (leftPos <= leftEnd && rightPos <= rightEnd) {
if (a[leftPos].compareTo(a[rightPos]) <= 0) {
tmpArray[tmpPos++] = a[leftPos++];
} else {
tmpArray[tmpPos++] = a[rightPos++];
}
}
// 复制前半部分
while (leftPos <= leftEnd) {
tmpArray[tmpPos++] = a[leftPos++];
}
//复制后半部分
while (rightPos <= rightEnd) {
tmpArray[tmpPos++] = a[rightPos++];
}
// 回写原数组
for (int i = 0; i < numElements; i++, rightEnd--) {
a[rightEnd] = tmpArray[rightEnd];
}
}
}
四、归并排序分析
我们假设N是2的幂,我们递归总可以均分为两部分。对于N=1,归并排序所用时间是常数,即O(1)。对于N个数归并排序的用时等于两部分时间之和再加上合并的时间。合并是线性的,因为最多使用N-1次比较。推导如下:
上面我们假设了N=2k,对于N不是2的幂(通常都是这种情况),其实,结果都是差不多的,也只是最多再多一次过程而已。
- 时间复杂度:从分析可以看出,归并排序的最好最坏都稳定在O(NlogN)。
- 空间复杂度:需要O(N)个临时空间进行合并操作。
- 稳定性:稳定。采用分治的思想,每次合并时,在前面的总会先存入临时数组内。
五、简谈java泛型为什么选择归并排序
归并排序与其他O(NlogN)排序算法相比,时间很依赖比较算法与在数组中移动元素(包括临时数组中)的相对开销。这是与语言环境有关的。对于Java来说,进行比较可能比较耗时(使用Comparator);但移动元素属于引用赋值,不是庞大对象的拷贝。归并算法在所有流行的使用比较的算法中使用最少的比较次数。另一个原因是归并排序是稳定的,这在某些特殊的场景特别重要。
六、总结
本篇通过画图详述了归并排序的过程,还通过数学证明归并排序时间复杂度稳定在O(NlogN);简谈了下java选择归并排序的原因。java中对于基本类型的排序,使用的是快速排序。