深入理解java源码 mergeSort实现
操作数据的时候我们经常会用到排序。而java提供的排序是
Collections.sort(List<T>);
我们点进去可以发现在Collections类中有两个sort方法,区别是一个带有自定义比较器。底层实现一致。
public static <T extends Comparable<? super T>> void sort(List<T> list) {
list.sort(null);
}
再接着跟进,在List类中,会将我们传入的List 转成数组类型。调用Arrays 提供的sort方法。
@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
因为我们这里没有传入比较器。所以调用第一个sort(a)
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
在这里,判断条件有一个参数,是否使用经典的归并排序。在jdk1.7以后默认的排序更改为了TimSort,这个排序算法这里先不谈。我们来看看归并排序。
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
这里有一个数组的拷贝a.clone();对于引用类型来说是浅拷贝,不建议使用(改变其中一个会影响另一个,因为指向的是同一个对象)。
对于基本类型数据这里是深拷贝(两者的改变互不影响,创建了一个副本返回一个新的对象)。
然后就进入了关键的归并排序mergeSort()
private static void legacyMergeSort(Object[] a) {
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
// src 源数组
// dest 目标数组
// low 开始下标
// high 尾端下标
// off 偏移量 对数组指定位置进行排序需要用到这个。
@SuppressWarnings({"unchecked", "rawtypes"})
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
// 数组区间的数据长度
int length = high - low;
// 这里是对归并排序的一个优化,因为在对于少量数据的数组使用插入排序的效率更高。
// 所以这里加了一个插入排序的阈值为7
if (length < INSERTIONSORT_THRESHOLD) {
// 这里实现的是插入排序。将数组分为两个区间,其中一个为已排序区间,开始只有一个就是数组的
// 第一个元素,其余的都为未排序区间,将未排序区间的每一个元素与已排序区间做比较,找到合适
// 的位置插入
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
// Recursively sort halves of dest into src
int destLow = low;
int destHigh = high;
low += off;
high += off;
// >>>1 表示做无符号位右移1 位 ,即除以2 .
int mid = (low + high) >>> 1;
// 这里进行递归排序,将 dest 数组的一半排序成 src数组
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);
// 这里是对归并排序的第二个优化部分。
// 即进行归并排序的两部分分别排序后
// 前半部分的最大值 小于 后半部分的最小值,即已经是有序数组,就直接将 排序后的src 数组
// 复制 到dest 数组
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}
// 在这里将分别排序后的两个数组进行合并
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
// 前半部分值小
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
// 后半部分值小
else
dest[i] = src[q++];
}
}
这里贴一张归并排序的过程图
归并排序在合并前后的位置不会发生变化,所以是一种稳定的排序算法。
归并排序的时间复杂度为O(nlogn).
归并排序的空间复杂度为O(n),从代码中可以看出,归并排序会复制一个原数组,多开辟出来一块内存空间。
以上就是我对归并排序的理解和总结了。