排序算法(js版本)
2021/5/23 22:55:11
本文主要是介绍排序算法(js版本),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
几个概念
1、稳定排序:如果 a 原本在 b 的前面,且 a == b,排序之后 a 仍然在 b 的前面,则为稳定排序。
2、非稳定排序:如果 a 原本在 b 的前面,且 a == b,排序之后 a 可能不在 b 的前面,则为非稳定排序。
3、原地排序:原地排序就是指在排序过程中不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
4、非原地排序:需要利用额外的数组来辅助排序。
1.冒泡
思想:把第一个元素与第二个元素比较,如果第一个比第二个大,则交换他们的位置。接着继续比较第二个与第三个元素,如果第二个比第三个大,则交换他们的位置....
未优化
int [] arry={2,4,1,0,8,5}; int n=arry.length; int temp; for (int i = 0; i <n ; i++) { // 从0-i有序 for (int j = 0; j <n-i-1 ; j++) { if (arry[j]<arry[j+1]){ temp=arry[j]; arry[j]=arry[j+1]; arry[j+1]=temp; } } }
优化
相邻的元素之间都没有发生交换的操作,这意味着右边的元素总是大于等于左边的元素,此时的数组已经是有序的了.
for (let i = 0; i < a.length; i++) { let flag = false; let temp; for (let j = 0; j < a.length - i - 1; j++) { if (a[j] > a[j + 1]) { flag = true; temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp } } //如果没有交换,直接退出循环 if (!flag) { break; } }
插入排序
思路:
1、从数组第2个元素开始抽取元素。
2、把它与左边第一个元素比较,如果左边第一个元素比它大,则继续与左边第二个元素比较下去,直到遇到不比它大的元素,然后插到这个元素的右边。
3、继续选取第3,4,....n个元素,重复步骤 2 ,选择适当的位置插入。
let a = [1,4,5,1,2,9,0,3]; for(let i=1;i<a.length;i++){ for(let j=i-1;j>=0 && a[j]>a[j+1]; j--){ //这里用了解构来交换值 [a[j],a[j+1]]=[a[j+1],a[j]]; } }
性质:1、时间复杂度:O(n2) 2、空间复杂度:O(1) 3、稳定排序 4、原地排序
注意这里不能自己写个swap()函数来交换,牵扯到作用域的问题。
交换两个值有很多方法!
3.选择排序
思路:
1.在未排序的数列中找到最小(or最大)元素,然后将其存放到数列的起始位置
2.再从剩余未排序的元素中继续寻找最小(or最大)元素,然后放到已排序序列的末尾。
3.以此类推,直到所有元素均排序完毕。
let a = [1,4,5,1,2,9,0,3]; let min;//无序区的最小值 let i;//有序区的末尾位置 let j;//无序区的开始位置 for( i=0;i<a.length;i++){ min=i; //找出a[i+1]-a[n]之间最小的元素 for(j=i+1;j<a.length;j++){ if(a[j]<a[min]){ //更新无序区最小值的位置 min=j; } } //若min!=i,则交换 a[i] 和 a[min]。 //交换后,保证了a[0]..a[i]之间元素有序 if(min!=i){ [a[min],a[i]]=[a[i],a[min]]; } }
性质:1、时间复杂度:O(n2) 2、空间复杂度:O(1) 4、原地排序
稳定性得具体问题具体分析
不同的实现方法有不同的结果.
- 如果是在数组中交换,那么就有可能不稳定,如{5,5,2}
- 如果是链表或者开一个新的数组(自然不会破坏相同元素的相对位置),那么又是稳定的。
则可以这样说,当空间复杂度为O(1)的时候,是不稳定的。
《算法》p217,有提到,有很多办法可以将任意排序算法变成稳定的,但是,往往需要额外的时间或者空间。
这篇关于排序算法(js版本)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-06vue 新建功能多条数据(还没和后端交互)还能看详情 数据是前端缓存到本地吗?-icode9专业技术文章分享
- 2024-05-30React Native常用组件-点击组件
- 2024-05-30uniapp+vue3+uv-ui手机端后台OA管理模板
- 2024-05-29Python网络爬虫的时候json=就是让你少写个json.dumps()
- 2024-05-27React Native常用组件-展示组件
- 2024-05-27React Native常用组件-列表组件
- 2024-05-09vue3开发前端表单缓存自定义指令,移动端h5必备插件
- 2024-05-09React Hooks在class组件中的使用方式
- 2024-03-30[OIDC in Action] 2. 基于OIDC(OpenID Connect)的SSO(纯JS客户端)
- 2024-03-29terraform jsonencode