【一起学习排序算法】3 选择排序

栏目: 编程工具 · 发布时间: 5年前

内容简介:先看看Wikipedia的定义:所以选择排序的思路就是:可以通过动画演示理解, 以下网上找的动画。如果你想操作不同的参数来演示,可以上这个网站visualgo.net动手试试。

先看看Wikipedia的定义:

The Selection sort algorithm divides the input list into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest element in the unsorted sublist, exchanging it with the leftmost unsorted element, and moving the sublist boundaries one element to the right. .

所以选择 排序 的思路就是:

  • 把列表分为两个部分,一部分是已经排好序,一部分待排序。
  • 初始有序子列为空,然后遍历待排序子列,找出最小的元素,然后和待排序子列的第一个元素互换。然后游标右移一个。这样有序子列增加一个元素。
  • 重复以上步骤,直到到最后一个元素,则表示数组有序。

图示

可以通过动画演示理解, 以下网上找的动画。如果你想操作不同的参数来演示,可以上这个网站visualgo.net动手试试。

【一起学习排序算法】3 选择排序

代码实现

关于代码,README中代码只有实现算法的函数,具体运行的代码,请查看该目录下的文件。

代码如下:

const selectSort = (array) => {
    // 不修改原数组
    const originValues = array.slice(); 
    const length = originValues.length;
    // 迭代次数 数组长度-1, 因为前n个元素有序,则全部有序
    for (let i = 0; i < length - 1; i++) {
        // 把当前无序子列的第一个元素当做最小值
        let minIndex = i;
        // 找出最小值的索引
        for (let j = i+1; j < length; j++) {
            if (originValues[j] < originValues[minIndex]) {
                minIndex = j;
            }
        }
        // 如果最小值不为当前值,交换
        if (minIndex !== i) {
            const tmp = originValues[i];
            originValues[i] = originValues[minIndex];
            originValues[minIndex] = tmp;
        }
    }

    return originValues;
};
复制代码

选择排序还是比较简单的,基本知道原理,看了注释就很明白了。有一点要说的是,就是在找最小值这个步骤。很多文章的实现,在发现当前值小于当前最小值时,就交换元素。这种交换还是没必要的,只要先记住最小值得下标 minIndex 就可以,最后一步来做交换。这样就减少了很多不必要的交换要素,后来发现和wikipedia的实现一模一样(第一次也是唯一一次,哈哈)。

算法分析

时间复杂度

选择排序,不管数组正序还是逆序,都是一样的操作。最优复杂度和最差复杂度都是O(n 2 )。

稳定性

因为可能存在和最小值元素交换是,把数值相同的元素顺序调换,所以, 选择排序是不稳定的排序

举个例子吧:

[3] 5 2 (3) 1
复制代码

由于最小的元素1在最后一个,需要和 [3] 元素交换,此时 [3] 就到 (3) 后面了。

有文章说选择排序是稳定的,其实看具体的实现。在《算法》第四版217页上作者已经说了,有很多办法可以将任意 排序算法 变成稳定的,但是,往往需要额外的时间或者空间。摘自知乎


以上所述就是小编给大家介绍的《【一起学习排序算法】3 选择排序》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

矩阵论

矩阵论

方保镕 / 清华大学出版社 / 2004-1 / 39.00元

本书比较全面、系统地介绍了矩阵的基本理论、方法及其应用。全书分上、下两篇,共10章,分别介绍了线性空间与线性算子,内积空间与等积变换,λ矩陈与若尔当标准形,赋范线性空间与矩阵范数,矩阵的微积分运算及其应用,广义逆矩阵及其应用,矩阵的分解,矩阵的克罗内克积、阿达马积与反积,几类特殊矩阵(如:非负矩阵与正矩阵、循环矩阵与素矩阵、随机矩阵和双随机矩阵、单调矩阵、M矩阵与H矩阵、T矩阵与汉大象尔矩阵等),......一起来看看 《矩阵论》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

在线进制转换器
在线进制转换器

各进制数互转换器

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具