选择排序

/**
 * 选择排序
 * 工作原理
 *      是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，
 *      然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 */
public class SelectionSort {

    // 我们的算法类不允许产生任何实例
    private SelectionSort(){}

    public static void sort(int[] arr){
        int n = arr.length;
        for( int i = 0 ; i < n ; i ++ ){
            // 寻找[i, n)区间里的最小值的索引
            int minIndex = i;
            for( int j = i + 1 ; j < n ; j ++ ) {
                if( arr[j] < arr[minIndex] )
                    //用一个变量minIndex来记住最小的位置
                    minIndex = j;
                swap( arr , i , minIndex);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        int[] arr = {10,9,8,7,6,5,4,3,2,1};
        SelectionSort.sort(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }

        System.out.println();
    }
}