选择算法
public static void selection(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
// i 代表每轮选择最小元素要交换到的目标索引
int s = i; // s 代表最小元素的索引
for (int j = s + 1; j < a.length; j++) {
if (a展开 > a[j]) {
s = j;
}
}
if (s != i) {
swap(a, s, i);
}
}
}
实现思路
- 1,将数组分为两个子集,排序的和未排序的,每一轮从未排序的子集中选出最小的元素,放入排序子集。
- 2,重复以上步骤,直到整个数组有序。
优化思路
- 为了减少交换次数,每一轮可以先找最小的索引,在每轮最后才交换元素。
与冒泡排序算法比较
- 1,二者平均时间复杂度都是O(n^2)。
- 2,选择排序一般要快于冒泡,因为其交换次数少。
- 3,如果集合有序度高,则冒泡优于选择。
- 4,冒泡属于稳定排序算法,而选择属于不稳定排序算法。(ps:不稳定算法指多次排序会打乱相同元素原本的顺序)