首页 > 代码库 > JS-排序详解-选择排序
JS-排序详解-选择排序
说明
- 时间复杂度指的是一个算法执行所耗费的时间
- 空间复杂度指运行完一个程序所需内存的大小
- 稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面
- 不稳定指,如果a=b,a在b的前面,排序后可能会交换位置
JS选择排序
原理
首先从原始数组中找到最小的元素,并把该元素放在数组的最前面,然后再从剩下的元素中寻找最小的元素,放在之前最小元素的后面,知道排序完毕。
时间复杂度,空间复杂度,稳定性
- 平均时间复杂度O(n*n)
- 最好情况O(n*n)
- 最差情况O(n*n)
- 空间复杂度O(1)
- 稳定性:不稳定
选择排序的写法
var example=[8,94,15,88,55,76,21,39]; function selectSort(arr){ var len=arr.length; var minIndex,temp; console.time(‘选择排序耗时‘); for(i=0;i<len-1;i++){ minIndex=i; for(j=i+1;j<len;j++){ if(arr[j]<arr[minIndex]){ minIndex=j; } } temp=arr[i]; arr[i]=arr[minIndex]; arr[minIndex]=temp; } console.timeEnd(‘选择排序耗时‘); return arr; } console.log(selectSort(example));
解析
minIndex始终保存着最小值的位置的索引,随着i的自增,遍历的数组长度越来越短,直到完成排序。
JS-排序详解-选择排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。