|
|
Posted on 2009-10-26 11:53 小强摩羯座 阅读(174) 评论(0) 编辑 收藏 所属分类: 算法编程
1 package dwq.algo.sort;
2
3import java.util.Arrays;
4
5public class Sorting
6   {
7
8 public static void main(String[] args)
9  {
10 // int []a = {2,1, 3, 5, 4};
11 //
12 // bubbleSort(a);
13 // System.out.println( Arrays.toString(a));
14 // //Integer []b = {7,1, 3, 5, 4};
15 // //
16 Integer[] b = { 11, 8, 4, 7 };
17 insertSort(b, b.length);
18
19 System.out.println(Arrays.toString(b));
20
21 int[] c = { 2, 1, 3, 2, 5, 4, 2, 3, 3, 4, 5, 6 ,-10, 110};// 12
22 heapSort(c);
23
24 System.out.println("heap sort " + Arrays.toString(c));
25
26 int[] re = const2ElemSum(c, 3);
27 if (re.length == 2)
28 System.out.println(Arrays.toString(re));
29
30 int[] a = { 1, 2, 3, 8, 5, 9, 17 };
31 int re2 = const2ElemSum2(a, 8);
32 System.out.println(re2);
33 }
34
35 /** *//**
36 *
37 * @param a
38 * @param x
39 * @return :int[2]:i,j when a[i] + a[j] == x
40 */
41 static int[] const2ElemSum(int[] a, int x)
42 {
43 quickSort(a);
44 int sum = 0;
45 for (int i = 0, j = a.length - 1; i < j;)
46 {
47 sum = a[i] + a[j];
48 if (sum == x) return new int[] { a[i], a[j] };
49 else if (x > sum) i++;
50 else j--;
51 }
52 return new int[] {};
53 }
54
55 /** *//**
56 * 题目条件：a是一个集合的元素，则各数不同。则可正确统计出存在两数为和的对数 利用了原理：若a, x-a存在于集合中则条件满
57
58足。所以
59 *
60 * @param a
61 * @param x
62 * @return
63 */
64 static int const2ElemSum2(int[] a, int x)
65 {
66 // int []b = new int[a.length];
67 int[] c = new int[2 * a.length];
68 for (int i = 0; i < a.length; i++)
69 {
70 c[i] = a[i];
71 // b[i] = x - a[i];
72 c[a.length + i] = x - a[i];
73 }
74 quickSort(c);
75 int count = 0;
76 for (int i = 1, tmp = c[0]; i < c.length; i++)
77 {
78 if (tmp == c[i])
79 {
80 count++;
81 if (i < c.length - 1)
82 tmp = c[++i];// tmp设置为i的下一个
83 } else tmp = c[i];
84 }
85 return count / 2;
86 }
87
88 /** *//**
89 * 严蔚敏书上的冒泡排序算法，有利用交换与否进行改进
90 *
91 * @param a
92 */
93 static void bubbleSort(int[] a)
94 {
95 boolean change = true;
96 for (int i = a.length - 1; i > 0 && change; i--)// i > 0即可因为i =
97 // 1时有二个元素比较过了。一个无需比较
98 {
99 for (int j = 0; j < i; j++)
100 {
101 change = false;
102 if (a[j] > a[j + 1])
103 {
104 change = true;
105 a[j] = a[j] + a[j + 1] - (a[j + 1] = a[j]);
106 }
107 }
108 }
109 }
110
111 static void quickSort(int[] a)
112 {
113 System.out.println(" call my QS");
114 quickSort(a, 0, a.length - 1);
115 }
116
117 static void quickSort(int[] a, int left, int right)
118 {
119 if (left < right) // 这里是if, 给写成了while
120 {
121 // int j = partition(a, left, right);
122 int pivot = a[left];
123 int i = left;
124 int j = right + 1;
125 while (true)// 一定是true, 使用break退出的
126 {
127 while (i < right && a[++i] <= pivot)
128 ;
129 while (j > left && a[--j] >= pivot)
130 ; // a[left] end it.
131 // 错误代码：每次i都必然会++的，但是这显然不对
132 // while( a[++i] <= pivot | a[--j] >= pivot) if(j <= i) break;
133 if (j <= i) break; // 这里也必须有相等，否则对2,1排不了，因为其实本身这时交换就没有意义了,=出
134
135现在一个到头时
136 a[j] = a[j] + a[i] - (a[i] = a[j]);
137 }
138 a[j] = a[j] + a[left] - (a[left] = a[j]);
139 quickSort(a, left, j - 1);
140 quickSort(a, j + 1, right);
141 }
142 }
143
144 /** *//**
145 * 1、最后pivot位置确定:pivot 取在第一个，为从后到前指针交流，取最后一个话，与从前到后指针交换 2、对等号的有无，
146 * 应该有，这样可以跳过与pivot相等，移动快一次
147 *
148 * @param a
149 * @param left
150 * @param right
151 * @return
152 */
153 static int partition(int a[], int left, int right)
154 {
155 int pivot = a[left];
156 int i = left;
157 int j = right + 1;
158 while (true)// 一定是true, 使用break退出的
159 {
160 while (i < right && a[++i] <= pivot)
161 ;
162 while (j > left && a[--j] >= pivot)
163 ; // a[left] end it.
164 if (i >= j)
165 break;
166 a[j] = a[j] + a[i] - (a[i] = a[j]);
167 }
168 a[j] = a[j] + a[left] - (a[left] = a[j]);
169 return j;
170 }
171
172 static <T extends Comparable<T>> void quickSort(T[] data)
173 {
174 quickSort(data, 0, data.length - 1);
175 }
176
177 private static <T extends Comparable<T>> void quickSort(T[] data, int left,
178 int right)
179 {
180 if (left + 10 <= right)
181 {
182 T pivot = middle3(data, left, right);// 执行三数中值分割法， pivot =
183 // data[last]
184 int i = left, j = right - 1;
185 for (;;)
186 {
187 while (data[++i].compareTo(pivot) < 0)
188 {
189 }
190 while (data[--j].compareTo(pivot) > 0)
191 {
192 }
193 if (i < j)
194 {
195 swap(data, i, j);
196 } else
197 {
198 break;
199 }
200 }
201 swap(data, i, right - 1);
202 quickSort(data, left, i - 1);
203 quickSort(data, i + 1, right);
204 } else
205 {
206 System.out.println("insertionSort() in Quicksort");
207 insertionSort(data);
208 }
209 }
210
211 private static <T extends Comparable<T>> T middle3(T[] data, int left,
212 int right)
213 {
214 int center = (left + right) / 2;
215 if (data[center].compareTo(data[left]) < 0)
216 {
217 swap(data, left, center);
218 }
219 if (data[right].compareTo(data[left]) < 0)
220 {
221 swap(data, left, right);
222 }
223 if (data[right].compareTo(data[center]) < 0)
224 {
225 swap(data, center, right);
226 }
227 swap(data, center, right - 1); // 取中元素最后放到了末尾
228 return data[right - 1];
229 }
230
231 private static <T extends Comparable<T>> void swap(T[] data, int i, int j)
232 {
233 T temp = data[i];
234 data[i] = data[j];
235 data[j] = temp;
236 }
237
238 // 插入排序;
239 public static <T extends Comparable<T>> void insertionSort(T[] data)
240 {
241 System.out.println("insertSort() ");
242 int j;
243 for (int p = 1; p < data.length; p++)
244 {
245 T temp = data[p];
246 for (j = p; j > 0 && temp.compareTo(data[j - 1]) < 0; j--)
247 {
248 data[j] = data[j - 1];
249 }
250 data[j] = temp;
251 }
252 }
253
254 public static <T extends Comparable<T>> void insertSort(T[] data, int n)
255 {
256 if (n == 1) return;
257 insertSort(data, n - 1);
258 int j;
259 for (int p = 1; p < n; p++)
260 {
261 T temp = data[p];
262 for (j = p; j > 0 && temp.compareTo(data[j - 1]) < 0; j--)
263 {
264 data[j] = data[j - 1];
265 }
266 data[j] = temp;
267 }
268 }
269
270 static void heapSort(int[] a)
271 {
272 //builder the heap
273 int size = a.length;
274 for(int i = (size-1)/2; i >= 0;i--)
275 maxHeapity(a, i, size);
276 // for i= size - 2, exchagne to last
277 for(int i = size -1;i > 0;i--)
278 {
279 a[0] = a[0] + a[i] - ( a[i] = a[0]);
280 size -= 1;
281 maxHeapity(a, 0, size);
282 }
283 }
284
285 static void maxHeapity(int[] a, int i, int size)
286 {
287 int left = (i << 1) + 1; // i * 2 + 1,当下标从0正式开始时
288 int right = (i << 1) + 2;
289 int t;
290 if ( left<size && a[left]>a[i] ) t = left;
291 else t = i;
292 if (right < size && a[right] > a[t])
293 t = right;
294 if( t != i)
295 {
296 a[t] = a[i] + a[t] - ( a[i] = a[t]);
297 maxHeapity(a, t, size);
298 }
299 }
300 }
301
|