选择排序

选择排序的本质就是筛查列表中的最小值，然后进行数据元素的交换。
选择排序也是需要将列表分为已排序和未排序两部分，我们每次对未排序的部分进行筛查找到其中的最小值然后添加的已排序部分。我们默认取列表的左边部分为已排序部分，右边部分为列表的未排序部分，已排序和未排序的关系是已排序部分增加的下标是未排序部分的起始下标（具体提现即：当从未排序部分筛查出最小值之后需要将这个元素与未排序部分的起始元素进行交换，这样随着下次进行选择操作时未排序起始位置下标的增加，筛查出来的元素就自动划分给了已排序部分）。默认情况下列表的已排序部分为0，未排序部分占据整个列表。接下来我们看一下具体的实现：

package com.lijianjian.test;

public class SelectSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] ar = { 9, 12, 3, 45, 11, 2 };
        selectSort(ar);
        for (int i = 0; i < ar.length; i++) {
            System.out.println("i value is =" + ar[i]);
        }
    }

    /**
     * 选择排序的原理是将列表分为未排序和已排序部分 每次从未排序部分中获取最小值（或者最大值）放入已排序部分中
     * 需要知道未排序的第一个下标和当前选择操作中未排序部分最小值的下标 将两个元素的值互换
     * 
     * 我们选则将列表的前面部分划为已排序部分
     */
    private static void selectSort(int[] array) {
        int minIndex = 0;// 标识未排序部分的最小值的下标 默认取未排序列表的第一个元素，后续的选择操作会覆盖掉这个值
        
        for (int i = 1; i < array.length; i++) {
            // 外层循环用来限制执行选择操作的次数，i代表第几次执行选择操作（i-1代表着未排序部分的起始下标）
            // i<array.length表示最多可以执行(array.length-1)次选择操作(当只剩下一个元素的时候是不用进行排序的)
            
            minIndex=i-1;
            for (int j = i; j < array.length; j++) {
                // 内层循环 执行选择操作 从未排序的部分中选出最小值
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }

            // 将筛选出来的最小值添加进已排序部分
            if (minIndex >= i) {
                array[minIndex] = array[minIndex] + array[i - 1];
                array[i - 1] = array[minIndex] - array[i - 1];
                array[minIndex] = array[minIndex] - array[i - 1];
            }
        }
    }
}