简单排序之选择排序

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

用选择排序算法对篮球队员排序

篮球队员站在一排，高低不齐，排序从球员队列的最左边开始，在记录本上记录下最左端球员的身高，并且把紫红色的毛巾放在这个队员的前面。于是开始用下一个队员的身高和记录本上记录的值相比较。如果这个队员更矮，则划掉第一个球员的身高，记录下第二个队员的身高；同时移动毛巾，把它放在这个新的最矮的队员前面，继续沿着队列走下去，每一个队员都和记录本上的最小值进行比较。当发现更矮的队员时，就更新记录本上的最小值并且移动毛巾。做完这些时期后，毛巾就会落在最矮的队员前面

然后这个最矮的队员和队列最左边的队员交换位置。现在已经对一个队员拍好了序，这期间做了N-1此比较，但是只进行了一次交换。在下一趟排序中，所做的事情一模一样，只是要完全忽略最左边队员的存在，因为他已经排序了。因此算法的第二趟排序从位置1而不是位置0开始，没进行完一次排序，就多一个队员有序，并被安排在左边，下次再找新的最小值时就可以少考虑一个队员

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

外层循环用循环变量out，从数组开头开始向高位增长。内层循环用循环变量in,从out所指位置开始，同样是向右移位，每一个in的新位置，数据项a[in]和a[min]进行比较，如果a[in]更小，则min被赋值为in的值，在内层循环的最后，min指向最小的数据项，然后交换out和min指向的数据数据项