选择排序
算法描述
选择排序算法的运作如下：
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 以此类推，直到所有元素均排序完毕。
整数数组实现
int[] a = ...
for (int i = 0; i < a.length - 1; i++) {
for (int j = i + 1; j < a.length; j++) {
if (a[i] > a[j]) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
泛化实现
@FunctionalInterface
public interface Sort {
public abstract <T> void sort(T[] a, Comparator<? super T> comparator);
}
public class SelectSort implements Sort {
@Override
public <T> void sort(T[] a, Comparator<? super T> comparator) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = i + 1; j < a.length; j++) {
if (comparator.compare(a[i], a[j]) > 0) {
T t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
}
}
评价
- 选择排序时间复杂度为O(n2)
- 选择排序交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快