前端实现选择排序(Selection sort)算法
前端  /  管理员 发布于 8年前   460
选择排序(Selection sort)是一种简单直观的排序算法,无论什么数据进去都是 O(n²)
的时间复杂度,所以用到它的时候,数据规模越小越好
其基本思想是:首先在未排序的数列中找到最小(or最大)元素,然后将其存放到数列的起始位置
然后再从剩余未排序的元素中继续寻找最小(or最大)元素,然后放到已排序序列的末尾
以此类推,直到所有元素均排序完毕
举个例子,一个数组为 56、12、80、91、29,其排序过程如下:
从上面可以看到,对于具有 n
个记录的无序表遍历 n-1
次,第i
次从无序表中第 i
个记录开始,找出后序关键字中最小的记录,然后放置在第 i
的位置上
直至到从第n
个和第n-1
个元素中选出最小的放在第n-1
个位置
如下动画所示:
用代码表示则如下:
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
第一次内循环比较N - 1
次,然后是N-2
次,N-3
次,……,最后一次内循环比较1次
共比较的次数是 (N - 1) + (N - 2) + ... + 1
,求等差数列和,得 (N - 1 + 1)* N / 2 = N^2 / 2
,舍去最高项系数,其时间复杂度为 O(N^2)
从上述也可以看到,选择排序是一种稳定的排序
和冒泡排序一致,相比其它排序算法,这也是一个相对较高的时间复杂度,一般情况不推荐使用
但是我们还是要掌握冒泡排序的思想及实现,这对于我们的算法思维是有很大帮助的
123 在
Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..原梓番博客 在
在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..博主 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..1111 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..路人 在
php中使用hyperf框架调用讯飞星火大模型实现国内版chatgpt功能示例中评论 教程很详细,如果加个前端chatgpt对话页面就完美了..Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号