首页 / 算法 / 《算法》第二章部分程序 part 1
《算法》第二章部分程序 part 1
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《算法》第二章部分程序 part 1，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7957字，纯文字阅读大概需要12分钟。
内容图文
? 书中第二章部分程序，加上自己补充的代码，包括插入排序，选择排序
● 插入排序
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 }
内容总结
以上是互联网集市为您收集整理的《算法》第二章部分程序 part 1全部内容，希望文章能够帮你解决《算法》第二章部分程序 part 1所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】