排序_选择排序之简单选择排序（直接选择排序）

基本思想

数组分成有序区和无序区，初始时整个数组都是无序区，然后每次从无序区选一个最小的元素直接放到有序区的最后，重复这样的操作，直到整个数组变成有序区。

处理流程

设数组为a[0…n-1]。

1. 初始时，数组全为无序区a[0..n-1]。
2. 令i=0，从无序列a[i…n-1]中选取一个最小的元素；将其与a[i]交换。交换之后a[0...i]就形成了一个有序区
3. i++并重复第二步直到i==n-1。排序完成。

与其它排序算法比较

冒泡排序与选择排序：

• 冒泡排序的思想就是不断地在交换，通过交换完成最终的排序。
• 找到合适的关键字再做交换，并且只移动一次就完成相应关键字的排序

简单选择排序(直接选择排序)与直接插入排序对比理解：

• 简单选择排序和直接插入排序类似，都将数据分为有序区和无序区
• 不同的是直接插入排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区
• 而简单选择排序是从无序区选一个最小的元素直接放到有序区的最后。

简单选择排序(直接选择排序)与堆排序的关系：

• 堆排序是简单选择排序进行的一种改进。
• 简单选择排序每一趟排序时未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作。堆排序对于这一问题进行解决。

代码示例

public class 简单选择排序 {

    public static void main(String[] args) {
        int[] sequence = new int[]{9, 1, 5, 8, 3, 7, 4, 6, 2};//待排序的关键字序列
        System.out.println("排序前：" + Arrays.toString(sequence));
        sortFromRear2Front(sequence);
//        sortFromFront2Rear(sequence);
        System.out.println("排序后：" + Arrays.toString(sequence));
    }

    /**
     * 从后往前搜索 从小到大排序
     */
    private static void sortFromRear2Front(int[] sequence) {

        int i, j, max;
        for (i = sequence.length - 1; i > 0; i--) {
            max = i;//将当前下标定义为最大值下标
            for (j = i - 1; j >= 0; j--) {
                if (sequence[j] > sequence[max]) {//如果有大于当前最大值的关键字
                    max = j;
                }
            }
            if (i != max) {//若min不等于i，说明找到最大值，交换
                swap(sequence, max, i);
            }
        }
    }

    /**
     * 从前往后搜索 从小到大排序
     */
    private static void sortFromFront2Rear(int[] sequence) {
        //对数组a[i...n-1]无序区间，进行排序
        for (int i = 0; i < sequence.length - 1; i++) {

            int temp = 0;
            int minIndex = i;// 用来保存最小值的索引

            //得到无序区的最小元素对应的索引
            for (int j = i + 1; j < sequence.length; j++) {
                if (sequence[minIndex] > sequence[j]) {
                    minIndex = j;
                }
            }

            //无序区最小元素与无序区第1个元素交换
            temp = sequence[minIndex];
            sequence[minIndex] = sequence[i];
            sequence[i] = temp;
        }
    }

    private static void swap(int[] sequence, int formerIndex, int latterIndex) {
        int temp;
        temp = sequence[formerIndex];
        sequence[formerIndex] = sequence[latterIndex];
        sequence[latterIndex] = temp;
    }

}

简单选择排序示例图

算法分析

简单选择排序是不稳定的排序。
时间复杂度：O(n2)。