3
排序算法之选择排序 - 白夜ovo
source link: https://www.cnblogs.com/wqstart/p/16573672.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
选择排序(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²)
- 选择排序一般要快于冒泡,因为其交换次数少
- 但如果集合有序度高,冒泡优于选择
- 冒泡属于稳定排序算法,而选择属于不稳定排序
- 稳定排序指,按对象中不同字段进行多次排序,不会打乱同值元素的顺序
- 不稳定排序则反之
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK