入门算法：选择排序

上手难度：★

算法复杂度：O(n^2)

selectionSort.gif

这个排序的主要思想就是通过两层循环

第一层循环从0到length - 1，前闭后开，设置索引 minIndex = i，对应图就是红色块标记，这里的i就是我们第一层循环中选择要排序的位置

第二层循环从i+1到length，前闭后开，遍历 minIndex 后面的元素，也就是绿色块标记在移动，如果发现比minIndex还要小的，就用minIndex记住这个位置，当第二层循环结束后，就交换i和minIndex的值

如此实现从小到大的排序

public class SelectSort {

    //选择排序算法实现
    public static void selectSort(int[] arr){
        for(int i = 0; i < arr.length - 1; i++){//之所以循环到arr.length-1，是因为下一层循环肯定能取到arr[length-1]这个值
            int minIndex = i;
            for(int j = i + 1; j < arr.length; j++){//从i的下一个元素开始与i进行比较
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }

            if(i != minIndex){
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {

        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        selectSort(arr);

        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }
}

运行结果

选择排序

优点：思想简单
缺点：对于任何一个数组，选择排序两层循环，每一层循环都必须完全的执行
因此，选择循环的效率在任何情况下都是非常慢的