直接选择排序算法”
程序员文章站
2024-01-17 21:27:52
...
选择排序的算法思想是逐个选出待排序序列中关键码第i小(大)的记录,并按照从左到右将其放入到第i个位置。这样由选取记录的排序,就得到关键码有序的排列。
下面介绍最简单的直接选择排序
一 基本思路
1 将待定的排序序列分为已排序的有序序列和尚未排序无序序列两部分。设有待排序的n个数据,则起始未排序的无需序列为n,有序序列为0。以后没进行一次排序,则有序序列加1直至到n,无序序列减1直至到0,即完成排序。
2 设置一个整形变量min用来记录每次比较过程中较小数据的位置,起始时设置min=当前无序序列的第一个位置,在以后的每次比较中都将较小的数据的位置赋给min
3 当比较到了最后一个数据时,此时min即是那个最小数据的位置,将r[i]=r[min]。完成第i次排序
4 重复第2步和第3步,直到排序完成,即需要排序的序列都变为了有序序列。
二 直接选择排序java代码实现
package ClassTest;
public class Test {
public static void main(String args[]){
int[] array = {2,4,1,7,5,8,0,9,3,6};
int[] arraytest = SelectSort(array);
System.out.println("排序后 ");
for(int i = 0; i < arraytest.length; i++){
System.out.print(arraytest[i]);
}
}
public static int[] SelectSort(int[] array){
for(int i = 0; i< array.length-1; i++){
int min = i,
temp;
for(int j = i+1; j<array.length; j++){
if(array[j] < array[min])
min = j;
}
if(i!=min){
temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
return array;
}
}
三 性能分析
1 时间性能 该排序共需排序n-1次,每次比较需n-i个。则n*(n-1)/2次,则时间复杂度为O(n2)
``` 2 空间性能 该排序空间复杂度为O(1)