选择排序-笔记

算法描述

首先,选择出剩余元素中最小的。对于第一次选择,剩余元素就是所有元素。
接着,将它跟第一个元素交换位置。
然后,再从剩余元素中选择出最小的,跟第二个元素交换位置。
如此往复,直到将整个数组排序。
其名称就是来源于该算法不断从剩余的元素中选择出最小的。

算法实现

Java 实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 升序排列
public void sort(Comparable[] a) {
int n = a.length;
// 每一次外层循环确定一个索引位置的元素
for (int i = 0; i < n; i++) {
// 先假定索引为 i 的元素就是最小的
int min = i;
// 然后跟剩余元素逐个比较, 找到实际最小的
for (int j = i+1; j < n; j++) {
if (less(a[j], a[min])) {
min = j;
}
}
// 交换索引 i 和 min 位置的元素
exch(a, i, min);
}
}

算法性能评估

它有两个很鲜明的特点:

  1. 运行时间和输入的初始状态无关。为了找出最小元素而扫描一遍数组并不能为下一遍扫描提供什么信息。这种性质在某些情况下是缺点,你会发现 已经有序的数组 或者 主键全部相等的数组 和 元素随机排列的数组 所用的排序时间竟然一样长!但有些算法就更善于利用输入的初始状态。

  2. 数据移动是最少的。每次交换排定一个位置上的元素,因此总共 N 次交换(N 是数组大小)。那么交换次数和数组大小就是线性关系。其他任何排序算法都不具备这个特征,大部分的增长数量级都是线性对数或是平方级别的。

对于长度为 N 的数组,选择排序需要大约 $N^2/2$ 次比较,N 次交换。分析代码可知 0 到 N-1 的任意 i 都会进行 1 次交换和 N-1-i 次比较。因此总共有 N 次交换以及 $(N-1)+(N-2)+…+2+1 = N(N-1)/2$ ~ $N^2/2$ 次比较。

注意,~f(n) 表示所有随着 n 的增大,除以 f(n) 的结果趋近于 1 的函数。例如,g(n)~f(n) 意思就是随着 n 的增大,g(n)/f(n) 趋向于 1。

参考资源

《算法(第四版)》Robert Sedgewick 等著,第 2 章-排序

0%