选择排序

选择排序改进了冒泡排序，将必要的交换次数从O(N*N)减少到O(N)。不过比较次数还是O(N*N)。然而，选择排序仍然为大记录量的排序提出了一个非常重要的改进，因为这些大量的记录需要在内存中移动，这就使得交换时间比起比较时间来更为重要。

其过程如下：
将数组中所有的数据项扫描一趟，从中选出最小的一个。最小的和数组的0号元素交换位置。现在最左端的数据项就是有序的了。再次扫描数组，从1号位置开始，还是找最小的，然后和1号位置的元素交换。这个过程持续到所有数据项排定。

java代码如下：

publicvoidselectionSort()...{
intout,in,min;
for(out=0;out<a.length-1;out++)...{
min=out;
for(in=out+1;in<a.length;in++)...{
if(a[in]<a[min])
min=in;
}
swap(out,min);
}
}

privatevoidswap(intin,inti)...{
longtemp=a[in];
a[in]=a[i];
a[i]=temp;
}