1 归并排序(自顶向下)
归并排序是将数组分成两半分别进行排序，然后将结果进行归并。针对分成的两半也分别进行递归的归并处理。
3 4 2 1 5 6
先分成 3 4 2，和 1 5 6,然后分别对前、后部分进行归并排序，最后将排序好的2 3 4和1 5 6进行归并。
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
public void mergeSort(int[] a){
if(a == null || a.length <= 1) return;
int hi = a.length - 1;
aux = new int[a.length];
mergeSort(a,0,hi);
}
private void mergeSort(int[] a,int lo,int hi){
if(lo >= hi) return;
int mid = lo + (hi - lo)/2;
mergeSort(a,lo,mid);
mergeSort(a,mid+1,hi);
merge(a,lo,mid,hi);
}
private void merge(int[] a,int lo,int mid,int hi){
int i = lo;
int j = mid+1;
for(int k = lo; k <= hi; k++){
aux[k] = a[k];
}
for(int k = lo; k <= hi; k++){
if (i > mid) a[k] = aux[j++];
else if(j > hi) a[k] = aux[i++];
else if(aux[i] > aux[j]) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
2 归并排序(自底向上)
实现归并排序的另一种方法是由少到多的进行归并。首先两两归并，然后四四归并....直到完成。这种方法代码量很少。
1
2
3
4
5
6
7
8
9
10
11
public void mergeSort2(int[] a){
if(a == null || a.length <= 1) return;
int hi = a.length - 1;
int n = hi+1;
aux = new int[a.length];
for(int sz = 1; sz < n;sz += sz)
for(int lo = 0;lo <= hi-sz ; lo += sz + sz){
merge(a,lo,lo+sz-1,Math.min(hi,lo+sz+sz-1));
}
}
3 归并排序(链表实现)
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
35
36
37
38
39
40
41
42
43
44
class Node{
public int val;
public Node next;
public Node(int value){
this.val = value;
}
public Node(){}
}
public Node mergeSort3(Node node){
if(node == null || node.next == null) return node;
Node mid = findMid(node);
Node first = node;
Node r = mid.next;
mid.next = null;
Node left = mergeSort3(first);
Node right = mergeSort3(r);
return mergeNode(left,right);
}
private Node mergeNode(Node left,Node right){
Node dummyHead = new Node();
Node cur = dummyHead;
while(left != null && right != null){
if(left.val < right.val){
cur.next = left;
left = left.next;
}else{
cur.next = right;
right = right.next;
}
cur = cur.next;
}
cur.next = (left == null) ? right : left;
return dummyHead.next;
}
private Node findMid(Node node){
Node slow,fast;
slow = fast = node;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
4 快速归并
这个存在的问题是不是稳定排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void merge(int[] a,int lo,int mid,int hi){
for(int i = 0; i <= mid;i++){
aux[i] = a[i];
}
for (int j = mid+1; j <= hi; j++ ) {
aux[j] = a[hi-j+mid+1];
}
int i = lo; j=hi;
for(int k = lo; k <= hi; k++){
if(aux[i] > aux[j]) a[k] = a[j--];
else a[k] = a[i++];
}
}
5 归并排序的三个改进
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
private void merge(int[] src,int[] dst,int lo,int mid,int hi){
//避免复制数组带来的开销
int i = lo;
int j = mid+1;
for(int k = lo; k <= hi; k++){
if (i > mid) dst[k] = src[j++];
else if (j > hi) dst[k] = src[i++];
else if (less(src, j,i)) dst[k] = src[j++];
else dst[k] = src[i++];
}
//assert isSorted(dst, lo, hi);
}
private void sort(int[] src,int[] dst,int lo,int hi){
//小数组使用插入排序
if(hi <= lo + cutoff){
insertionSort(dst,lo,hi);
return;}
int mid = (hi - lo) / 2 + lo;
sort(dst,src,lo,mid);
sort(dst,src,mid+1,hi);
//如果a[mid]<a[mid+1]那么则不用merge数组，arraycopy比for循环快一些
if(!less(src, mid+1, mid)){
System.arraycopy(src, lo, dst, lo,hi-lo+1);
return;
}
merge(src, dst, lo, mid, hi);
}
private void sort(int[] a){
int hi = a.length - 1;
int[] aux = a.clone();
//System.err.println(Arrays.toString(aux));
sort(aux, a, 0, hi);
}