《算法》第二章部分程序 part 1

▶ 书中第二章部分程序，加上自己补充的代码，包括插入排序，选择排序，Shell 排序

● 插入排序

  1 package package01;
  2 
  3 import java.util.Comparator;
  4 import edu.princeton.cs.algs4.StdIn;
  5 import edu.princeton.cs.algs4.StdOut;
  6 
  7 public class class01
  8 {
  9     private class01() { }
 10 
 11     public static void sort(Comparable[] a)                     // 插入排序
 12     {
 13         int n = a.length;
 14         for (int i = 0; i < n; i++)
 15         {
 16             for (int j = i; j > 0 && less(a[j], a[j - 1]); j--)
 17             {
 18                 exch(a, j, j - 1);
 19             }
 20             //assert isSorted(a, 0, i);                         // 检验是否正确排序
 21         }
 22         //assert isSorted(a);
 23     }
 24 
 25     public static void sort(Comparable[] a, int lo, int hi)     // 部分插入排序
 26     {
 27         for (int i = lo; i < hi; i++)
 28         {
 29             for (int j = i; j > lo && less(a[j], a[j - 1]); j--)
 30             {
 31                 exch(a, j, j - 1);
 32             }
 33         }
 34         //assert isSorted(a, lo, hi);
 35     }
 36 
 37     public static void sort(Object[] a, Comparator comparator)  // 自定义比较运算的插入排序
 38     {
 39         int n = a.length;
 40         for (int i = 0; i < n; i++)
 41         {
 42             for (int j = i; j > 0 && less(a[j], a[j - 1], comparator); j--)
 43             {
 44                 exch(a, j, j - 1);
 45             }
 46             //assert isSorted(a, 0, i, comparator);
 47         }
 48         //assert isSorted(a, comparator);
 49     }
 50 
 51     public static void sort(Object[] a, int lo, int hi, Comparator comparator)  // 自定义比较运算的部分插入排序
 52     {
 53         for (int i = lo; i < hi; i++)
 54         {
 55             for (int j = i; j > lo && less(a[j], a[j - 1], comparator); j--)
 56             {
 57                 exch(a, j, j - 1);
 58             }
 59         }
 60         //assert isSorted(a, lo, hi, comparator);
 61     }
 62 
 63     public static void sort2(Comparable[] a)    // 改良版本，不使用逐两元交换，而是位移 - 赋值方法
 64     {
 65         int n = a.length;
 66         boolean exchanges = false;
 67         for (int i = n - 1; i > 0; i--)   // 倒着扫描一遍，将最小元素放到开头，并统计倒序
 68         {
 69             if (less(a[i], a[i - 1]))
 70             {
 71                 exch(a, i, i - 1);
 72                 exchanges = true;
 73             }
 74         }
 75         if (exchanges == false)         // 如果没有交换，说明已经排好序了
 76             return;
 77 
 78         for (int i = 2; i < n; i++)     // 正常的排序，从第 3 元素开始
 79         {
 80             Comparable v = a[i];
 81             int j = i;
 82             for (; less(v, a[j - 1]); j--)
 83                 a[j] = a[j - 1];
 84             a[j] = v;
 85         }
 86         //assert isSorted(a);
 87     }
 88 
 89     public static void sort3(Comparable[] a)    // 改良版本，使用二分搜索寻找插入位置，减少判断次数
 90     {
 91         int n = a.length;
 92         for (int i = 1; i < n; i++)
 93         {
 94             Comparable v = a[i];
 95             int lo = 0, hi = i;
 96             for (; lo < hi;)
 97             {
 98                 int mid = lo + (hi - lo) / 2;
 99                 if (less(v, a[mid]))            // 左边强调整，右边弱调整
100                     hi = mid;
101                 else
102                     lo = mid + 1;
103             }
104 
105             for (int j = i; j > lo; --j)        // 用前面的位移 - 赋值方法
106                 a[j] = a[j - 1];
107             a[lo] = v;
108         }
109         //assert isSorted(a);
110     }
111 
112     public static int[] indexSort(Comparable[] a)   // 给定数组 a 及其排序后的数组 a'，对于任意 0 ≤ i ≤ a.length - 1，
113     {                                               // a'[i] == a[index[i]]，即 a 排序后第 i 位的值可用 a 和 index 来查找
114         int n = a.length;
115         int[] index = new int[n];
116         for (int i = 0; i < n; i++)
117             index[i] = i;
118 
119         for (int i = 0; i < n; i++)
120             for (int j = i; j > 0 && less(a[index[j]], a[index[j - 1]]); j--)
121                 exch(index, j, j - 1);
122         return index;
123     }
124 
125     private static boolean less(Comparable v, Comparable w)                 // v < w ?
126     {
127         return v.compareTo(w) < 0;
128     }
129 
130     private static boolean less(Object v, Object w, Comparator comparator)  // v < w ?
131     {
132         return comparator.compare(v, w) < 0;
133     }
134 
135 
136     private static void exch(Object[] a, int i, int j)  // 交换
137     {
138         Object swap = a[i];
139         a[i] = a[j];
140         a[j] = swap;
141     }
142 
143     private static void exch(int[] a, int i, int j)     // 间接交换，用于 indexSort
144     {
145         int swap = a[i];
146         a[i] = a[j];
147         a[j] = swap;
148     }
149 
150     // 检验是否完成排序的辅助函数，4 个
151     private static boolean isSorted(Comparable[] a)
152     {
153         return isSorted(a, 0, a.length);
154     }
155 
156     private static boolean isSorted(Comparable[] a, int lo, int hi)
157     {
158         for (int i = lo + 1; i < hi; i++)
159         {
160             if (less(a[i], a[i - 1]))
161                 return false;
162         }
163         return true;
164     }
165 
166     private static boolean isSorted(Object[] a, Comparator comparator)
167     {
168         return isSorted(a, 0, a.length, comparator);
169     }
170 
171     private static boolean isSorted(Object[] a, int lo, int hi, Comparator comparator)
172     {
173         for (int i = lo + 1; i < hi; i++)
174         {
175             if (less(a[i], a[i - 1], comparator))
176                 return false;
177         }
178         return true;
179     }
180 
181     private static void show(Comparable[] a)    // 输出结果
182     {
183         for (int i = 0; i < a.length; i++)
184             StdOut.println(a[i]);
185     }
186 
187     public static void main(String[] args)
188     {
189         String[] a = StdIn.readAllStrings();
190         int[] index = class01.indexSort(a);
191 
192         class01.sort(a);
193 
194         show(a);
195         for (int i = 0; i<a.length; i++)
196             StdOut.println(index[i]);
197     }
198 }

