1
package dwq.algo.sort;
2
3
import java.util.Arrays;
4
5
public 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是一個集合的元素,則各數(shù)不同。則可正確統(tǒng)計出存在兩數(shù)為和的對數(shù) 利用了原理:若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設(shè)置為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
現(xiàn)在一個到頭時
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
* 應(yīng)該有,這樣可以跳過與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);// 執(zhí)行三數(shù)中值分割法, 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,當(dāng)下標(biāo)從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

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206


207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241


242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301
