排序-选择排序

浏览数：44 / 时间：2015年06月08日

基本思想：
　　每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
　　从第一层循环的起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换。

复杂度分析:
　　选择排序的交换操作介于0和(n-1)次之间。选择排序的比较操作为n(n-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。
　　比较次数O(n^2),比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

例：
public class aaaa {

　　public static void main(String[] args) {
　　　　int [] intarray = {1,23,34,22,11,444,332};
　　　　int keyvalue, index, temp;

　　　　System.out.println("排序前后的数组元素为：");
　　　　for(int a = 0; a < intarray.length; a++){
　　　　　　System.out.print(intarray[a] + " ");
　　　　}
　　　　System.out.println();

　　　　for(int i = 0 ;i < intarray.length; i++){
　　　　　　index = i ;
　　　　　　keyvalue = intarray[i];
　　　　　　for(int j = i + 1 ; j < intarray.length; j++){
　　　　　　　　if(intarray[j] < keyvalue){
　　　　　　　　　　index = j;
　　　　　　　　　　keyvalue = intarray[j];
　　　　　　　　}
　　　　　　}
　　　　　　temp = intarray[i];
　　　　　　intarray[i] = intarray[index];
　　　　　　intarray[index] = temp;
　　　　}

　　　　System.out.println("排序后的数组元素为：");
　　　　for(int b : intarray){
　　　　　　System.out.print(b + " ");
　　　　}
　　}
}