【算法】选择排序算法的讲解和代码实践

思路

选择排序，顾名思义，就是每次选出一个最小或最大的数，移动位置，直到整个数组完成排序。
有数组[26, -3, 14, -15, 0, 324, 98, 1, 22]
现对该数组进行排序，使用选择排序算法。
先来屡一下思路和步骤：

1. 选出整个数组最小的数，记录它的下标；
2. 将它和未排序的最左边数组进行交换（交换过就是排序了）；
3. 直至整个数组排序完成。

讲解

首先声明出待排序下标、最小值和最小下标。最小值我们使用Integer.MAX_VALUE，来确保数组中肯定有值能够被排序：

image.png

然后通过遍历，找到从待排序下标开始最小的数，记录它的下标：

image.png

然后把记录的下标和待排序下标的两个元素进行交换：

image.png

这就完成了第一个数字的排序，然后把待排序下标加一，继续寻找下一个最小的数，以此类推即可：

image.png

实现

    @Test
    public void sortTest() {
        int[] nums = new int[]{26, -3, 14, -15, 0, 324, 98, 1, 22};
        selectSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    private void selectSort(int[] nums) {
        if (nums.length < 2) {
            return;
        }
        // 待排序下标，从0开始
        for (int i = 0; i < nums.length; i++) {
            // 初始化最小值和最小下标
            int minVal = Integer.MAX_VALUE;
            int minIndex = -1;
            // 遍历，寻找最小值
            for (int j = i; j < nums.length; j++) {
                // 如果元素小于minVal，则赋值minVal和minIndex
                if (nums[j] < minVal) {
                    minVal = nums[j];
                    minIndex = j;
                }
            }
            // 如果最小下标不等于-1，与待排序下表交换
            if (minIndex != -1) {
                int temp = nums[i];
                nums[i] = nums[minIndex];
                nums[minIndex] = temp;
            }
        }
    }

看下运行结果：

image.png