js 实现选择排序及优化
2023-09-14 09:07:43 时间
// 选择排序 // 原理:进行 n-1 趟 循环,每趟循环中遍历所有未排好序的数,第一趟循环,从第0个元素开始向后遍历,找到 最小的元素,与第1 一个元素进行交换,第二趟,从第 1 个元素开始向后遍历,找到最小值与第2个元素 进行交换,以此类推 // 从而得出规律,每次遍历元素开始位置为 i+1,并维护每轮循环的最小值的索引,一轮循环结束后,通过最小值的索引获取到最小值,与起始位置交换 // 稳定性:因为选择排序每次找到最小值,都会与起始位置交换,所以是不稳定的 function selectSort(arr) { let length = arr.length; if (length < 2) { return arr; } // 定义 count 代表执行了趟循环 let count = 0; // 维护每趟循环中的未排序序列中的最小值,默认设为第一个值 let minIndex; let temp; for (let i = 0; i < length - 1; i++) { count++; // 每趟循环,将 minIndex 设为无序数列的起始索引 minIndex = i; for (let j = i + 1; j < length; j++) { minIndex = arr[j] < arr[minIndex] ? j : minIndex; // 将最小数的索引保存 } // 交换最小中与未排序序列开始遍历的第一个值 temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } console.log(`执行了${count}趟循环`); return arr; } console.log("普通选择排序"); console.log(selectSort([6, 3, 7, 8, 2, 4, 0, 1, 6, 5])); // 执行了9趟循环 console.log(selectSort([1, 2, 3, 4, 5, 6, 7, 8, 9, 9])); // 执行了9趟循环 // 优化选择排序,减少交换的次数及循环的趟数 function selectSort2(arr) { let length = arr.length; if (length < 2) { return arr; } // 定义 count 代表执行了趟循环 let count = 0; // 维护每趟循环中的未排序序列中的最小值,默认设为第一个值 let minIndex; let temp; for (let i = 0; i < length - 1; i++) { count++; // 默认为有序 let hasSort = true; // 每趟循环,将 minIndex 设为无序数列的起始索引 minIndex = i; for (let j = i + 1; j < length; j++) { if (arr[j] < arr[minIndex]) { // 只要进行交换,则本次是无序 hasSort = false; minIndex = j; // 将最小数的索引保存 } } // 交换最小中与未排序序列开始遍历的第一个值 // 减少交换的次数 if (arr[i] !== arr[minIndex]) { temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } // 当是有序数列时,跳出外层循环,减少循环趟 if (hasSort) { break; } } console.log(`执行了${count}趟循环`); return arr; } console.log("普通选择排序"); console.log(selectSort2([6, 3, 7, 8, 2, 4, 0, 1, 6, 5])); // 执行了7趟循环 console.log(selectSort2([1, 2, 3, 4, 5, 6, 7, 8, 9, 9])); // 执行了1趟循环
参考链接 :https://blog.csdn.net/hcz666/article/details/126486057
原文链接:https://www.cnblogs.com/beileixinqing/p/16649344.html
转载请注明出处。
相关文章
- 【说站】js中快速排序如何实现
- JS面试题-js新增基本数据类型BigInt
- js 数组去除重复数据-当WPS开始像支持VBA一样支持JS语言时,微软又该何去何从?
- JS手撕(十一) 选择排序、快速排序
- 【JS 逆向百例】猿人学系列 web 比赛第五题:js 混淆 - 乱码增强,详细剖析
- JS小技巧,如何使用内置函数对数组内容进行排序
- 【源码】PDF.js批注注释插件库(纯JS). 创建和保存PDF批注(PDF 高亮/签名/插图/截屏/文本框/画笔/多边形)-pdf.js
- js 设置焦点 判断控件是否获得焦点 判断哪个控件获得焦点详解编程语言
- 使用JS连接MySQL数据库:实现化繁为简(js连接mysql数据库)
- nodeMongoDB、Redis和Node.js:强大的组合服务器架构(mongodbredis)
- 使用JS技术实现Oracle数据库链接(js 链接 oracle)
- Redis中的订阅机制及其在JS中的应用(redis 订阅 js)
- js事件小结表格区别
- JS函数验证总结(方便js客户端输入验证)
- js常用排序实现代码
- 远离JS灾难css灾难之js私有函数和css选择器作为容器
- js三种排序算法分享
- js对数组中的数字从小到大排序实现代码
- js二维数组排序的简单示例代码
- JS获取几种URL地址的方法小结