排序算法之选择排序-java版
1. 选择排序
1.1 选择排序的基本介绍
选择排序类似于冒泡排序，均属于内排，也可以看做是对冒泡排序的优化。因为冒泡排序是比较相邻的两个值，然后直接交换。而选择排序是找到一个最大值或者最小值之后，再进行交换。
1.2 选择排序思想
第一次从 arr[0] ~ arr[n-1]中选择一个最大值或者最小值，与 arr[0] 交换；第二次从 arr[1] ~ arr[n-1]中选择一个最大值或者最小值，与 arr[1] 交换； 第二次从 arr[2] ~ arr[n-1]中选择一个最大值或者最小值，与 arr[2] 交换； 依次类推。
1.3 选择排序的时间复杂度和空间复杂度等
算法名称 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
选择排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
2. 代码演示
/**
* @author shengjk1
* @date 2020/3/30
*/
public class SelectSort {
public static void main(String[] args) {
int[] arr = {1, 10, 2, 30, -1};
selectSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[i] < arr[j] ? i : j;
}
if (minIndex != i) {
int tem = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tem;
}
}
}
}举报
腾讯云开发者
