选择排序(Selection Sort)算法简介:
选择排序是利用逐个选择的方式进行排序,逐个选择出数组中的最小(或最大)的元素,顺序放在已排好序的序列后面,直到全部记录排序完毕。
选择排序(Selection Sort)算法原理:
例如我们有一个数组,我们需要把较小的元素排在前面,把较大的元素排在后面,那么需要选择出最小元素并将其排在序列最前:
- 从待排序列中选出最小(或最大)的一个元素,记录其下标的位置;
- 将记录的下标值与待排序列的第一个元素进行交换;
- 以此类推,直到全部待排序列的元素排完。
举例说明:
现在需要对数组序列 6 1 7 8 9 3 5 4 2 运用选择排序算法从小到大排序。
第一轮:最小元素为1,把1放在首位,也就是1和6互换位置:1 6 7 8 9 3 5 4 2
第二轮:将排序好的元素以外的序列6 7 8 9 3 5 4 2进行比较,最小元素为2,将2与第二位的6互换位置:1 2 7 8 9 3 5 4 6
第三轮:将排序好的元素以外的序列7 8 9 3 5 4 6 进行比较,最小元素为3,将3与第三位的7互换位置:1 2 3 8 9 7 5 4 6
.................
第n轮:重复同样的操作直到所有数字都归位为止,排序完成。
选择排序(Selection Sort)代码实现:
public class Demo {
public static void main(String[] args) {
int[] array= {6,1,7,8,9,3,5,4,2};
int[] newarray=selectionSort(array);
for(int arr:newarray) {
System.out.print(arr+" ");
}
}
public static int[] selectionSort(int[] array){
//外层循环,控制选择的次数
for(int i=0;i<array.length-1;i++) {
int min_index=i;
//内存循环
for(int j=i+1;j<array.length;j++) {
if(array[j]<array[min_index]) {
min_index=j;
}
}
if(min_index!=i) {
int temp=array[i];
array[i]=array[min_index];
array[min_index]=temp;
}
}
return array;
}
}
选择排序(Selection Sort)的时间复杂度:
选择排序使用了线性查找来寻找最小值,因此在第1轮中需要比较n-1个数字,第2轮需要比较n-2个数.....到第n-1轮的时候就只需比较1个数字了。因此,总的比较次数与冒泡排序的相同,都是(n-1)+(n-2) +...+1≈n²/2次。每轮中交换数字的次数最多为1次。如果输入数据就是按从小到大的顺序排列的,便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样,都为O(n²)。