首页 > 代码库 > 选择排序基础(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时,需要被比较的最后一个数必然已经是最大的数了,不需要进行交换;不过只有一次比较操作,两者没什么本质区别。

 选择排序的本质即从第一位开始,遍历之后的所有剩余元素,找出其中最小的一个放到第一位;接下来再从第二位开始,找出数组中第二小的数,依次类推。

选择排序有两个重要特点:

  1. 运行时间和输入无关

即不论数组的初始状态的有序程度,选择排序的比较次数都没有变化。考虑到比较次数与元素个数的关系是N²/2,所以当一个已经比较有序的数组使用选择排序会很不划算。

      2.数据的移动操作最少

移动操作次数是一个常量,最多为N,其他的算法都不具备这个特征。

 

选择排序基础(java实现)