选择排序(Selection Sort)
选择排序(Selection-sort) 是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
算法描述
- 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
- 重复第二步,直到所有元素均排序完毕。
算法分析
动图演示
代码实现
public class SelectionSort {
public static void swap(int[] array, int begin, int end){
int temp = array[begin];
array[begin] = array[end];
array[end] = temp;
}
public static void sort(int[] array) {
//存储最大值得下标
int maxIndex;
for (int end = array.length - 1; end > 0; end--) {
maxIndex = 0;
for (int begin = 1; begin <= end; begin++) {
if (array[maxIndex] <= array[begin]) {
//将当前下标赋值给 maxIndex
maxIndex = begin;
}
}
//交换最大值
swap(array,maxIndex,end);
System.out.println("第" + (array.length - end) + "次排序: " + Arrays.toString(array));
}
}
public static void main(String[] args) {
int[] array = {5, 9, 7, 4, 1, 3, 2, 8};
System.out.println("排序前: " + Arrays.toString(array));
sort(array);
}
}
执行结果:
与冒泡排序比较
- 二者平均时间复杂度都是 O(n²)
- 选择排序一般要快于冒泡,因为其交换次数少
- 但如果集合有序度高,冒泡优于选择
- 冒泡属于稳定排序算法,而选择属于不稳定排序
- 稳定排序指,按对象中不同字段进行多次排序,不会打乱同值元素的顺序
- 不稳定排序则反之