合并排序 Java实现

合并排序 MergeSort

算法步骤(分治法)

  • 将数组分成两半
  • 递归排序每一部分
  • 合并两部分
    basic plan of merge sort

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 合并
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
assert isSorted(a, lo, mid);
assert isSorted(a, mid, hi);
// 转存到辅助数组
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// 将辅助数组,即两个已经有序的数组,按按序放回原数组
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++]; // 做数组已经放完
else if (j > hi) a[k] = aux[i++]; // 右边数组已经放完
else if (less(aux[i], aux[j])) a[k] = aux[i++]; // 比较左右两个数组,较小的值先放
else a[k] = aux[j++];
}
assert isSorted(a, lo, hi);
}
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi){
if (hi <=lo) return;
int mid = lo+(hi-lo)/2;
// 数组分成两半
sort(a,aux,lo,mid);
sort(a,aux,mid+1,hi);
// 合并数组
merge(a,aux,lo,mid,hi);
}
public static void sort(Comparable[] a){
Comparable[] aux = new Comparable[a.length];
sort(a,aux,0,a.length-1);
assert isSorted(a);
}

优化

小数组使用插入排序

  • 减少合并排序产生无用的交换
  • Java8源码中合并排序使用插入排序的阈值是:7
1
2
3
4
5
if (hi <= lo + CUTOFF) {
//使用自己写的代码或者参考我之前的代码
Insertion.sort(dest, lo, hi);
return;
}

如果数组已经有序,则停止排序

  • 每部分数组都是分别有序的
  • 可以比较前半部分数组的最大值和后半部分的最小值来判断是否已经有序
  • 优化了部分有序的情况
1
2
3
if (!less(src[mid + 1], src[mid])) {
System.arraycopy(src, lo, dest, lo, hi - lo + 1);
}

减少复制到辅助数组的消费

  • 减少复制次数,节约时间
  • 假设辅助数组在递归调用前完成复制
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private static void mergeX_merge(Comparable[] src, Comparable[] dest, int lo, int mid, int hi) {
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) dest[k] = src[j++];
else if (j > hi) dest[k] = src[i++];
else if (less(src[j], src[i])) dest[k] = src[j++];
else dest[k] = src[i++];
}
}
private static void mergeX_sort(Comparable[] src, Comparable[] dest, int lo, int hi) {
if (hi <= lo + CUTOFF) {
Insertion.sort(dest, lo, hi);
return;
}
int mid = (lo + hi) >>> 1;
// 将中间的排序结果放在src中,可以直接从src开始合并
mergeX_sort(dest, src, lo, mid);
mergeX_sort(dest, src, mid + 1, hi);
if (!less(src[mid + 1], src[mid])) {
System.arraycopy(src, lo, dest, lo, hi - lo + 1);
}
mergeX_merge(src,dest,lo,mid,hi);
}

improve of merge sort

MERGESORT 和 MergexSort 性能比较

merge 和 mergeX camparison

java中使用的排序算法

  • Java8系统使用的系统Arrays.sort()排序算法主要是快速排序和合并排序
  • 从源码中可以看出: 对象类型使用合并排序,原始类型(int,double之类的)使用快速排序
  • Java8快速排序使用双轴快排(使用了十分复杂的各种优化手段)
    • 不同的长度使用不同的快排(单轴,双轴)
    • 按照某一策略选择合适的轴点
    • 灵活利用插入排序等排序方法
  • Java8合并排序使用TimSort(MergeSort的优化版本)
    • 还保留着MergeX版本的MergeSort算法
    • 优化如下图(但还是看不懂,以后有机会在啃。。。)

introduction of tim sort

各排序算法的性能总结

summary of performance

算法分析总结

  1. 还有排序算法没有涵盖如:
    • 堆排序,基数排序等
    • 并行排序算法等
  2. 没有涉及相关算法的理论推导,只有代码实现
  3. 这系列博客主要作为自己的思路提醒功能以及一个代码参考功能

个人总结

  • 拖拖拉拉,最后还是写完了。还是想想如何提高自己的效率吧!
  • 接下来应该开始搜索算法和图相关的算法吧
  • 还是需要继续整理自己的笔记。。历史遗留问题..

链接或参考资料

Algs4书籍网页
基本排序算法
快速排序
个人GitHub
算法可视化网站