摘自 <Algorithms_4th> Robert Sedgewick, chapter 2 sorting
the following class illustrates the conventions that we will use
public class Example{ public static void sort(Comparable[] a) { /* See Algorithms 2.1, 2.2, 2.3, 2.4, 2.5, or 2.7. */ } private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } private static void show(Comparable[] a) { // Print the array, on a single line. for (int i = 0; i < a.length; i++) StdOut.print(a[i] + " "); StdOut.println(); } public static boolean isSorted(Comparable[] a) { // Test whether the array entries are in order. for (int i = 1; i < a.length; i++) if (less(a[i], a[i-1])) return false; return true; } public static void main(String[] args) { // Read strings from standard input, sort them, and print. String[] a = In.readStrings(); sort(a); assert isSorted(a); show(a); }} 1 elementary sort
1) selection sort 选择排序
first, find the smallest item in the array and exchange it with the first entry;
then, find the next smallest item and exchange it with the second entry; continute until the entire entry is sorted
Java 实例：
public class Selection{ public static void sort(Comparable[] a) { // Sort a[] into increasing order. int N = a.length; // array length for (int i = 0; i < N; i++) { // Exchange a[i] with smallest entry in a[i+1...N). int min = i; // index of minimal entr. for (int j = i+1; j < N; j++) if (less(a[j], a[min])) min = j; exch(a, i, min); } }} 2) insertion sort 插入排序
sort bridge hands: consider one at a time, insert each into proper place among those already sorted
computer implementation: before inserting the current item, move larger items one position to the right to make space
打扑克：摸牌 -> 插牌 -> 再摸牌 -> 插牌 -> ... ...
Java 实例：
public class Insertion{ public static void sort(Comparable[] a) { // Sort a[] into increasing order. int N = a.length; for (int i = 1; i < N; i++) { // Insert a[i] among a[i-1], a[i-2], a[i-3]... .. for (int j = i; j > 0 && less(a[j], a[j-1]); j--) exch(a, j, j-1); } }} 3) shell sort
a fast algorithm based on insertion sort
a h-sorted array: taking every hth entry(starting anywhere) yields a sorted subsequence
Java 实例：
public class Shell{ public static void sort(Comparable[] a) { // Sort a[] into increasing order. int N = a.length; int h = 1; while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, 1093, ... while (h >= 1) { // h-sort the array. for (int i = h; i < N; i++) { // Insert a[i] among a[i-h], a[i-2*h], a[i-3*h]... . for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) exch(a, j, j-h); } h = h/3; } }} 
2 merge sort 合并排序
1) overview
to sort an array, divide it into two havles, sort the two halves(recursively), and then merge the results
2) merge method
Java 实例：
public static void merge(Comparable[] a, int lo, int mid, int hi){ // Merge a[lo..mid] with a[mid+1..hi]. int i = lo, j = mid+1; for (int k = lo; k <= hi; k++) // Copy a[lo..hi] to aux[lo..hi]. aux[k] = a[k]; for (int k = lo; k <= hi; k++) // Merge back to a[lo..hi]. if (i > mid) a[k] = aux[j++]; else if (j > hi ) a[k] = aux[i++]; else if (less(aux[j], aux[i])) a[k] = aux[j++]; else a[k] = aux[i++];} 3) top-down mergesort
Java 实例：
public class Merge{ private static Comparable[] aux; // auxiliary array for merges public static void sort(Comparable[] a) { aux = new Comparable[a.length]; // Allocate space just once. sort(a, 0, a.length - 1); } private static void sort(Comparable[] a, int lo, int hi) { // Sort a[lo..hi]. if (hi <= lo) return; int mid = lo + (hi - lo)/2; sort(a, lo, mid); // Sort left half sort(a, mid+1, hi); // Sort right half merge(a, lo, mid, hi); // Merge results }} left half: sort(a,0,15) -> sort(a,0,7) -> sort(a,0,3) -> sort(a,0,1) -> merge(a,0,0,1) -> sort(a,2,3) -> merge(a,2,2,3) -> merge(a,0,1,3)
-> sort(a,4,7) -> sort(a,4,5) -> merge(a,4,4,5) -> sort(a,6,7) -> merge(a,6,6,7) -> merge(a,4,5,7) -> merge(a,0,3,7)
3 quick sort 快速排序
1) overview
partition an array into two subarrays, then sort the subarrays independently
2) partition method
three conditions:
a) the entry a[j] is in its final place in the array, for some j
b) no entry in a[lo] through a[j-1] is greater than a[j]
c) no entry in a[j+1] through a[hi] is less than a[j]
Java 实例：
private static int partition(Comparable[] a, int lo, int hi){ // Partition into a[lo..i-1], a[i], a[i+1..hi]. int i = lo, j = hi+1; // left and right scan indices Comparable v = a[lo]; // partitioning item while (true) { // Scan right, scan left, check for scan complete, and exchange. while (less(a[++i], v)) if (i == hi) break; while (less(v, a[--j])) if (j == lo) break; if (i >= j) break; exch(a, i, j); } exch(a, lo, j); // Put v = a[j] into position return j; // with a[lo..j-1] <= a[j] <= a[j+1..hi].} 
3) quick sort
Java 实例：
public class Quick{ public static void sort(Comparable[] a) { StdRandom.shuffle(a); // Eliminate dependence on input. sort(a, 0, a.length - 1); } private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) return; int j = partition(a, lo, hi); // Partition (see page 291). sort(a, lo, j-1); // Sort left part a[lo .. j-1]. sort(a, j+1, hi); // Sort right part a[j+1 .. hi]. }} 