算法图解
选择一个最大/小的数, 排到最前面
假设数组长度为 n
- i = 0 , 遍历 [i,n] 个数字,
选择一个最小的, 和 i 交换 - i + 1
- 重复 1 2 步骤, 直到 i == n
实现
1
2
3
4
5
6
7
8
9
10
int n = array.length;
int curMin;
for (int i = 0; i < n - 1; i++) {
curMin = i;
for (int j = i + 1; j < n; j++) {
curMin = array[curMin] > array[j] ? j : curMin;
}
doSwap(array, i, curMin);
}
时间复杂度
f(n) = n(n-1)/2 = O(n^2)
空间复杂度
O(1), 没有使用多余的空间
完整代码
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
class SelectionSort {
private static void sort(int[] array) {
if (array == null || array.length == 1) {
return;
}
int n = array.length;
int curMin;
for (int i = 0; i < n - 1; i++) {
curMin = i;
for (int j = i + 1; j < n; j++) {
curMin = array[curMin] > array[j] ? j : curMin;
}
doSwap(array, i, curMin);
}
}
private static void doSwap(int[] array, int x, int y) {
int t = array[x];
array[x] = array[y];
array[y] = t;
}
public static void main(String[] args) {
int[] array = {111, 522, 77, 98, 36, 12, 13, 48};
sort(array);
System.out.println(arrayToString(array));
}
private static String arrayToString(int[] array) {
StringBuilder builder = new StringBuilder();
for (int t : array) {
builder.append(t + " ");
}
return builder.toString();
}
}
