简单排序：选择排序

小半 • 2023年2月3日上午10:56 • 技术随笔 • 阅读 95

一.原理
1.每一次遍历的过程中，都假定第一个索引处的元素是最小值min，并和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索他引处的值，则假定其某个索引出的值为最小值min，最后可以找到最小值所在的索引

2.最后交换第一个索引处和最小值所在的索引处的值

总结
寻找最小
假定第一个数的索引为min
从前往后两两比较
谁小谁的索引就是min
最后将min和每轮最前面交换
比较个数越来越少）

由于原理较简单，直接上代码。

二.java代码实现

public class selection {
    public static void sort(int[] a){
    	int min=i; //初始化min指针为i
        for (int i=0;i<a.length-1;i++){  //i是假定最小值的索引（不包括最后一个数）； min是最小数的指针
            for(int j=i+1;j<a.length;j++){ //j最大是n-1
                if(a[min]>a[j]){  //比较假定最小数和后面一位
                    min=j;
                }
            }
            exchange(a,i,min);  
                    }}

private static void exchange(int[]a,int i,int min){ 
        int t=a[i];
        a[i]=a[min];
        a[min]=t;}
    public static void main(String[] args) {
        int[] a={4,6,8,7,9,2,10,1};
        selection.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

运行结果：[1, 2, 4, 6, 7, 8, 9, 10]

注意：

外层循环 i 视为每一轮假定最小值。不能取到最后一个，所以i < a.length-1
需要初始化一个min作为最小数的指针，初始化为i
j最大为n-1，所以j<a.length

复杂度分析：
数据比较次数： (N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;
数据交换次数： N-1 （最坏情况时，外层循环一次则交换一次） // 比冒泡排序少！
时间复杂度：N^2 /2-N/2+（N-1）=N^2/2+N/2-1;
根据大O推导法则，保留最高阶项，去除常数因子，时间复杂度为O(N^2);

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89396.html

简单排序：选择排序

相关推荐