排序算法二 选择排序

1.选择排序描述：

选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。

但是过程不同，冒泡排序是通过相邻的比较和交换，而选择排序是通过对整体的选择。

其实选择排序可以看成冒泡排序的优化，选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。

2.排序流程

• 找到数组中最大（小）的那个元素；

• 将它和数组的第一个元素交换位置（如果第一个元素就是最大（小）元素那么它就和自己交换）；

• 在剩下的元素中找到最大（小）的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

3.排序流程图解

如此重复，最后形成降序后数组：

Java 选择实现

public class ChoiceSort {

    /**
     * 找后边元素的最小值 跟当前的位置交换  
     */
    public static int[] sort(int[] array) {
        if (array.length==0){
            return array;
        }

        for (int i = 0; i < array.length; i++) {
            int minIndex=i;/*最小数的下标，每个循环开始总是假设第一个数最小*/
            for (int j = i; j < array.length-1; j++) {  //在后边的元素里边找到最小值的下标
                  if (array[minIndex]>array[j+1]){
                      minIndex=j+1;    //选择最小的值 的下标
                  }
            }
            //交换i 跟 最小值   
            int temp;
            temp=array[i];
            array[i]=array[minIndex];
            array[minIndex]=temp;
        }

        return array;
    }

外层循环一次，排序好一个位置，交换元素的次数就是数组的大小，比冒泡排序交互次数大大减少。