选择排序 #

1. 选择排序算法思想 #

选择排序（Selection Sort）基本思想：

对n个元素，进行n-1趟排序，第 i (i = 1, 2, …) 趟排序时从数组下标为 i - 1 的元素M开始遍历，直至数组最后一个元素，将其中值最小的元素与元素M进行交换。

简单来说，「选择排序法」关键在于每次遍历都选出一个最大/最小值，最终使整个数组有序。

2. 选择排序算法步骤 #

1. 第1趟排序，从数组中下标为0的元素开始，依次向后遍历整个数组；

   1. 假定一个变量min，表示第1趟排序中，最小值的下标，初始值设置为0；

   2. 依次向后遍历，同时比较每一个元素与arr[min]的大小，如果某个元素值比arr[min]小，则将该元素的下标赋值给min。

   3. 遍历结束后，将数组中下标为0和下标为min的元素交换位置；

2. 第2趟排序，从数组中下标为1的元素开始，依次向后遍历整个数组；

   1. 假定一个变量min，表示第2趟排序中，最小值的下标，初始值设置为1；
   2. 依次向后遍历，同时比较每一个元素与arr[min]的大小，如果某个元素值比arr[min]小，则将该元素的下标赋值给min。
   3. 遍历结束后，将数组中下标为1和下标为min的元素交换位置；

3. 依次类推，将上述过程进行n-1次，结束。

3. 选择排序动画演示 #

4. 选择排序代码实现 #

public static void selectSort(int[] arr){
    if(null==arr || arr.length==0){
        return;
    }
    for(int i=0;i<arr.length-1;i++){
        int min = i;
        for(int j=i+1;j<arr.length;j++){
            if(arr[min] > arr[j]){
                //记录本趟排序最小值的下标
                min = j;
            }
        }
        //交换
        if(i != min){
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;   
        }
    }
}