选择排序

　　排序，通常会把待排序的数据组织成数组结构，比如{15，8，10，2，5}。选择排序呢？就是用选择的方式进行排序。如果按照从小到大进行排序，那就是先从整个数组中，选出最小的一个数，然后放在第一个位置，那么第一个位置的数据，就算排好了。在剩下的数据中，再选出一个最小的数，然后放到数组的第二个位置，那第二个位置也算排好了，依次类推。选择排序，就是选择出一个最小的数，然后放到它应该在的位置。怎么放置呢？交换。找到最小的数，记录它的位置，然后和它该在的位置处的元素进行交换。要找到最小的数，那就循环遍历数组。以{15，8，10，2，5}为例，先循环遍历数组，从整个数组找到最小的数，那就是2，位置是3，它需要放到数组0的位置，那就和15进行交换。

 　　数组0位置处的元素，排好序了，就不用管了，再在剩下的元素{8，10，15，5}中，找到最小的数，还是遍历数组，最小的数是5，位置4，那它该在的位置是1，那就和数组1位置处的元素交换。

 　　数组0和数组1位置处的元素都排好序了，还剩下{10，15，8}，还是找出最小的一个元素，最小的数是8，位置4，它应该放到第2个位置，那就和数组3位置处的元素交换

 　　剩下{15，10}，最小的数是10，位置4，它应该放到第3个位置，那就和数组3位置处的元素交换，

 　　还剩下最后一个数15，它本身就不用排序了，只要前面的数都排好序，最后一下数，也就排好序了，排序完成。

 　　5个数，经历了4次循环，每一次循环都是为了从剩下的数中找到最小的数，然后进行交换，将它放到合适的位置。第一次循环，合适的位置是0，找出最小数的范围是[0,4]。第二次循环，合适的位置是1，找出最小数的范围是[1,4]。第三次循环，合适的位置是2，找出最小数的范围是[2,4]。 第四次循环，合适的位置是3，找出最小数的范围是[3,4]。 第五次循环，合适的位置是4，找出最小数的范围是[4,4]。[4,4]就是它本身，所以不用第五次循环。如果把待排序的数据组织成数组结构，合适的位置就是数组中的元素的索引，每一次循环，索引加1，又是合适的位置。每一次循环中，要找出最小数，又是一个循环，先假设合适的位置就是最小值，然后再从合适的位置+1处开始循环，直到数组中最后一个元素，如果有有数比最小值还小，就找到最小数的位置，把它记录下来，循环结束后进行交换。

public class SortArray {
    public static void selectionSort(int[] a) {
        // N-1 轮比较
        for (int i = 0; i < a.length -1; i++) {
            int minIndex = i;

            // 找到的最小值元素的下标
            for (int j = i + 1; j < a.length; j++) {
                if(a[j] < a[minIndex]) {
                    minIndex = j;
                }
            }

            // 进行交换
            int temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
}

　　Java 中有泛型，

public class SortArray {
    public static  <T extends Comparable<? super T>> void selectionSort(T[] a) {
        // N-1 轮比较
        for (int i = 0; i < a.length -1; i++) {
            int minIndex = i;

            // 找到的最小值元素的下标
            for (int j = i + 1; j < a.length; j++) {
                if(a[j].compareTo(a[minIndex]) < 0) {
                    minIndex = j;
                }
            }

            // 进行交换
            T temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        Integer[] a = {9, 6, 2, 4, 8};
        selectionSort(a);
        System.out.println(Arrays.toString(a));
    }
}

 　　选择排序还可以用递归实现，第一次排序的时候，整个数组选一个最小值并和数组的第一个位置交换，第二次排序的时候，数组剩下的部分选一个最小值，并和该部分数组的第一个位置进行交换，最终数组只剩下一个元素，排序完毕。排序的时候，总是在一部分数组中进行，在部分数组中的操作都是一样的，找到最小的元素并交换。如果我们定义的方法接受数组作为第一个参数，要排序的数组部分起始位置为作为第二个参数，终止位置作为第三个参数，每次调用方法的时候，起始位置加1，就相当于原数组前面的部分已经排好了，待排序的部分减少，起始位置每加1，待排序的部分就越少，直到起始位置等于终止位置，那待排序的部分就剩下一个元素，排序完毕。方法的内部，就是从数组的起始位置开始，寻找最小值，并和起始位置进行交换

public class SortArray {
    
    public static void selectionSort(int[] a){
        sort(a, 0, a.length -1);
    }

    private static void sort(int[] a, int start, int end){

        if (start < end) {
            int minIndex = start;
            int minValue = a[start];

            for (int i = start + 1; i <= end; i++) {
                if(a[i] < minValue){
                    minIndex = i;
                    minValue = a[i];
                }
            }
            a[minIndex] = a[start];
            a[start] = minValue;

            sort(a, start + 1, end);
        }
    }
}

　　当用递归算法操作数组的时候，通常将数组时进行分段，切割，算法也通常会接受三个参数，数组， start, end, start和end 用于描述部分数组，数组[start] 和数组[end]。