JavaScript经典算法实例：线性查找、二分搜索与排序

68 浏览量更新于2024-08-30 收藏 129KB PDF 举报

"本文详细介绍了JavaScript中的几种经典算法，包括线性查找、二分查找、冒泡排序、选择排序和插入排序。这些算法是编程基础知识的重要组成部分，对于理解数据处理和优化程序性能至关重要。" 线性查找是一种基础的搜索算法，其时间复杂度为O(n)。在给定的数组A中寻找值x时，线性查找会逐个检查数组元素，直到找到匹配的x或者遍历完整个数组。如果找到匹配项，则返回该元素的索引，否则返回-1。这种方法虽然简单，但在大数据量的情况下效率较低。二分查找，又称为折半查找，适用于已排序的线性结构，其时间复杂度为O(logN)。算法通过不断将待搜索区间减半来快速定位目标元素。每次比较中间元素，如果目标值等于中间元素则返回索引；如果目标值小于中间元素，则在左半部分继续搜索；反之，在右半部分搜索。如此递归进行，直到找到目标元素或搜索范围为空。冒泡排序是一种简单的排序算法，时间复杂度为O(n^2)。它通过不断交换相邻的不正确顺序的元素来逐步排序整个数组。当一轮比较结束后没有发生任何交换，说明数组已经排序完成。选择排序同样具有O(n^2)的时间复杂度，其工作原理是每次遍历未排序部分，找到最小（或最大）的元素，然后将其与未排序部分的第一个元素交换。这个过程重复n-1次，直到所有元素排序完毕。插入排序同样具有O(n^2)的时间复杂度，它的基本思想是将数组分为已排序部分和未排序部分，每次从未排序部分取出一个元素，插入到已排序部分的正确位置，以此逐渐扩大已排序部分，直至整个数组有序。这些算法是JavaScript编程中常见的基础操作，理解并掌握它们对于提升编程技能、解决实际问题以及优化代码性能具有重要意义。在实际开发中，根据数据特性和需求，选择合适的算法能够显著提高程序执行效率。

var preNode = this.getNodeByIndex(n - 1);

preNode.next = preNode.next.next;

}

//取第N个位置的节点(约定头节点为第0个位置)

//N大于链表元素个数时，返回最后一个元素

this.getNodeByIndex = function (n) {

var p = this.head;

var i = 0;

while (p.next != null && i < n) {

p = p.next;

i++;

}

return p;

}

//查询值为V的节点，

//如果链表中有多个相同值的节点，

//返回第一个找到的

this.getNodeByValue = function (v) {

var p = this.head;

while (p.next != null) {

p = p.next;

if (p.data == v) {

return p;

}

return null;

}

//打印输出所有节点

this.print = function () {

var p = this.head;

while (p.next != null) {

p = p.next;

print(p.data + " ");

}

println("");

}

//测试单链表L中是否有重复元素

function hasSameValueNode(singleLink) {

var i = singleLink.head;

while (i.next != null) {

i = i.next;

var j = i;

while (j.next != null) {

j = j.next;

if (i.data == j.data) {

return true;

}

return false;

}

//单链表元素反转

function reverseSingleLink(singleLink) {

var arr = new Array();

var p = singleLink.head;

//先跑一遍，把所有节点放入数组

while (p.next != null) {

p = p.next;

arr.push(p.data);

}

var newLink = new SingleLink();

//再从后向前遍历数组,加入新链表

for (var i = arr.length - 1; i >= 0; i--) {

newLink.insert(arr[i]);

}

return newLink;

}

var linkTest = new SingleLink();

linkTest.insert('A');

linkTest.insert('B');

linkTest.insert('C');

linkTest.insert('D');

linkTest.print();//A B C D

var newLink = reverseSingleLink(linkTest);

newLink.print();//D C B A

</script>

关于邻接矩阵、邻接表邻接矩阵、邻接表的选择：

邻接矩阵、邻接表都是图的基本存储方式，

剩余11页未读，继续阅读

weixin_38718690

粉丝: 6
资源: 944

JavaScript经典算法实例：线性查找、二分搜索与排序

JS实现的几个常用算法

自己总结的二十四道js算法题

前端JS面试中常见的算法问题总结

javascript 磁盘调度算法

瑞士轮算法javascript实例

Javascript算法

JavaScript的设计模式详解

使用原生ajax进行提交实例详解

javaScript中的继承extends详解

数据结构与算法javascript描述

最新资源