● 选择排序，结构类似前面的插入排序，删掉了检查等辅助函数

 1 package package01;
 2 
 3 import java.util.Comparator;
 4 import edu.princeton.cs.algs4.StdIn;
 5 import edu.princeton.cs.algs4.StdOut;
 6 
 7 public class class01
 8 {
 9     private class01() {}
10 
11     public static void sort(Comparable[] a)
12     {
13         int n = a.length;
14         for (int i = 0; i < n; i++)
15         {
16             int min = i;
17             for (int j = i + 1; j < n; j++)
18             {
19                 if (less(a[j], a[min]))
20                     min = j;
21             }
22             exch(a, i, min);
23         }
24     }
25 
26     public static void sort(Object[] a, Comparator comparator)
27     {
28         int n = a.length;
29         for (int i = 0; i < n; i++)
30         {
31             int min = i;
32             for (int j = i + 1; j < n; j++)
33             {
34                 if (less(a[j], a[min], comparator))
35                     min = j;
36             }
37             exch(a, i, min);
38         }
39     }
40 
41     private static boolean less(Comparable v, Comparable w)
42     {
43         return v.compareTo(w) < 0;
44     }
45 
46     private static boolean less(Object v, Object w, Comparator comparator)
47     {
48         return comparator.compare(v, w) < 0;
49     }
50 
51     private static void exch(Object[] a, int i, int j)
52     {
53         Object swap = a[i];
54         a[i] = a[j];
55         a[j] = swap;
56     }
57 
58     private static void show(Comparable[] a)
59     {
60         for (int i = 0; i < a.length; i++)
61             StdOut.println(a[i]);
62     }
63 
64     public static void main(String[] args)
65     {
66         String[] a = StdIn.readAllStrings();
67 
68         class01.sort(a);
69 
70         show(a);
71     }
72 }

● Shell 排序

 1 package package01;
 2 
 3 import edu.princeton.cs.algs4.StdIn;
 4 import edu.princeton.cs.algs4.StdOut;
 5 
 6 public class class01
 7 {
 8     private class01() {}
 9 
10     public static void sort(Comparable[] a)
11     {
12         int n = a.length, h = 1;
13         for (; h < n / 3; h = 3 * h + 1);   // a[n+1] = 3 * a[n] + 1 : 1, 4, 13, 40, 121, 364, 1093, ...
14         for (; h >= 1; h /= 3)              // 使用 h 递增序列来逐步排序
15         {
16             for (int i = h; i < n; i++)
17             {
18                 for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
19                     exch(a, j, j - h);
20             }
21             //assert isHsorted(a, h);
22         }
23         //assert isSorted(a);
24     }
25 
26     private static boolean less(Comparable v, Comparable w)
27     {
28         return v.compareTo(w) < 0;
29     }
30 
31     private static void exch(Object[] a, int i, int j)
32     {
33         Object swap = a[i];
34         a[i] = a[j];
35         a[j] = swap;
36     }
37 
38     private static boolean isHsorted(Comparable[] a, int h) // 检查函数与前面不同，保留
39     {
40         for (int i = h; i < a.length; i++)
41         {
42             if (less(a[i], a[i - h]))
43                 return false;
44         }
45         return true;
46     }
47 
48     private static boolean isSorted(Comparable[] a)
49     {
50         for (int i = 1; i < a.length; i++)
51             if (less(a[i], a[i - 1])) return false;
52         return true;
53     }
54 
55     private static void show(Comparable[] a)
56     {
57         for (int i = 0; i < a.length; i++)
58             StdOut.println(a[i]);
59     }
60 
61     public static void main(String[] args)
62     {
63         String[] a = StdIn.readAllStrings();
64 
65         class01.sort(a);
66 
67         show(a);
68     }
69 }