1. 将数组分为两个子集,排序的和未排序的,每一轮从未排序的子集中选出最小的元素,放入排序子
集
2. 重复以上步骤,直到整个数组有序
更形象的描述请参考:
selection_sort.html
算法实现
优化点:为减少交换次数,每一轮可以先找最小的索引,在每轮最后再交换元素
与冒泡排序比较
1. 二者平均时间复杂度都是 $O(n^2)$
2. 选择排序一般要快于冒泡,因为其交换次数少
3. 但如果集合有序度高,冒泡优于选择
4. 冒泡属于稳定排序算法,而选择属于不稳定排序
稳定排序指,按对象中不同字段进行多次排序,不会打乱同值元素的顺序
不稳定排序则反之
稳定排序与不稳定排序
都是先按照花色排序(♠♥♣♦),再按照数字排序(AKQJ...)
public static void selection(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
// i 代表每轮选择最小元素要交换到的目标索引
int s = i; // 代表最小元素的索引
for (int j = s + 1; j < a.length; j++) {
if (a[s] > a[j]) { // j 元素比 s 元素还要小, 更新 s
s = j;
}
}
if (s != i) {
swap(a, s, i);
}
System.out.println(Arrays.toString(a));
}
}
System.out.println("=================不稳定================");
Card[] cards = getStaticCards();
System.out.println(Arrays.toString(cards));
selection(cards, Comparator.comparingInt((Card a) -> a.sharpOrder).reversed());
System.out.println(Arrays.toString(cards));
selection(cards, Comparator.comparingInt((Card a) -> a.numberOrder).reversed());
System.out.println(Arrays.toString(cards));
System.out.println("=================稳定=================");
cards = getStaticCards();
System.out.println(Arrays.toString(cards));
bubble(cards, Comparator.comparingInt((Card a) -> a.sharpOrder).reversed());
System.out.println(Arrays.toString(cards));
bubble(cards, Comparator.comparingInt((Card a) -> a.numberOrder).reversed());
System.out.println(Arrays.toString(cards));