一.原理
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
