基本思想
这是思路最简单的排序算法。
- 找到数组中最小的那个元素；
- 将它和数组的第一个元素交换位置（如果第一个元素就是最小元素，那么它就和自己交换）；
- 在剩下的元素中找出最小的元素，将它与剩余元素中的第一个元素交换（即数组第二个元素）；
- 重复执行 3 ，直到将整个数组排序。
运行轨迹
选择排序运行轨迹
选择排序.gif
代码实现
根据排序算法类的模板实现选择排序（提醒：点蓝字查看详情）
/**
* 选择排序
*
* @author TinyDolphin
* 2017/11/1 14:20.
*/
public class Selection {
/**
* 排序实现
* @param arr 待排序数组
*/
public static void sort(Comparable[] arr) {
int length = arr.length;//数组长度
for (int indexI = 0; indexI < length; indexI++) {
// 将arr[indexI]和arr[indexI+1...length]中最小的元素交换
int min = indexI; // 最小元素的索引
for (int indexJ = indexI + 1; indexJ < length; indexJ++) {
if (less(arr[indexJ], arr[min])) {
min = indexJ;
}
}
exch(arr, indexI, min);
}
}
/**
* 比较两个元素的大小
* @param comparableA 待比较元素A
* @param comparableB 待比较元素B
* @return 若 A < B,返回 true,否则返回 false
*/
private static boolean less(Comparable comparableA, Comparable comparableB) {
return comparableA.compareTo(comparableB) < 0;
}
/**
* 将两个元素交换位置
* @param arr 待交换元素所在的数组
* @param indexI 第一个元素索引
* @param indexJ 第二个元素索引
*/
private static void exch(Comparable[] arr, int indexI, int indexJ) {
Comparable temp = arr[indexI];
arr[indexI] = arr[indexJ];
arr[indexJ] = temp;
}
/**
* 打印数组的内容
* @param arr 待打印的数组
*/
private static void show(Comparable[] arr) {
for (int index = 0; index < arr.length; index++) {
System.out.print(arr[index] + " ");
}
System.out.println();
}
/**
* 判断数组是否有序
* @param arr 待判断数组
* @return 若数组有序，返回 true，否则返回 false
*/
public static boolean isSort(Comparable[] arr) {
for (int index = 1; index < arr.length; index++) {
if (less(arr[index], arr[index - 1])) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Integer[] arr = new Integer[]{14, 23, 21, 17, 20, 49, 24, 77, 54, 47, 31};
sort(arr);
assert isSort(arr);
show(arr); //14 17 20 21 23 24 31 47 49 54 77
}
}
性能分析
交换元素的代码写在内循环之外，每次交换都能排定一个元素，因此交换的总次数是 N。所以算法的时间效率取决于比较的次数。
查看代码可以精准得到，0 到 N-1 的任意 indexI 都会进行一次交换和 N-1-indexI 次比较，所以对于长度为 N 的数组，选择排序需要大约 N²/2 次比较和 N 次交换。
选择排序的特点
①、运行时间和输入无关。为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息；
②、数据移动是最小的。每次交换都会改变两个数组元素的值，因此选择排序用了 N 次交换——交换次数和数组的大小是线性关系。（其他大部分排序算法的增长数量级都是线性对数或是平方级别的）
优化方案
试想，上述方案中的主要思路是，每次遍历剩余元素，找出其中最小值，只排定最小值。（原有方案）
我们这样，每次遍历剩余元素的时候，找出其中最小值和最大值，并排定最小值和最大值。（优化方案）
这样遍历的次数会减少一半。时间复杂度是O（N/2 * N /2），还是平方级别的。但是运行时间有了相应的减少。
优化方案之后的运行轨迹
优化方案的运行轨迹
优化代码
public static void sortPlus(Comparable[] arr) {
for (int left = 0, right = arr.length - 1; left < right; left++, right--) {
int min = left; // 记录最小值
int max = right; // 记录最大值
for (int index = left; index <= right; index++) {
if (less(arr[index], arr[min])) {
min = index;
}
if (less(arr[max], arr[index])) {
max = index;
}
}
// 将最小值交换到 left 的位置
exch(arr, left, min);
//此处是先排最小值的位置，所以得考虑最大值（arr[max]）在最小位置（left）的情况。
if (left == max) {
max = min;
}
exch(arr, right, max);
}
}
测试代码
public static void main(String[] args) {
int length = 10000; // 上万级别
Integer[] arr = new Integer[length];
for (int index = 0; index < length; index++) {
arr[index] = new Random().nextInt(length) + 1;
}
Integer[] arr2 = new Integer[length];
System.arraycopy(arr, 0, arr2, 0, length); // 数组复制的最优选择
long start = System.currentTimeMillis();
sort(arr);
long end = System.currentTimeMillis();
System.out.println("sort()耗费时间：" + (end - start) + "ms");
assert isSort(arr);
start = System.currentTimeMillis();
sortPlus(arr2);
end = System.currentTimeMillis();
System.out.println("sortPlus()耗费时间：" + (end - start) + "ms");
assert isSort(arr);
}
测试结果
其中数组复制的最优方法来自：Java中数组复制的四种方法
注意：编译器默认不适用 assert 检测（但是junit测试中适用），所以要使用时要添加参数虚拟机启动参数 -ea 具体添加过程，请参照eclipse 和 IDEA 设置虚拟机启动参数
结论
虽然选择排序算法简单，但是其优化方案是非常好的一个优化思路，也可以考虑使用在别的算法上，不要仅仅局限于此。
网友评论