首页 > 代码库 > 选择排序基础（java实现）
选择排序基础（java实现）
算法实现：
红宝书版本：
public class Selection{ public static void sort(Comparable[] a) { int N=a.length; for (int i=0;i<N;i++) { int min=i; for(int j=i+1;j<N;j++) if (lessa([j],a[min])) min =j; exch(a,i,min); } }}
基于int数组的实现：
public static void selectSort(int[]a){ int minIndex=0; int temp=0; if((a==null)||(a.length==0)) return; for(int i=0;i<a.length-1;i++) { minIndex=i;//无序区的最小数据数组下标 for(intj=i+1;j<a.length;j++) { //在无序区中找到最小数据并保存其数组下标 if(a[j]<a[minIndex]) { minIndex=j; } } if(minIndex!=i) { //如果不是无序区的最小值位置不是默认的第一个数据，则交换之。 temp=a[i]; a[i]=a[minIndex]; a[minIndex]=temp; } }}
注：除去前者定义的less(Comparable a, Comparable b) 和 exch(Comparable[] a,int a,int b)简化了代码之外，还有一个字面上的区别，即外层for循环中的判定条件一个是i<N、另一个是i<N-1;其实i=N-1时，需要被比较的最后一个数必然已经是最大的数了，不需要进行交换；不过只有一次比较操作，两者没什么本质区别。
选择排序的本质即从第一位开始，遍历之后的所有剩余元素，找出其中最小的一个放到第一位；接下来再从第二位开始，找出数组中第二小的数，依次类推。
选择排序有两个重要特点:
- 运行时间和输入无关
即不论数组的初始状态的有序程度，选择排序的比较次数都没有变化。考虑到比较次数与元素个数的关系是N²/2，所以当一个已经比较有序的数组使用选择排序会很不划算。
2.数据的移动操作最少
移动操作次数是一个常量，最多为N，其他的算法都不具备这个特征。
选择排序基础（java实现）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。