选择排序算法

选择排序（Selection sort）是一种简单直观的排序算法。

它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

简单选择排序

1. 在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。
2. 最坏情况下，即待排序记录初始状态是按第一条记录最大，之后的记录从小到大顺序排列，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2

算法复杂度：进行比较操作的时间复杂度为O(n^2)，进行移动操作的时间复杂度为O(n) 不稳定

算法思想：

1. 将数组与本数组循环比较

public class SimpleSort{
    public static void sort(Comparable[] data){
        //数组长度
        int len=data.length;
        for(int i=0; i<len; i++){
            //记录当前位置
            int position = i;
            //找出最小的数，并用position指向最小数的位置
            for(int j=i+1; j<len; j++){
                if( data[position].compareTo(data[j]) > 0 ) {
                    position=j;
                }//endif
            }//endfor
            //交换最小数data[position]和第i位数的位置
            Comparable temp=data[i];
            data[i]=data[position];
            data[position]=temp;
        }//endfor
    }//endsort
    public static void main(String[] args) {
        //在JDK1.5版本以上,基本数据类型可以自动装箱
        //int,double等基本类型的包装类已实现了Comparable接口
        Comparable[] c={4,9,23,1,45,27,5,2};
        sort(c);
        for(Comparable data:c) {
            System.out.println(data);
        }
    }
}

• ← 上一篇
• 下一篇 →