选择排序

选择排序改进了 。将必要的交换次数从O（n的平方）减少到了O（n）.不幸的是，比较次数仍然保持着O（n的平方）。然而，选择排序仍然为大记录量的排序提出了一个非常重要的改进，因为这些大量的记录需要在内存中移动，这就使交换的时间和比较的时间相比起来，交换的时间更为重要。（一般来说，在JAVA语言中不是这种情况，JAVA中只是改变了引用位置，而实际对象的位置并没有发生改变。）

用选择排序算法来对棒球队员进行排序

让我们再来考虑棒球队排序的问题。在选择排序中，不再只比较两个相邻的球员。因此，需要记录下某一个指定队员的高度：可以使用记事本写下指定队员的身高，同时还需要准备好一条紫红色的毛巾。

简述

进行选择排序就是把所有的队员扫描一趟，从中挑出（或者说选择，这正是这个排序名字的由来）最矮的一个队员。最矮的这个队员和站在队列最左端的队员交换位置，即站在0号文职。现在最左端的队员是有序的了，不需要再交换位置了。注意，在这个算法中有序的队员都排列在队列的左边（较小的下标点），而在冒泡排序中则是排列在队列右边的。

再次扫描球队队列时，就从1号位置开始，还是寻找最矮的，然后和1号位置的队员交换。这个过程一直持续到所有的队员都排定。

代码

 

/**
 * Created by Bruce on 2020/8/12
 * 选择排序
 **/public class SelectSort_07 {

    private long[] a;
    private int nElems;

    public SelectSort_07(int maxSize) {
        this.a = new long[maxSize];
        this.nElems = 0;
    }

    public void insert(long insertValue){
        if(nElems == a.length){
            return;
        }
        a[nElems] = insertValue;
        nElems++;
    }

    public void display(){
        for(int i = 0 ; i < nElems; i++){
            System.out.print(a[i] + " ");
        }
        System.out.println(" ");
    }

    public void selectSort(){
        for(int out = 0 ; out < nElems - 1; out++){
            int minIndex = out;
            for(int in = out + 1; in < nElems; in++){
                if(a[in] < a[minIndex]){
                    minIndex = in;
                }
            }
            if(minIndex != out){
                swap(out,minIndex);
            }
        }
    }

    private void swap(int one, int two){
        long temp = a[one];
        a[one] = a[two];
        a[two] = temp;
    }

    public static void main(String[] args) {
        SelectSort_07 arr = new SelectSort_07(100);
        arr.insert(77);
        arr.insert(99);
        arr.insert(44);
        arr.insert(55);
        arr.insert(22);
        arr.insert(88);
        arr.insert(11);
        arr.insert(00);
        arr.insert(66);
        arr.insert(33);

        arr.display();

        arr.selectSort();
        arr.display();
    }

}
  

执行结果：

77 99 44 55 22 88 11 0 66 33

0 11 22 33 44 55 66 77 88 99

释义

不变性

在SelectSort_07.java程序中，下标小于或等于out的位置的数据总是有序的。

选择排序的效率

选择排序和冒泡排序执行了相同次数的比较：N*(N-1)/2.对于10个数据项，需要45次比较。然后，10个数据项只需要少于10次的交换。对于100个数据项，需要4950次比较，但是只进行了不到100次的交换。N值很大时，比较的次数是主要的，所以结论是选择排序和冒泡排序一样运行了O（n的平方）的时间复杂度。但是，选择排序无疑更快，因为它进行的交换少的多。当N较小时，特别是如果交换的时间级别比较的的时间级别大的多时，选择排序实际上是相当快的。

本文摘要自《Java数据结构和算法（第二版）》