Java排序算法总结

Posted on | In , |

先定义一些排序算法通用的API

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
public class Sort{
  public static void sort(Comparable[] a){
    // 新建排序算法对象
    Quick quick = new Quick();
    quick.sort(a);
  }
  
  protected static boolean less(Comparable v, Comparable w){
    return (v.compareTo(w) < 0);
  }
  
  protected static void exc (Comparable[] a, int i, int j){
    Comparable t = a[i];
    a[i] = a[j];
    a[j] = t;
  }
  
  protected static void show(Comparable[] a){
    for (int i =0; i<a.length; i++)
    	System.out.print(a[i] + " ");
    System.out.println();
  }
  
  protected static boolean isSorted(Comparable[] a){
    for (int i=0; i<a.length; i++)
    	if (less(a[i], a[i+1])) return false;
    return true;
  }
  
  public static void main(String[] args){
    Comparable[] a = {'A','R','E','U','K','I','D','D','I','N','G','M','E'};
    sort(a);
    assert isSorted(a);
    show(a);
  }
}

插入排序 / Insertion Sort

1
2
3
4
5
6
7
8
9
public class Insertion extends Sort{
  public static void sort(Comparable[] a){
    int N = a.length;
    for (int i=0; i<N; i++){
      for (int j = i; j>0 && less(a[j],a[j-1]); j--)
      	exc(a,j,j-1);
    }
  }
}

选择排序 / Selection Sort

1
2
3
4
5
6
7
8
9
10
11
12
public class Selection extends Sort{
  public static void sort(Comparable[] a){
    int N = a.length;
    for (int i=0; i<N; i++){
      int min = i;
      for (int j=i+1; j<N; j++){
        if (less(a[j],a[min])) min = j;
      }
      exc(a,i,min);
    }
  }
}

希尔排序 / Shell Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Shell extends Sort{
  public static void sort(Comparable[] a){
    int N = a.length();
    int h = 1;
    while (h < N/3) (h = 3*h + 1);
    while (h >= 1){
      for (int i=h; i<N; i++){
        for (int j=i; j>=h && less(a[j],a[j-h]); j-=h)
        	exc(a,j,j-h);
      }
      h = h/3;
    }
  }
}

归并排序 / 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
public class Merge extends Sort{
  
  private static Comparable[] aux;
  
  public static void sort(Comparable[] a){
    aux = new Comparable[a.length];
    sort(a,0,a.length-1);
  }
  
  public static void sort(Comparable[] a, int lo, int hi){
    if (hi<=lo) return;
    int mid = lo + (hi-lo)/2;
    sort(a,lo,mid);
    sort(a,mid,hi);
    Merge(a,lo,mid,hi);
  }
  
  public static void Merge(Comparable[] 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 (less(aux[i],aux[j])) a[k] = aux[i++];
      else a[k] = a[j++];
    }
  }  
}

快速排序 / Quick 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
public class Quick extends Sort{
  public static void sort(Comparable[] a){
    StdRandom.shuffle(a);
    sort(a, 0, a.length);
  }
  
  public static void sort(Comparable[] a, int lo, int hi){
    if (hi<=lo) return;
    int j = partition(a,lo,hi);
    sort(a,lo,j-1);
    sort(a,j+1,hi);
  }
  
  public static int partition(Comparable[] a, int lo, int hi){
    int i = lo;
    int j = hi+1;
    Comparable v = a[lo];
    while (true){
      while (less(a[++i],v)) if (i == hi) break;
      while (less(v,a[--j])) if (j == lo) break;
      if (i >= j) break;
      exc(a,i,j);
    }
    // 跟 j 交换位置，因为 i 此时位置在 a[i] > v 处而 a[j] < v
    exc (a,lo,j);
    return j;
  }
}

三向切分快速排序 / Quick 3 Ways

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Quick3Way extends Quick{
  public static void sort(Comparable[] a, int lo, int hi){
    if (lo>=hi) return;
    int i = lo+1;
    int gt = hi;
    int lt = lo;
    Comparable v = a[lo];
    while ( i <= gt ){
      int cm = v.compareTo(a[i]);
      if (cm > 0) exc(a,i,gt--);
      else if (cm < 0) exc(a,lt++,i++);
      else i++;
    }
    sort(a,lo,lt-1);
    sort(a,gt+1,hi);
  }
}

堆排 / StackSort

数组最大堆：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class MaxPQ<Key extends Comparable<Key>> {
  private Key[] pq;
  private N = 0;
  
  public boolean less(int i, int j){
    return pq[i].compareTo(pq[j]) < 0;
  }
  
  public void exc(int i, int j){
    Key temp;
    temp = pq[i];
    pq[i] = pq[j];
    pq[j] = temp;
  }
  
  public void swin(int k){
    while (k>1 && less(k/2,k)){
      exc(k/2,k);
      k /= 2;
    }
  }
  
  public void sink(int k){
    while (2*k <= N){
      int j = 2*k;
      if (j<N && less(2*k, 2*k+1)) j++;
      if (!less(k,j)) break;
      exc(k,j);
      k = j;
    }
  }
  
  public MaxPQ (int maxN){
    pq = (Key[]) new Comparable[maxN+1];
  }
  
  public boolean isEmpty(){
    return N==0;
  }
  
  public void insert(Key v){
    pq[++N] = v;
    swin(N);
  }
  
  public int size(){
    return N;
  }
  
  public Key delMax(){
    Key max = pq[1];
    exc(N--,1);
    pq[N+1] = null;
    sink(1);
    return max;
  }
}
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
public class StackSort{
  
  private Comparable[] a;
  private int N = a.length;
  
  public void StackSort(int max){
    a = new Comparable[max];
  }
  
  public void sort(Comparable[] a){
    for (int k = a.length/2; k>=1; k--)
    	sink(k);
    while (N>1){
      exc(N--,1);
      sink(N);
    }
  }
  
  public boolean less(int i, int j){
    return a[i].compareTo(j) < 0;
  }
  
  piublic void sink(int k){
    while (2*k <= a.length){
      int j = 2*k;
      if (less(j,j+1)) j++;
      if (!less(k,j)) break;
      exc(k,j);
      k = j;
    }
  }
  
  public void exc(int i, int j){
    Comparable t = a[i];
    a[i] = a[j];
    a[j] = t;
  }
}

就这么多吧。