【算法】排序

Posted on | In ,

选择排序

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

示意

Markdown
Markdown

实现

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
public class Selection {
	public void sort(Comparable[] a){
		for (int i = 0; i < a.length - 1; i++){
			int minIndex = i;
			
			for (int j = i + 1; j < a.length; j++){
				if (!less(a[minIndex], a[j]))
					minIndex = j;
			}
			
			exch(a, i, minIndex);
		}
	}
	
	private boolean less(Comparable a, Comparable b){
		return a.compareTo(b) < 0;
	}
	
	private void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	
	public void show(Comparable[] a){
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		
		System.out.println();
	}
}

特点

对于长度为N的数组，选择排序需要大约N^2/2次比较和N次交换。

  1. 运行时间和输入无关
  2. 数据移动是最少的

插入排序

将元素插入到其他已经有序的数组中的适当位置。为了要给插入的元素腾出空间，需要将其余所有元素在插入之前都向右移动一位。

示意

Markdown

实现

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
public class Insertion {
	public void sort(Comparable[] a){
		for (int i = 1; i < a.length; i++){			
			for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
				exch(a, j-1, j);
		}
	}
	
	private boolean less(Comparable a, Comparable b){
		return a.compareTo(b) < 0;
	}
	
	private void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	
	public void show(Comparable[] a){
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		
		System.out.println();
	}
}

特点

对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要～N^2/2次比较以及~N^2/4次交换。最坏情况下需要～N^2/2次比较和～N^2/2次交换，最好情况下需要N-1次比较和0次交换。

插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一。

  1. 所需的时间取决于输入中元素的初始顺序，对于部分有序的数组十分高效，也很适合小规模数组

比较

对于随机排序的无重复主键的数组，插入排序和选择排序的运行时间是平方级别的，两者之比应该是一个较小的常数。

  1. 插入排序不会访问索引右侧的元素，而选择排序不会访问索引左侧的元素
  2. 插入排序所需的比较次数平均只有选择排序的一半

希尔排序

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。在进行排序时，如果h很大，就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的h序列，都能够将数组排序。

示意

Markdown
Markdown

实现

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
public class Shell {
	public void sort(Comparable[] a){
		int h = 1;
		
		while (h <= a.length / 3)
			h = 3 * h + 1;
		
		while (h >= 1){
			for (int i = h; i < a.length; i++){
				for (int j = i; j > h && less(a[j], a[j-h]); j -= h)
					exch(a, j-h, j);
			}
			
			h = (h - 1) / 3;
		}
	}
	
	private boolean less(Comparable a, Comparable b){
		return a.compareTo(b) < 0;
	}
	
	private void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	
	public void show(Comparable[] a){
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		
		System.out.println();
	}
}

特点

使用递增序列1，4，13，40，121，364…的希尔排序所需的比较次数不会超出N的若干倍数乘以递增序列的长度。

  1. 希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。
  2. 希尔排序可以用于大型数组。它对任意排序（不一定是随机的）的数组表现也很好。
  3. 希尔排序对于中等大小的数组它的运行时间是可以接受的。它的代码量很小，且不需要使用额外的内存空间。

归并排序

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。

递归实现的归并排序是算法设计中分治思想的典型应用。

示意

Markdown

特点

  1. 能够保证将任意长度为N的数组排序所需时间和NlogN成正比，所需的额外空间和N成正比。
  2. 可以用归并排序处理数百万甚至更大规模的数组，这是插入排序或者选择排序做不到的。

自顶向下的归并排序

示意

Markdown

实现

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
public class Merge {
	private Comparable[] aux;
	
	public void sort(Comparable[] a){
		aux = new Comparable[a.length];
		
		sort(a, 0, a.length-1);
	}
	
	private void sort(Comparable[] a, int lo, int hi){
		if (lo == hi)
			return;
		
		int mid = (hi + lo) / 2;
		
		sort(a, lo, mid);
		sort(a, mid+1, hi);
		merge(a, lo, mid, hi);
	}
	
