【排序算法】选择排序
选择排序是一种我们平时常用的排序算法,它的核心思想是:每一轮选出最小者(或者是最大者)交换到数组的一侧,这种思路最大的优势是可以大量节省元素的交换次数(比如和冒泡排序相比)。
本博客参考自:漫画:什么是选择排序
1. 选择排序的原理图
2. 选择排序的代码实现
public class SelectSort {
public static void main(String[] args) {
int[] array1 = new int[200];
for (int i = 0; i < array1.length; i++) {
array1[i] = (int) (Math.random() * 100);
}
System.out.println("生成随机数列1:" + Arrays.toString(array1));
selectSort1(array1);
System.out.println("选择排序数列1:" + Arrays.toString(array1));
}
public static void selectSort1(int[] array){
for(int i =0;i<array.length-1;i++){
int minIndex = i;
for(int j=i+1;j<array.length;j++){
if(array[j]<array[minIndex]){
minIndex = j;
}
}
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}
}
}
3. 算法复杂度
- 时间复杂度:o(n^2)
- 空间复杂度:o(1),并没有使用额外的空间进行排序