你知道和你不知道的选择排序

什么是选择排序?

首先贴上从wiki上弄下来的关于选择排序的定义。

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

更加直白的解释是,每次都从数组中选出最大或者最小的元素,然后放到数组的左边。

选择排序的过程展示

老规矩,我们还是通过动图来看一下选择排序的过程。以下的gif来自于wiki。

然后我们再通过我制作的gif,配上数据再了解一下过程。假设我们的待排序数组还是[5, 1, 3, 7, 6, 2, 4]。

选择最小值的算法

我们使用Java来实现最常见的,选择最小值的选择排序,其代码如下。

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
private void selectionSort(int[] arr) {
int min;
int minIndex;
for (int i = 0; i < arr.length - 1; i++) {
min = arr[i];
minIndex = -1;
for (int j = i; j < arr.length; j++) {
if (arr[j] < min) {
min = arr[j];
minIndex = j;
}
}
// 排序结束 交换位置
if (minIndex != -1) {
exchange(arr, i, minIndex);
}
}
}

private void exchange(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};
selectionSort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]

假设数组的长度为7,那么算法就需要进行6轮。如果数组的长度为n,则算法需要进行n - 1轮。

每一轮,算法都会从剩下的待排序元素中,选出最小的元素,并将其与当前数组下标为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
25
26
27
28
29
30
private void selectionSort(int[] arr) {
int max;
int maxIndex;

for (int i = 0; i < arr.length - 1; i++) {
max = Integer.MIN_VALUE;
maxIndex = -1;
for (int j = 0; j < arr.length - i; j++) {
if (max < arr[j]) {
max = arr[j];
maxIndex = j;
}
}

// 排序结束 交换位置
if (maxIndex != -1) {
exchange(arr, maxIndex, arr.length - i - 1);
}
}
}

private void exchange(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};
selectionSort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]

这个思想与选择最小值的算法完全一样,只不过是选择了最大值,每次都将剩余序列的最大值放到数组的有序序列的最左边。

那么到此,选择排序最常见的两种写法我们都已经实现了。有的兄弟可能会想,这篇博客是不是结束了。其实我们可以从上面两个算法中想到可以优化的点。

既然我们有两个选择,一种选择最小值,另外一种选择最大值。那么我们为什么不同时进行两个操作呢?

下面我们就来实现这种算法。

同时选择最大值和最小值

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
private void selectionSort(int[] arr) {
int min;
int max;
int minIndex;
int maxIndex;

for (int i = 0; i <= arr.length / 2; i++) {
min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;
minIndex = -1;
maxIndex = -1;
for (int j = i; j < arr.length - i; j++) {
if (arr[j] < min) {
min = arr[j];
minIndex = j;
}
if (arr[j] > max) {
max = arr[j];
maxIndex = j;
}
}
// 排序结束 交换位置
if (minIndex != -1) {
if (maxIndex == i) {
maxIndex = minIndex;
}
exchange(arr, i, minIndex);
}

if (maxIndex != -1) {
exchange(arr, maxIndex, arr.length - 1 - i);
}
}
}

private void exchange(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};
selectionSort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]

因为选择最大值和最小值同时进行,相对于上面两种算法,同时选择算法在执行次数上比前两种算法减少了50%。

在运行时间上相对于选择最小值和最大值分别减少了39.22%和62.20%。

总结

以下是对同一个长度为10000的随机乱序数组使用三种算法的情况。

[0 - 10000] 的乱序数组 取最小值 取最大值 同时取最大值最小值
100次平均执行时间(ms) 51 82 31
执行次数(次) 50004999 50004999 25005000

最后我们看一下选择排序算法的时间复杂度。

  • 最好的情况为O(n ^ 2). 即使整个数组都是有序的,选择排序也会执行完选择最大值或者最小值的过程,只是不会去进行元素交换。
  • 最坏的情况为O(n ^ 2). 同上,会执行完选择最大值或者最小值的过程,并且每次都需要进行元素交换。

其空间复杂度为O(n),上面三种算法都属于原地排序算法,除了交换元素使用了一个辅助空间之外,没有额外申请空间,同时选择排序是不稳定排序。