javascript中排序算法大全
2021/4/8 12:38:22
本文主要是介绍javascript中排序算法大全,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
javascript当中存在两个API:sort和indexOf来实现排序和搜索,但知其然还要知其所以然,下面来看下javascript如何实现排序和搜索算法。
排序算法
1.冒泡排序
时间复杂度:O(n^2).
Array.prototype.bubbleSort = function () { for (let i = 0; i < this.length - 1; i++) { for (let j = 0; j < this.length - 1 - i; j++) { if (this[j] > this[j + 1]) { const temp = this[j]; this[j] = this[j + 1]; this[j + 1] = temp; } } } }; var arr = [3, 2, 4, 9, 1]; arr.bubbleSort(); console.log(arr);
2.选择排序
时间复杂度:O(n^2).
Array.prototype.selectionSort = function () { for (let i = 0; i < this.length - 1; i++) { let indexMin = i; for (let j = i; j < this.length - 1; j++) { if (this[j] < this[indexMin]) { indexMin = j; } } const temp = this[i]; this[i] = this[indexMin]; this[indexMin] = temp; } }; const arr = [3, 4, 1, 2, 5]; arr.selectionSort(); console.log(arr);
3.插入排序
时间复杂度:O(n^2).
Array.prototype.insertionSort = function () { for (let i = 1; i < this.length; i++) { let temp = this[i]; let j = i; //进行插入 while (j > 0) { if (this[j - 1] > temp) { this[j] = this[j - 1]; } else { break; } j--; } this[j] = temp; } }; const arr = [3, 4, 1, 2, 5]; arr.insertionSort(); console.log(arr);
4.归并排序
分的时间复杂度是O(logN)
合的时间复杂度是O(n)
时间复杂度:O(n*logN)
Array.prototype.mergeSort = function () { const rec = (arr) => { //递归判断条件 if (arr.length === 1) { return arr; } //先分数组 const mid = Math.floor(arr.length / 2); const left = arr.slice(0, mid); const right = arr.slice(mid, arr.length); const orderLeft = rec(left); const orderRight = rec(right); const res = []; //再治数组 while (orderLeft.length || orderRight.length) { if (orderLeft.length && orderRight.length) { res.push( orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift(), ); } else if (orderLeft.length) { res.push(orderLeft.shift()); } else if (orderRight.length) { res.push(orderRight.shift()); } } //数组合并 return res; }; const res = rec(this); res.forEach((n, i) => { this[i] = n; }); }; var arr = [3, 2, 4, 9, 1]; arr.mergeSort(); console.log(arr);
这篇关于javascript中排序算法大全的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性