选择排序

目标:会手写

这篇文章主要带大家来了解什么是选择排序,选择排序可以说是最简单的一种排序算法了。

虽然比较简单,但是在讲解完选择排序的最后也给大家留了一道思考题,大家可以尝试实现,拓展自己的思路。

还记得我们上篇文章讲冒泡排序的原理吗?

算法的核心是在排序的过程中将数组分成有序和无序的两部分,并在排序的过程中不断的让无序的部分变得有序。

其实选择排序的核心思路也是如此。

那选择排序算法是怎么逐渐的将数组变有序的?

我们通过遍历从数组的无序部分中选择最小的元素,并放到数组的有序部分的最后一个位置(升序)。并重复这个过程。

选择排序算法流程分析

我们通过一个对有 n 个元素的数组进行选择排序的具体例子,来演示这个过程。

排序之前

8 4 2 6 9 6

排序之前整个数组从 [0, n - 1] 这个范围都是无序的。

第一轮选择

我们从第一个元素开始,依次遍历数组的无序部分(目前也就是整个数组),发现最小的元素是 2,此时将其放到数组的有序的部分的最后一个位置(即整个数组的第一个位置)。

结果:

2 8 4 6 9 6

此时,数组从 [0, 0] 这个范围是有序的,从 [1, n - 1] 这个范围是无序的。

接下来,我们只需要对 [1, n - 1] 这个范围重复上面的操作。

第二轮选择

我们从第二个元素开始,依次遍历,发现最小的元素是 4。

接下来希望大家自己按照这个比较的方法,自己推演体会这个过程。

结果:

2 4 8 6 9 6

经过第二轮选择之后,数组从 [0, 1] 这个范围是有序的,从 [2, n - 1] 这个范围是无序的。

接下来,我们只需要对 [2, n - 1] 这个范围重复上面的操作进行排序。

继续选择

依次类推,我们可以顺利推出下面几次选择的结果,并在最后得到有序的数组。

第三轮选择结果

2 4 6 8 9 6

第四轮选择结果

2 4 6 6 8 9

第五轮选择结果

2 4 6 6 8 9

代码实现

public void selectSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int minIndex = i;
        for (int j = i; j < nums.length; j++) {
            minIndex = nums[j] < nums[minIndex] ? j : minIndex;
        }
        swap(nums, i, minIndex);
    }
}

public void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

时间复杂度

选择排序的时间复杂度是 {O(n^2)}

仔细想想其实是没有啥优化空间了,因为我们不得不通过遍历数组的无序部分才能选择出最小的元素。

空间复杂度

选择排序和冒泡排序一样,也属于典型的原地排序算法,空间复杂度为 {O(1)},因为只需要常数级别的额外空间来存储临时变量。

稳定性

选择排序 不是一种稳定的排序算法。在我们的算法实现中,在交换元素时,相同元素的相对位置会发生改变。

写在最后

总的来说,选择排序虽然可以说是最简单的排序算法,我们在前文也给出了迭代算法的实现,不过大家可以尝试下用递归的方法,去实现选择排序,同一个问题可以多尝试不同的方法,这样才能打开自己解决问题的思维。

为今后学习更复杂的算法问题提供帮助,毕竟罗马不是一天建成的。

好了,今天的学习比较轻松,我们下篇文章再见。

发表回复

后才能评论