1
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
| package cn.vinc.sort;
import org.junit.Test;
import java.util.Arrays;
/**
* Created by vinc on 2016/11/15.
*/
public class SortTest {
@Test
public void testSort() {
int[] attr = new int[]{35, 2, 72, 1, 5, 6, 3, 34, 66, 7};
sortFlow(attr);
sortInsert(attr);
sortSelect(attr);
sortQuick(attr);
sortMerge(attr);
sortHash(attr);
printAttr(attr);
}
/**
* 快速排序
* 1取一值a，整个数组分两边，
* 2从左往右撸，撸到第一个比a大的值l，右边往左撸，
* 撸到第一个比a小的r,将l和r交换，
* 3只要l的下标比r下标小，重复2
* 4递归将第一步分成的两边继续
*
* @param attr
*/
private void sortQuick(int[] attr) {
quick(attr, 0, attr.length - 1);
}
private void quick(int[] attrs, int left, int right) {
printAttr(attrs);
int i = left;
int j = right;
int mid = attrs[(i + j) / 2];
while (i < j) {
while (attrs[i] < mid && i < right) {
i++;
}
while (attrs[j] > mid && j > left) {
j--;
}
if (i <= j) {
int tmp = attrs[i];
attrs[i] = attrs[j];
attrs[j] = tmp;
j--;
i++;
}
}
if (i < right) {
quick(attrs, i, right);
}
if (j > left) {
quick(attrs, left, j);
}
}
/**
* 合并排序
* 1将数组分为两组
* 2递归将其分为更小的数组,直到只有两位对比
* 3左数组left和右数组right都是有序的，挨个比较，
* 依次往总的attr里面放，判断哪个数组还有剩余也一通填到总的attr中
*
* @param attr
*/
private void sortMerge(int[] attr) {
int len = attr.length;
int middle = len / 2;
printAttr(attr);
if (len > 1) {
int[] left = Arrays.copyOfRange(attr, 0, middle);
int[] right = Arrays.copyOfRange(attr, middle, len);
sortMerge(left);
sortMerge(right);
merge(attr, left, right);
}
}
private void merge(int[] attr, int[] left, int[] right) {
int i = 0, l = 0, r = 0;
while (l < left.length && r < right.length) {
if (left[l] < right[r]) {
attr[i] = left[l];
i++;
l++;
} else {
attr[i] = right[r];
i++;
r++;
}
}
while (r < right.length) {
attr[i] = right[r];
i++;
r++;
}
while (l < left.length) {
attr[i] = left[l];
i++;
l++;
}
}
/**
* 选择排序
* 1每次都把最小的往左放
*
* @param attr
*/
private void sortSelect(int[] attr) {
for (int i = 0; i < attr.length; i++) {
int index = i;
int tmp = attr[i];
for (int j = i; j < attr.length; j++) {
if (attr[j] < tmp) {
index = j;
tmp = attr[j];
}
}
tmp = attr[i];
attr[i] = attr[index];
attr[index] = tmp;
}
}
/**
* 插入排序
* 从左往右，把当前下标的值插入到比它大的前面，比它小的后面
*
* @param attr
*/
private void sortInsert(int[] attr) {
int tmp;
for (int i = 0; i < attr.length; i++) {
for (int j = i; j > 0; j--) {
if (attr[j] < attr[j - 1]) {
tmp = attr[j];
attr[j] = attr[j - 1];
attr[j - 1] = tmp;
}
}
}
}
/**
* 冒泡排序
* 两两比较，大于就交换
*
* @param attr
*/
private void sortFlow(int[] attr) {
int tmp;
for (int i = 0; i < attr.length; i++) {
for (int j = 0; j < attr.length - 1; j++) {
if (attr[j] > attr[j + 1]) {
tmp = attr[j];
attr[j] = attr[j + 1];
attr[j + 1] = tmp;
}
printAttr(attr);
}
}
}
//希尔
private void sortHash(int[] attr) {
}
private void printAttr(int[] attr) {
for (int k : attr) {
System.out.print(k + ",");
}
System.out.println();
}
}
|
