内容简介:先看看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动手试试。
代码实现
关于代码,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 选择排序》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 算法之常见排序算法-冒泡排序、归并排序、快速排序
- 排序算法之冒泡排序改进算法
- 快速排序算法,C语言快速排序算法深入剖析
- 排序算法下——桶排序、计数排序和基数排序
- 数据结构和算法面试题系列—排序算法之快速排序
- 数据结构和算法面试题系列—排序算法之基础排序
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。