选择排序算法

本文介绍: 选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序的基本思想是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的时间复杂度为O(n^2)，其中n为待排序元素的个数。

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

选择排序的基本思想是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的时间复杂度为O(n^2)，其中n为待排序元素的个数。虽然时间复杂度较高，但选择排序是稳定的排序算法，且具有较好的性能表现。

实现思想：

首先，定义一个最小值min，将min赋值循环后的第一个未排序的值，将该值与后续的值进行比较，如果发现有比min还有小的值，将两个元素进行交换。如果没有发现比该元素还要小的值，说明该值不需要改动，当前位置就是其排序后的位置。依次循环，比较 (元素-1) 次即可完成排序。

推敲代码中：

public class Sortselect {
    public static void main(String[] args) {
        int[] arrays = {12, 5, 8, 9, 4, 2};
        System.out.println("排序前：" + Arrays.toString(arrays));
        int min = arrays[0];
        for (int j = 0; j < arrays.length; j++) {
            if (min > arrays[j]) {
                //交换元素，将最小值移到相应的位置
                min = arrays[j];
                arrays[j] = arrays[0];
                arrays[0] = min;
            }
        }
        System.out.println("第一轮：" + Arrays.toString(arrays));

        min = arrays[1];
        for (int j = 1; j < arrays.length; j++) {
            if (min > arrays[j]) {
                //交换元素，将最小值移到相应的位置
                min = arrays[j];
                arrays[j] = arrays[1];
                arrays[1] = min;
            }
        }
        System.out.println("第二轮：" + Arrays.toString(arrays));

        min = arrays[2];
        for (int j = 2; j < arrays.length; j++) {
            if (min > arrays[j]) {
                //交换元素，将最小值移到相应的位置
                min = arrays[j];
                arrays[j] = arrays[2];
                arrays[2] = min;
            }
        }
        System.out.println("第三轮：" + Arrays.toString(arrays));

        min = arrays[3];
        for (int j = 3; j < arrays.length; j++) {
            if(min > arrays[j]){
                min = arrays[j];
                arrays[j] = arrays[3];
                arrays[3] = min;
            }
        }
        System.out.println("第四轮：" + Arrays.toString(arrays));

        min = arrays[4];
        for (int j = 4; j < arrays.length; j++) {
            if(min > arrays[j]){
                min = arrays[j];
                arrays[j] = arrays[4];
                arrays[4] = min;
            }
        }
        System.out.println("第五轮：" + Arrays.toString(arrays));

        min = arrays[5];
        for (int j = 5; j < arrays.length; j++) {
            if(min > arrays[j]){
                min = arrays[j];
                arrays[j] = arrays[5];
                arrays[5] = min;
            }
        }
        System.out.println("第五轮：" + Arrays.toString(arrays));
    }
}

找到规律后，实现简化：

public class SelectSort {
    public static void main(String[] args) {
        int[] arrays = {12, 5, 8, 9, 4, 2};
        System.out.println("排序前：" + Arrays.toString(arrays));
        int min = arrays[0];
        for (int i = 0; i < arrays.length - 1; i++) {
            min = arrays[i];
            for (int j = i; j < arrays.length; j++) {
                if (min > arrays[j]) {
                    //交换元素，将最小值移到相应的位置
                    min = arrays[j];
                    arrays[j] = arrays[i];
                    arrays[i] = min;
                }
            }
            System.out.println("排序中：" + Arrays.toString(arrays)); //为了看清交换顺序
        }
        System.out.println("排序后：" + Arrays.toString(arrays));
    }
}

使用下标控制进行交换（实现）：

public class SelectSort2 {
    public static void main(String[] args) {
        //选择排序的时间复杂度是O(n^2)
        int[] arrays = {12, 5, 8, 9, 4, 2};
        System.out.println("排序前：" + Arrays.toString(arrays));
        for (int i = 0; i < arrays.length - 1; i++) {
            int minIndex = i;
            int min = arrays[i];
            for (int j = i + 1; j < arrays.length; j++) {
                if (min > arrays[j]) { //说明假定的最小值不是最小的那一个
                    min = arrays[j]; //重置min
                    minIndex = j; //重置minIndex
                }
            }

            //将最小值，放在array[i],即交换
            if (minIndex != i) {
                arrays[minIndex] = arrays[i];
                arrays[i] = min;
            }
            System.out.println("第" + (i + 1) + "轮:" + Arrays.toString(arrays));
        }
        System.out.println("排序前：" + Arrays.toString(arrays));
    }
}