首页 > 代码库 > 排序——直接选择排序(简单选择排序)

排序——直接选择排序(简单选择排序)

直接选择排序也称简单选择排序,是一种相对简单的排序算法,它的基本思想是:从一列数中找出最小的,和第一个交换;剩下的重新找出最小的,和这列数的第二个交换,......一直进行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 = sin.nextInt();//输入数组的长度
            int array[] = new int[100];
            for(int i=0; i<len; i++){
                array[i] = sin.nextInt();//以此输入无序数组
            }
            S_sort(array, len);//直接插入排序
            display(array, len);//显示排序之后的有序数列
        }
    }
    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足够大时,算法的效率会降低。所以使用时要注意所以当记录占用字节数较多时,通常比直接插入排序的执行速度快些。
由于在直接选择排序中存在着不相邻元素之间的互换,因此,直接选择排序是一种不稳定的排序方法。

 

排序——直接选择排序(简单选择排序)