小白算法_(2)

前言

笔者属于算法小白一枚，本系列文章属于算法的学习笔记，也希望能给算法小小白起到些许的指引作用。如果有算法大佬不小心点了进来，只能说一声抱歉打扰了。

正文

题目

请实现一个选择排序，升序排列。

原理

在未排序队列中找到最小元素，放在排序队列的头部。
再从剩余未排序元素中继续寻找最小元素，然后放到已排序队列的尾部。
重复第二步，直到所有元素均排序完毕。

实现

选择排序需要两层循环才能实现，个人建议先梳理清楚一层循环做了什么事情，得到了什么结果，最后再加上一层循环嵌套，思路会更清晰一些。

假设待排序的数组：[6, 4, 2, 1, 8, 3, 7, 9, 5]

我们在一层循环里面想要将最小的元素放在排序队列的头部，结合算法原理，不难写出以下代码：

public static void main(String[] args) {
    int[] array = {6, 4, 2, 1, 8, 3, 7, 9, 5};
    // 假设最小的元素索引是0
    int minIndex = 0;
    for (int j = 1; j < array.length; j++) {
        // 找到了更小的元素，更新索引
        if (array[j] < array[minIndex]) {
            minIndex = j;
        }
    }
    // 将最小的元素放置在索引0
    if (minIndex != 0) {
        int tmp = array[minIndex];
        array[minIndex] = array[0];
        array[0] = tmp;
    }
    System.out.println(Arrays.toString(array));
}

得到数组：[1, 4, 2, 6, 8, 3, 7, 9, 5]

分析：

经过一层循环，我们选择出了最小的元素，并且将它放在了队列头部。
接下来我们需要找到第二小的元素，将它放在队列的第二个位置。
此时队列头部位置已经放置了最小元素，我们从第二个位置开始选择。

继续写代码：

public static void main(String[] args) {
    int[] array = {6, 4, 2, 1, 8, 3, 7, 9, 5};
    // 假设最小的元素索引是0
    int minIndex = 0;
    for (int j = 1; j < array.length; j++) {
        // 找到了更小的元素，更新索引
        if (array[j] < array[minIndex]) {
            minIndex = j;
        }
    }
    // 将最小的元素放置在索引0
    if (minIndex != 0) {
        int tmp = array[minIndex];
        array[minIndex] = array[0];
        array[0] = tmp;
    }
    // 假设最小的元素索引是1
    minIndex = 1;
    for (int j = 2; j < array.length; j++) {
        // 找到了更小的元素，更新索引
        if (array[j] < array[minIndex]) {
            minIndex = j;
        }
    }
    // 将最小的元素放置在索引1
    if (minIndex != 1) {
        int tmp = array[minIndex];
        array[minIndex] = array[1];
        array[1] = tmp;
    }
    System.out.println(Arrays.toString(array));
}

得到数组：[1, 2, 4, 6, 8, 3, 7, 9, 5]

分析：

仔细观察两段代码，不难发现：
- 当 minIndex = 0 的时候，循环从 1 开始，最终交换 minIndex 和 0 位置上的元素。
- 当 minIndex = 1 的时候，循环从 2 开始，最终交换 minIndex 和 1 位置上的元素。
可以推测：当 minIndex = i 的时候，循环从 i+1 开始，最终交换 minIndex 和 i 位置上的元素。
那么我们最终需要进行多少次元素的选择呢？很简单，对9个元素排序，只需要进行8次即可。
就这样，新的一层循环嵌套已经呼之欲出了。int i = 0; i < array.length - 1; i++。

改进代码：

public static void main(String[] args) {
    int[] array = {6, 4, 2, 1, 8, 3, 7, 9, 5};
    for (int i = 0; i < array.length - 1; i++) {
        // 假设最小的元素索引是i
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            // 找到了更小的元素，更新索引
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        // 将最小的元素放置在索引i
        if (minIndex != i) {
            int tmp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = tmp;
        }
    }
    System.out.println(Arrays.toString(array));
}

到这里，一个完整的选择排序就实现了。

总结

选择排序是一个非常简单的入门级排序，它具有如下特点:

时间复杂度是O(n²)，
空间复杂度是O(1)。
是一个不稳定排序。

请深入理解了它的实现以后，在纯文本编辑的环境下手撕了它

最后编辑于：2020.05.29 18:21:13