排序——直接选择排序（简单选择排序）
直接选择排序也称简单选择排序，是⼀种相对简单的排序算法，它的基本思想是：从⼀列数中出最⼩的，和第⼀个交换；剩下的重新出最⼩的，和这列数的第⼆个交换，......⼀直进⾏n-1次⽐较之后，该数列已经为有序数列了。
例如：已知⼀组⽆序数列：6 3 5 1 4 2 9
第⼀次：[6 3 5 1 4 2 9] 最⼩数为：1
第⼆次：1 [3 5 6 4 2 9] 最⼩数为：2
第三次：1 2 [5 6 4 3 9] 最⼩数为：3
第四次：1 2 3 [6 4 5 9] 最⼩数为：4
第五次：1 2 3 4 [6 5 9] 最⼩数为：5
第六次：1 2 3 4 5 [6 9] 最⼩数为：6
第七次：1 2 3 4 5 6 [9] 已经为有序数列了。
代码实现(Java语⾔)：
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Scanner;
public class Main{
//    public final static double pi = 3.1415927;
public static void main(String[] args) {
Scanner sin=new Scanner(System.in);
while(sin.hasNextInt()){
int len = Int();//输⼊数组的长度
int array[] = new int[100];
for(int i=0; i<len; i++){
array[i] = Int();//以此输⼊⽆序数组
}
S_sort(array, len);//直接插⼊排序
display(array, len);//显⽰排序之后的有序数列
}
}
nextint()方法public static void display(int array[],int len){
for(int i=0; i<len; i++){
System.out.print(array[i]+" ");
}
}
public static void S_sort(int array[],int len){
for(int i=0; i<len; i++){
int min = i;
for(int j=i+1; j<len; j++){
if(array[j]<array[min]){
min = j;
}
}
int temp = array[min];
array[min] = array[i];
array[i] = temp;
}
}
}
效率分析：
在直接选择排序中，共需要进⾏n-1次选择和交换，每次选择需要进⾏ n-i 次⽐较 (1<=i<=n-1),⽽每次交换最多需要3次移动，因此，总的⽐较次数C=(n*n - n)/2,
总的移动次数 3(n-1).由此可知，直接选择排序的时间复杂度为 O(n^2) ，这就意味值在n⽐较⼩的情况下，选择排序算法可以保证⼀定的速度，但当n⾜够⼤时，算法的效率会降低。所以使⽤时要注意所以当记录占⽤字节数较多时，通常⽐直接插⼊排序的执⾏速度快些。
由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是⼀种不稳定的排序⽅法。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。