Java 选择排序思路

选择排序是一种经典的排序算法。

选择排序思想

将数组分为两个子集，前一个子集是排序的，后一个子集是未排序的。

每一轮遍历从未排序的子集中选择最小的元素放入排序子集的末端。

重复以上过程，直到整个数组有序。

经典实现

为了能更好地展示冒泡排序的主要思想，我将数据准备工作定义在 main() 方法中。

public static void main(String[] args) {
    int[] nums = {5,9,7,4,6,1,3,2,8};
    System.out.println("排序前 " + Arrays.toString(nums));
    selectionSort(nums);
    System.out.println("排序后 " + Arrays.toString(nums));
}

private static void selectionSort(int[] nums) {

}

完成选择排序的代码：

private static void selectionSort(int[] nums) {
    // i 表示每轮选择最小元素需要交换到的位置
    for (int i = 0; i < nums.length - 1; i++) {
        // 最小元素的索引需要暂存
        int min = i;
        for (int j = min + 1; j < nums.length; j++) {
            if(nums[min] > nums[j]){
                min = j;
            }
        }
        System.out.println("交换 " + nums[min] + " 与 " + nums[i] + "; ");
        swap(nums, min, i);
    }
}

private static void swap(int[] nums, int m, int n) {
    int tmp = nums[m];
    nums[m] = nums[n];
    nums[n] = tmp;
}

可以发现，其中有些交换没有必要：当两个数相等的时候，可以不需要交换：

减少交换次数

private static void selectionSort(int[] nums) {
    // i 表示每轮选择最小元素需要交换到的位置
    for (int i = 0; i < nums.length - 1; i++) {
        // 最小元素的索引需要暂存
        int min = i;
        for (int j = min + 1; j < nums.length; j++) {
            if(nums[min] > nums[j]){
                min = j;
            }
        }
        // 只有 min 与 i 不是相同元素的时候，才发生交换
        if(min != i){
            System.out.println("交换 " + nums[min] + " 与 " + nums[i] + "; ");
            swap(nums, min, i);
        }
    }
}

完整代码

public class Selection {

    public static void main(String[] args) {
        int[] nums = {5,9,7,4,6,1,3,2,8};
        System.out.println("排序前 " + Arrays.toString(nums));
        selectionSort(nums);
        System.out.println("排序后 " + Arrays.toString(nums));
    }

    private static void selectionSort(int[] nums) {
        // i 表示每轮选择最小元素需要交换到的位置
        for (int i = 0; i < nums.length - 1; i++) {
            // 最小元素的索引需要暂存
            int min = i;
            for (int j = min + 1; j < nums.length; j++) {
                if(nums[min] > nums[j]){
                    min = j;
                }
            }
            if(min != i){
                System.out.println("交换 " + nums[min] + " 与 " + nums[i] + "; ");
                swap(nums, min, i);
            }
        }
    }

    private static void swap(int[] nums, int m, int n) {
        int tmp = nums[m];
        nums[m] = nums[n];
        nums[n] = tmp;
    }
}

选择与冒泡排序

选择与冒泡排序有很多相似的地方，经常拿二者相比较。

为什么冒泡排序有时效率反而更高？

对于有序的数组，冒泡排序未发生数据交换，第一次遍历直接跳出外层循环，排序结束。

对于有序的数组，选择排序无法知道当前数据是否有序，没法提前结束循环，需要将外层循环遍历到最后。