一、
1.
2.
3.
二、代码
1 package algorithms.mergesort22; 2 3 import algorithms.util.StdIn; 4 import algorithms.util.StdOut; 5 6 /****************************************************************************** 7 * Compilation: javac MergeBU.java 8 * Execution: java MergeBU < input.txt 9 * Dependencies: StdOut.java StdIn.java 10 * Data files: http://algs4.cs.princeton.edu/22mergesort/tiny.txt 11 * http://algs4.cs.princeton.edu/22mergesort/words3.txt 12 * 13 * Sorts a sequence of strings from standard input using 14 * bottom-up mergesort. 15 * 16 * % more tiny.txt 17 * S O R T E X A M P L E 18 * 19 * % java MergeBU < tiny.txt 20 * A E E L M O P R S T X [ one string per line ] 21 * 22 * % more words3.txt 23 * bed bug dad yes zoo ... all bad yet 24 * 25 * % java MergeBU < words3.txt 26 * all bad bed bug dad ... yes yet zoo [ one string per line ] 27 * 28 ******************************************************************************/ 29 30 /** 31 * The <tt>MergeBU</tt> class provides static methods for sorting an 32 * array using bottom-up mergesort. 33 * <p> 34 * For additional documentation, see <a href="http://algs4.cs.princeton.edu/21elementary">Section 2.1</a> of 35 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 36 * 37 * @author Robert Sedgewick 38 * @author Kevin Wayne 39 */ 40 public class MergeBU { 41 42 // This class should not be instantiated. 43 private MergeBU() { } 44 45 // stably merge a[lo..mid] with a[mid+1..hi] using aux[lo..hi] 46 private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) { 47 48 // copy to aux[] 49 for (int k = lo; k <= hi; k++) { 50 aux[k] = a[k]; 51 } 52 53 // merge back to a[] 54 int i = lo, j = mid+1; 55 for (int k = lo; k <= hi; k++) { 56 if (i > mid) a[k] = aux[j++]; // this copying is unneccessary 57 else if (j > hi) a[k] = aux[i++]; 58 else if (less(aux[j], aux[i])) a[k] = aux[j++]; 59 else a[k] = aux[i++]; 60 } 61 62 } 63 64 /** 65 * Rearranges the array in ascending order, using the natural order. 66 * @param a the array to be sorted 67 */ 68 public static void sort(Comparable[] a) { 69 int N = a.length; 70 Comparable[] aux = new Comparable[N]; 71 for (int n = 1; n < N; n = n+n) { 72 for (int i = 0; i < N-n; i += n+n) { 73 int lo = i; 74 int m = i+n-1; 75 int hi = Math.min(i+n+n-1, N-1); 76 merge(a, aux, lo, m, hi); 77 } 78 } 79 assert isSorted(a); 80 } 81 82 /*********************************************************************** 83 * Helper sorting functions. 84 ***************************************************************************/ 85 86 // is v < w ? 87 private static boolean less(Comparable v, Comparable w) { 88 return v.compareTo(w) < 0; 89 } 90 91 // exchange a[i] and a[j] 92 private static void exch(Object[] a, int i, int j) { 93 Object swap = a[i]; 94 a[i] = a[j]; 95 a[j] = swap; 96 } 97 98 99 /*************************************************************************** 100 * Check if array is sorted - useful for debugging. 101 ***************************************************************************/ 102 private static boolean isSorted(Comparable[] a) { 103 for (int i = 1; i < a.length; i++) 104 if (less(a[i], a[i-1])) return false; 105 return true; 106 } 107 108 // print array to standard output 109 private static void show(Comparable[] a) { 110 for (int i = 0; i < a.length; i++) { 111 StdOut.println(a[i]); 112 } 113 } 114 115 /** 116 * Reads in a sequence of strings from standard input; bottom-up 117 * mergesorts them; and prints them to standard output in ascending order. 118 */ 119 public static void main(String[] args) { 120 String[] a = StdIn.readAllStrings(); 121 MergeBU.sort(a); 122 show(a); 123 } 124 }