Intro

这是在《Algorithms 4th Editon》一书中学习的第一个排序算法,非常适合作为入门算法。

选择排序的时间复杂度

首先我们假设即将被排序的数列中有\(N\)个数,遍历整个数列一趟的时间复杂度为\(O(N)\),需要遍历的次数为多少次呢?\(N-1\),因此,我们可以说排序算法的时间复杂度为\( O(N^2) \)。

选择排序的思想

首先我们从一个从未排序过的数组开始,在第i次迭代中,我们在数组中剩下的项中找到最小的,然后我们将它和数组中的第一项交换,不断的进行递归直到数组中所有元素被排为正常的顺序。

代码实现

下面我们来看下代码层面的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package net.sunzhenyu.miscellaneous.dsa.sort;

public class SelectionSort implements Sort {

@Override
public void sort(Comparable[] c) {
int length = c.length;
for (int i = 0; i < length; i++) {
int index = i;
for (int j = i + 1; j < length; j++) {
if (less(c[j], c[index])) {
index = j;
}
}
exchange(c, i, index);
}
}

private void exchange(Comparable[] c, int i, int j) {
Comparable oldIValue = c[i];
c[i] = c[j];
c[j] = oldIValue;
}
}