排序算法：选择排序算法：选择最小的放在有序的开始位置 arr[i,n) 未排序，arr[0,i) 已排序

    1. 先把最小的拿出来，放到i=0,i++
    2. 剩下的，再把最小的拿出来,放大i的位置，i++ … 每次选择还没处理的元素里最小的元素

    实现方式如下：

    1. /**
    2. * 排序算法：选择排序算法：选择最小的放在有序的开始位置 arr[i,n) 未排序，arr[0,i) 已排序
    3. * 1. 先把最小的拿出来，放到i=0,i++
    4. * 2. 剩下的，再把最小的拿出来,放大i的位置，i++
    5. * ....
    6. * 每次选择还没处理的元素里最小的元素
    7. */
    8. public class SelectSort {
    9.     private SelectSort() {
    10.     }
    12.     public static <E extends Comparable<E>> void sort(E[] arr) {
    13.         for (int i = 0; i < arr.length; i++) {
    14.             //选择arr[i,n) 中的最小值索引，其中arr[0,i)是有序的
    15.             int minIndex = i;
    16.             for (int j = i; j < arr.length; j++) {
    17.                 //compareTo 相当于arr[j]-arr[minIndex] < 0
    18.                 if (arr[j].compareTo(arr[minIndex]) < 0) {
    19.                     minIndex = j;
    20.                 }
    21.             }
    22.             //交换位置 arr[i] 和 arr[minIndex] minIndex 一定是大于i的如果 等于就没必要交换
    23.             if (minIndex > i) {
    24.                 swap(arr, i, minIndex);
    25.             }
    26.         }
    27.     }
    29.     private static <E extends Comparable<E>> void swap(E[] arr, int i, int minIndex) {
    30.         E temp = arr[i];
    31.         arr[i] = arr[minIndex];
    32.         arr[minIndex] = temp;
    33.     }
    35.     public static void main(String[] args) {
    36.         // 【6 4 2 3 1 5】 需要新开辟一个数组，占用了额外的空间。优化：可否实现原地排序？
    37.         // 索引i 和 j, j 开始查找最小值
    38.         // arr[i,n) 中最小值放到arr[i]的位置 i++
    39.         Integer[] arr = {6, 4, 3, 1, 2, 5};
    40.         sort(arr);
    41.         for (Integer integer : arr) {
    42.             System.out.println("arr = " + integer);
    43.         }
    45.         Student[] stus = {new Student("张三", 6), new Student("张三2", 1),
    46.                           new Student("张三3", 2), new Student("张三5", 3),
    47.                           new Student("张三4", 4),new Student("张三6", 5)};
    48.         sort(stus);
    49.         for (Student student : stus) {
    50.             System.out.println("stu = " + student);
    51.         }
    52.     }
    53. }