选择排序(Selection Sort)
选择排序(Selection-sort) 是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法描述
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
算法分析
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | In-place | 不稳定 |
动图演示
代码实现
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²)
- 选择排序一般要快于冒泡，因为其交换次数少
- 但如果集合有序度高，冒泡优于选择
- 冒泡属于稳定排序算法，而选择属于不稳定排序
- 稳定排序指，按对象中不同字段进行多次排序，不会打乱同值元素的顺序
- 不稳定排序则反之
