JavaScript算法入门

女爷i 2022-12-23 03:26 97阅读 0赞

### JavaScript算法入门 ###

数组——最简单的内存数据结构

在很多编程语言中，数组的长度是固定的，当数组被填满时，再要加入新元素就很困难。Javascript 中数组不存在这个问题。

在很多编程语言中，数组存储一系列同一种数据类型的值，Javascript 中不存在这种限制。

JavaScript中的数组参见[https://www.runoob.com/jsref/jsref-obj-array.html][https_www.runoob.com_jsref_jsref-obj-array.html]

排序算法

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

function insertSort (arr) \{

var len = arr.length

for (i = 1; i < len; i++) \{

var key = arr\[i\]

var j = i - 1

while (j >= 0 && arr\[j\] > key) \{

arr\[j+1\] = arr\[j\]

j--;

arr\[j+1\] = key

return arr

var arr=\[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48\];

console.log(insertSort(arr));//\[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50\]

测试运行结果参见下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70][]

快速排序

快速排序是处理 大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方法将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤知道所有数据都是有序的。

这个算法首先要在列表中选择一个元素作为基准值。数据排序围绕基准值进行，将列表中小于基准值的元素移到数组的底部，将大于基准值的元素移到数组的顶部。

function qSort (arr) \{

if (arr.length == 0) \{

return \[\]

var left = \[\]

var right = \[\]

var pivot = arr\[0\]

for (var i = 1; i < arr.length; i++) \{

if (arr\[i\] < pivot) \{

left.push(arr\[i\])

\} else \{

right.push(arr\[i\])

return qSort(left).concat(pivot, qSort(right))

var arr=\[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48\];

console.log(qSort(arr));

测试运行结果参见下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 1][]

链表——存储有序的元素集合，但在内存中不是连续放置的。

链表是由一组节点组成的集合。每一个节点都使用一个对象的引用指向它的后续借点。指向另外一个借点的引用叫做链。

在此仅简单介绍(单向链表。

单向链表中的元素由存放元素本身「data」 的节点和一个指向下一个「next」 元素的指针组成。牢记这个特点。

相比数组，链表添加或者移除元素不需要移动其他元素，但是需要使用指针。访问元素每次都需要从表头开始查找。

在链表中插入一个节点的效率很高。向链表中插入一个节点，需要修改它前面的节点，使其指向新加入的节点，而新加入的节点则指向前面指向的节点。如下图展示的是在eggs后面加上cookies节点。如下图：

![20201122100952988.png][]

从链表中删除一个节点也很简单，将待删除的元素的前驱节点指向待删除的后续节点，同时将待删除元素指向null来释放。下图是一个巧合删除是的null元素前面的一个元素。如下图：

![20201122100952988.png][]

下面的代码来测试链表  
<!DOCTYPE html>  
<html>  
<head>  
<meta charset="utf-8">   
<title>单向链表的例子</title>  
</head>  
<body>  
<script>

//定义结点  
function Node(element)\{  
    this.element = element;  
    this.next = null;  
\}

//对链表进行操作  
function LList()\{  
    this.head = new Node('head');  
    this.find = find;  
    this.insert = insert;  
    //this.remove = remove;  
    this.display = display;  
\}

//遍历查找链表  
function find(item)\{  
    var currNode = this.head;  
    while (currNode.element != item)\{  
        currNode = currNode.next;  
    \}  
    return currNode;  
\}

//插入一个元素  
function insert(newElement, item)\{  
    var newNode = new Node(newElement);  
    var current = this.find(item);  
    newNode.next = current.next;  
    current.next = newNode;  
\}

//打印(显示)链表元素  
function display()\{  
    var currNode = this.head;  
    while (!(currNode.next == null))\{  
        document.write(currNode.next.element + ' ');  
        currNode = currNode.next;  
    \}  
\}

//测试程序  
var cities = new LList();  
cities.insert("北京", "head"); //添加元素：北京  
cities.insert("上海", "北京"); //添加元素：上海  
cities.insert("天津", "上海"); //添加元素：天津  
cities.insert("重庆", "天津"); //添加元素：重庆  
cities.display(); //打印(显示)链表元素

</script>  
</body>  
</html>

保存文件名为：单向链表的例子.html

测试运行结果参见下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 2][]

最后，给出实现等腰三角形、直角三角形、菱形代码

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 3][]

☆等腰三角形源码：

<!DOCTYPE html>  
<html>  
<head>  
    <meta charset="UTF-8">  
    <title>等腰三角形</title>  
    <style>  
        \*\{  
            font-family: Courier, monospace;  
        \}  
    </style>  
      
</head>  
<body>  
    <script>  
        for(var a =1;a<6;a++)\{  
        //a代表行；  
            for(var b = 1;b<6-a;b++)\{  
            //b表示在哪里运用空格;  
                document.write("&nbsp;");  
            \}  
            for(var c = 1;c<=2\*a-1;c++)\{  
            //d表示打印多少个\*  
                    document.write("\*");  
                \}  
            document.write("<br>");  
        \}  
    </script>  
</body>  
</html>

☆直角三角形源码：

<!DOCTYPE html>  
<html>  
<head>  
    <meta charset="UTF-8">  
     <title>直角三角形</title>  
    <style>  
        \*\{  
            font-family: Courier, monospace;  
        \}  
    </style>  
      
</head>  
<body>  
    <script>  
        for(var i=0;i<6;i++)  
        \{  
            var s="";  
            for(var k=0;k<2\*i+1;k++)  
            \{  
                  document.write("\*");  
            \}  
            document.write("<br>");  
        \}  
    </script>  
</body>  
</html>

☆菱形源码

<!DOCTYPE html>  
<html>  
<head>  
    <meta charset="UTF-8">  
    <title>打印一个菱形</title>  
    <style>  
        \*\{  
            font-family: Courier, monospace;  
        \}  
    </style>  
</head>  
<body>  
    <script>  
        for(var a =1;a<6;a++)\{  
            for(var b = 1;b<6-a;b++)\{  
                document.write("&nbsp;");  
            \}  
            for(var c = 1;c<=2\*a-1;c++)\{  
                    document.write("\*");  
                \}  
            document.write("<br>");  
        \}  
        // document.write("<br>");  
        for(var d = 1;d<5;d++)\{  
            for(var e=1;e<=d;e++)\{  
                document.write("&nbsp;");  
            \}  
            for(var f = 1;f<=(5-d)\*2-1;f++)\{  
                document.write("\*");  
            \}  
            document.write("<br>");  
        \}  
    </script>  
</body>  
</html>

[https_www.runoob.com_jsref_jsref-obj-array.html]: https://www.runoob.com/jsref/jsref-obj-array.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70]: /images/20221120/57dc53f6aa714234b5cb2ce70c603b7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201122100952993.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM=,size_16,color_FFFFFF,t_70
[20201122100952988.png]: https://img-blog.csdnimg.cn/20201122100952988.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201122101127394.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210202113441507.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM=,size_16,color_FFFFFF,t_70