	private void merge(Comparable[] a, int lo, int mid, int hi){
		int j = lo;
		int k = mid + 1;
		
		for (int i = lo; i <= hi; i++)
			aux[i] = a[i];
		
		for (int i = lo; i <= hi; i++){
			if (j > mid)
				a[i] = aux[k++];
			else if (k > hi)
				a[i] = aux[j++];
			else if (less(aux[j], aux[k]))
				a[i] = aux[j++];
			else
				a[i] = aux[k++];
		}
	}
	
	private boolean less(Comparable a, Comparable b){
		return a.compareTo(b) < 0;
	}
	
	public void show(Comparable[] a){
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		
		System.out.println();
	}
}

特点

对于长度为N的任意数组，自顶向下的归并排序需要1/2*NlgN至NlgN次比较，最多需要访问数组6NlgN次。

自底向上的归并排序

示意

Markdown

实现

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
public class Merge {
	private Comparable[] aux;
	
	public void sort(Comparable[] a){
		aux = new Comparable[a.length];
		
		for (int i = 1; i < a.length; i *= 2){
			for (int j = 0; j < a.length; j += 2*i)
				merge(a, j, j+i-1, Math.min(j+2*i-1, a.length-1));
		}
	}
	
	private void merge(Comparable[] a, int lo, int mid, int hi){
		int j = lo;
		int k = mid + 1;
		
		for (int i = lo; i <= hi; i++)
			aux[i] = a[i];
		
		for (int i = lo; i <= hi; i++){
			if (j > mid)
				a[i] = aux[k++];
			else if (k > hi)
				a[i] = aux[j++];
			else if (less(aux[j], aux[k]))
				a[i] = aux[j++];
			else
				a[i] = aux[k++];
		}
	}
	
	private boolean less(Comparable a, Comparable b){
		return a.compareTo(b) < 0;
	}
	
	public void show(Comparable[] a){
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		
		System.out.println();
	}
}

特点

对于长度为N的任意数组，自底向上的归并排序需要1/2*NlgN至NlgN次比较，最多访问数组6NlgN次。

  1. 比较适合用链表组织的数据。只需要重新组织链表链接就能将链表原地排序（不需要创建任何的链表结点）。
  2. 归并排序是一种渐进最优的基于比较排序的算法。

快速排序

快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。

示意

Markdown
Markdown

实现

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.util.Random;

public class Quick {
    private static Random random;
    private static long seed;

    static {
        seed = System.currentTimeMillis();
        random = new Random(seed);
    }
    
	public void sort(Comparable[] a){
		shuffle(a);
		sort(a, 0, a.length-1);
	}
	
	private void sort(Comparable[] a, int lo, int hi){
		if (hi <= lo)
			return;
		
		int i = partition(a, lo, hi);
		sort(a, lo, i-1);
		sort(a, i+1, hi);
	}
	
	private int partition(Comparable[] a, int lo, int hi){
		int i = lo;
		int j = hi;
		
		while (i < j){
			while (i < j && less(a[i], a[lo]))
				i++;
			
			while (i < j && less(a[lo], a[j]))
				j--;
			
			exch(a, i, j);
		}
		
		exch(a, lo, i);
		
		return i;
	}
	
	private boolean less(Comparable a, Comparable b){
		return a.compareTo(b) < 0;
	}
	
	private void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	
	public void show(Comparable[] a){
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		
		System.out.println();
	}
	
    private static void shuffle(Object[] a) {
        if (a == null) throw new IllegalArgumentException("argument array is null");
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int r = i + uniform(n-i);
            Object temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }
    
    private static int uniform(int n) {
        if (n <= 0) throw new IllegalArgumentException("argument must be positive");
        return random.nextInt(n);
    }
}

特点

