数据结构与算法——排序算法之选择排序

• 一：选择排序原理：
  将要排序的数据元素选出最小（大），将他和数据元素的首位交换位置。再次从剩下的数据元素中 找到最小（大）的元素，然后与数据元素的第二位子交换。。。直到将整个数据元素排序。
  总之他在不断选择剩余元素的最小值，然后放在恰当的位置。

• 二：选择排序的特点：
  1.运行时间和输入无关。

  为了找出最小的元素，遍历整个数组并不能为下一次遍历提供信息。这样的缺点是：一个有序的数组与一个随机数组所用的排序时间相同。

  2.数据移动最少。

  每次交换都会改变两个元素的值，因此数组多大，就几次数据移动。

• 三：代码描述（java实现）：

public static void sort(int[] a){
    int N=a.length;
    for(int i=0;i<N;i++){
        int min=i;
        for(int j=i+1;j<N;j++){
            if(a[j]<a[min]){  
                min=j;
            }
        }
        int temp=a[i];
        a[i]=a[min];
        a[min]=temp;
    }
}

内循环为找到当前序列的最小元素。然后最小元素与相应的位置的元素交换位置。每次交换能确定一个元素的位置，所以总交换次数为N.所以算法的时间效率取决于比较次数N*（N-1）/2