将长度为N的无重复数组排序，快速排序平均需要~2NlnN次比较（以及1/6的交换），最多需要约N^2/2次比较，但随机打乱数组能够预防这种情况。

  1. 快速排序实现简单、适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。
  2. 快速排序是原地排序（只需要一个很小的辅助栈），且将长度为N的数组排序所需的时间和NlgN成正比。
  3. 非常脆弱，在实现时要非常小心才能避免低劣的性能。

比较

快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。

在第一种情况中，递归调用发生在处理整个数组之前；在第二种情况中，递归调用发生在处理整个数组之后。

在归并排序中，一个数组被等分为两半；在快速排序中，切分的位置取决于数组的内容。

三向切分的快速排序

在有大量重复元素的情况下，快速排序的递归性会使元素全部重复的子数组经常出现。一个简单的想法是将数组切分为三部分，分别对应小于、等于和大于切分元素的数组元素。这样的切分能够将和切分元素相等的元素归位，就不会被包含在递归调用处理的子数组之中了。

对于包含大量重复元素的数组，三向切分的快速排序将排序时间从线性对数级降低到了线性级别。

示意

Markdown

实现

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.util.Random;

public class Quick {
    private static Random random;
    private static long seed;

    static {
        seed = System.currentTimeMillis();
        random = new Random(seed);
    }
    
	public void sort(Comparable[] a){
		shuffle(a);
		sort(a, 0, a.length-1);
	}
	
	private void sort(Comparable[] a, int lo, int hi){
		if (hi <= lo)
			return;
		
		int lt = lo;
		int gt = hi;
		int i = lo + 1;
		Comparable v = a[lo];
		
		while (i <= gt){
			if (a[i].compareTo(v) < 0){
				exch(a, lt, i);
				lt++;
				i++;
			}
			else if (a[i].compareTo(v) > 0){
				exch(a, gt, i);
				gt--;
			}
			else
				i++;
		}
		
		sort(a, lo, lt-1);
		sort(a, gt+1, hi);
	}
	
	private void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	
	public void show(Comparable[] a){
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		
		System.out.println();
	}
	
    private static void shuffle(Object[] a) {
        if (a == null) throw new IllegalArgumentException("argument array is null");
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int r = i + uniform(n-i);
            Object temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }
    
    private static int uniform(int n) {
        if (n <= 0) throw new IllegalArgumentException("argument must be positive");
        return random.nextInt(n);
    }
}

特点

对于大小为N的数组，三向切分的快速排序需要~(2ln2)NH次比较。其中H为由主键值出现频率定义的香农信息量。

堆排序

堆排序可以分为两个阶段。在堆的构造阶段中，将原始数组重新组织安排进一个堆中（从右至左用sink函数构造子堆）；然后在下沉排序阶段，从堆中按递减顺序取出所有元素得到排序结果（将堆中的最大元素删除，然后放入堆缩小后数组空出的位置）。

示意

Markdown
Markdown
Markdown

实现

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
public class Heap {
	public void sort(Comparable[] a){
		int n = a.length;
		
		for (int i = n / 2; i >= 1; i--)
			sink(a, i, n);
		
		while (n > 1){
			exch(a, 0, n-1);
			sink(a, 1, --n);
		}
	}
	
	private boolean less(Comparable a, Comparable b){
		return a.compareTo(b) < 0;
	}
	
	private void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	
	private void sink(Comparable[] a, int k, int n){
		while (2 * k <= n){
			int j = 2 * k;
			
			if (j < n && less(a[j-1], a[j]))
				j++;
			
			if (!less(a[k-1], a[j-1]))
				break;
			
			exch(a, k-1, j-1);
			
			k = j;
		}
	}
	
	public void show(Comparable[] a){
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		
		System.out.println();
	}
}

特点

用下沉操作由N个元素构造堆只需少于2N次比较以及少于N次交换。

将N个元素排序，堆排序只需少于（2NlgN+2N）次比较（以及一半次数的交换）。

总结

快速排序是最快的通用排序算法。

Markdown