JavaScript数据结构和算法

数据结构和算法
Word count: 4.6k   |   Reading time≈ 21 min

数据结构

存储和组织数据的一种方式

数组（Array）

通常情况下用于存储一系列同一种数据类型的值

创建和初始化

  • new Array('a','b')
  • ['a','b']

常用操作

添加元素
  • 数组的末尾添加元素 arr.push(item)
  • 数组的首位插入一个元素 arr.unshift(item)
  • 指定位置插入元素 arr.splice(index,0,item)
删除元素
  • 数组的末尾删除一个元素 arr.pop()
  • 数组的首位删除一个元素 arr.shift()
  • 删除指定位置的元素 arr.splice(start,number) 
1
2
3
let arr = [1,2,3,4]
arr.splice(1,2) // 起始位置，删除的个数
arr // [1,4]
修改元素
  • 修改指定索引的元素 arr.splice(index,1,item)
  • 修改指定索引的多个元素 arr.splice(index,number,item) 
1
2
3
let arr = [1,2,3,4,5]
arr.splice(1,2,'qq','bb')
arr // [1,'qq','bb',4,5]

栈（Stack）

数组是一个线性结构，并且可以在数组的任意位置插入和删除元素。但是有时候，我们为了实现某些功能，必须对这种任意性加以限制。栈和队列就是比较常见的受限的线性结构。

栈（stack）是一种运算受限的线性表：

  • LIFO（last in first out）表示就是后进入的元素，第一个弹出栈空间
  • 其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底
  • 向一个栈插入新元素又称作进栈(入栈/压栈)，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素
  • 从一个栈删除元素又称作出栈(退栈)，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素


先进后出，后进先出

程序中的栈结构

  • 函数调用: A(B(C(D()))): 即 A 函数中调用 B，B 调用 C，C 调用 D；在 A 执行的过程中会将 A 压入栈，随后 B 执行时 B 也被压入栈，函数 C 和 D 执行时也会被压入栈。所以当前栈的顺序为：A->B->C->D（栈顶）；函数 D 执行完之后，会弹出栈被释放，弹出栈的顺序为 D->C->B->A

  • 递归: 为什么没有停止条件的递归会造成栈溢出？比如函数 A 为递归函数，不断地调用自己（因为函数还没有执行完，不会把函数弹出栈），不停地把相同的函数 A 压入栈，最后造成栈溢出(Queue Overfloat)

栈结构实现

常用操作
  • push(item) 添加一个新元素到栈顶
  • pop() 移除栈顶元素（出栈）
  • peek() 返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）
  • isEmpty() 判断栈内是否有元素
  • size() 返回栈内元素个数
  • toString() 将栈结构的内容通过字符串的形式返回
JavaScript实现栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Stock {
    constructor() {
        this.items = []
    }
    // 进栈
    push(item) {
        this.items.push(item)
    }

    // 出栈,并返回该元素
    pop() {
        return this.items.pop()
    }

    // 返回当前栈顶元素(不改变栈)
    peek() {
        return this.items[this.items.length - 1]
    }

    // 判断栈是否为空
    isEmpty() {
        return this.items.length ? false : true
    }

    // 获取栈元素的个数
    size() {
        return this.items.length
    }

    // 以字符串的形式返回栈内元素
    toString() {
        let result = ''
        this.items.forEach((item) => {
            result += item + ''
        })
        return result
    }
}

let stock = new Stock()
stock.push(1)
stock.push(1)
stock.push(2)
console.log(stock.pop()) // 2
console.log(stock.items) // [1,1]
console.log(stock.peek()) // 1
console.log(stock.isEmpty()) // false
console.log(stock.size()) // 2
console.log(stock.toString()) // 1 1

简单应用

栈结构实现十进制转二进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function dec2bin(number) {
    let stock = new Stock()
    while (number) {
        stock.push(number % 2)
        number = Math.floor(number / 2)
    }
    let str = ''
    while(!stock.isEmpty()){
        str += stock.pop()
    }
    return str
}
console.log(dec2bin(10))  // 1010
console.log((10).toString(2)) //1010

队列（Queue）

是一种运算受限的线性表，特点：先进先出。(FIFO：First In First Out)

常用操作

  • enqueue(element) 向队尾添加一个/多个新的项
  • dequeue() 移除队列的第一项，并返回移除的元素
  • front() 返回队列中的第一个元素（最先被添加的，也是最早被移除的元素。不改变队列）
  • isEmpty() 是否有元素
  • size() 返回队列元素个数
  • toString() 将队列内容转换成字符串的形式

JavaScript实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Queue {
    constructor() {
        this.items = []
    }
    enqueue(element) {
        this.items.push(element)
    }
    dequeue() {
        return this.items.shift()
    }
    front() {
        return this.items[0]
    }
    isEmpty() {
        return !Boolean(this.items.length)
    }
    size() {
        return this.items.length
    }
    toString() {
        let str = ''
        this.items.forEach(item => {
            str += item + ' '
        })
        return str
    }
}

let queue = new Queue
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
console.log(queue.dequeue()) // 1
console.log(queue.front())   // 2
console.log(queue.isEmpty()) // false
console.log(queue.size())    // 2
console.log(queue.toString()) //  2 3

简单实现

击鼓传花游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function game(array, number) {
    let queue = new Queue()
    array.forEach(item => {
        // 进入队列
        queue.enqueue(item)
    })

    while (queue.size() > 1) {
        for (let i = 0; i < number - 1; i++) {
            // 不是number项的进入队尾
            queue.enqueue(queue.dequeue())
        }
        // 删除number项
        queue.dequeue()
    }

    // 获取留到最后一个的值
    const end = queue.front()
    return array.indexOf(end)  // 返回值所在的索引
}

let arr = ['doreen', 'jerry', 'sherry', 'tom', 'amy', 'gaga']
console.log(arr[game(arr, 2)])  // amy

优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class QueueElement {
    // 元素和他的优先级
    constructor(element, priority) {
        this.element = element
        this.priority = priority
    }
}

class PriorityQueue extends Queue {
    constructor() {
        super()
    }

    enqueue(element, priority) {
        const queueElement = new QueueElement(element, priority)
        if (this.isEmpty()) {
            this.items.push(queueElement)
        } else {
            let add = false
            for (let i = 0; i < this.items.length; i++) {
                if (this.items[i].priority > queueElement.priority) {
                    this.items.splice(i, 0, queueElement)
                    add = true; break
                }
            }
            if (!add) {
                this.items.push(queueElement)
            }
        }
    }

    toString() {
        let str = ''
        this.items.forEach(item => {
            str += item.element + '-' + item.priority + ' '
        })
        return str

    }


}

let queue = new PriorityQueue()
queue.enqueue(1, 1)
queue.enqueue(2, 0)
console.log(queue.toString())   // 2--0 1-1

链表（Linked List）

链表和数组

数组缺点

  • 数组的创建需要申请一段连续的内存空间(一整块内存)，并且大小是固定的，当前数组不能满足容量需求时，需要扩容。 (一般情况下是申请一个更大的数组，比如 2 倍，然后将原数组中的元素复制过去)

  • 在数组开头或中间位置插入数据的成本很高，需要进行大量元素的位移。

链表

链表中的元素在内存中不必是连续的空间。链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针)组成。

单向链表

优点
  • 内存空间不必是连续的，可以充分利用计算机的内存，实现灵活的内存动态管理。
  • 链表在插入和删除数据时，时间复杂度可以达到 O(1)，相对数组效率高很多。
    缺点
  • 访问任何一个位置的元素时，需要从头开始访问。(无法跳过第一个元素访问任何一个元素)
  • 无法通过下标值直接访问元素，需要从头开始一个个访问，直到找到对应的元素。
  • 虽然可以轻松地到达下一个节点，但是回到前一个节点是很难的。
常用操作
  • append(element) 链尾添加新项
  • insert(position,element) 在指定位置添加新项
  • get(position) 获取对应位置的元素
  • indexOf(element) 返回该元素在链表的索引，没有则为-1
  • update(position,element) 修改指定位置的元素
  • removeAt(position) 从链表的特定位置移除一项
  • remove(element) 从链表中移除一项
  • isEmpty()
  • size()
  • toString()
JavaScript实现单向链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
class Node {
    constructor(data) {
        this.data = data
        this.next = null
    }
}

class LinkedList {
    constructor() {
        this.length = 0
        this.head = null
    }
    apped(data) {
        let node = new Node(data)
        if (!this.length) {
            this.head = node
        } else {
            let nextNode = this.head
            while (nextNode.next !== null) {
                nextNode = nextNode.next
            }
            nextNode.next = node
        }
        this.length++
    }

    insert(position, element) {
        if (this.length >= position && position >= 0) {

            let newNode = new Node(element)
            let currentNode = this.head
            let nextNode;
            if (position === 0) {
                this.head = newNode
                this.head.next = currentNode
            } else {
                while (position > 1) {
                    currentNode = currentNode.next
                    position--
                }
                nextNode = currentNode.next
                currentNode.next = newNode
                newNode.next = nextNode
                this.length++
            }
            return this.head
        } else {
            return false
        }
    }

    get(position) {
        if (position < 0 || position >= this.length) return false
        if (position === 0) return this.head.data
        let currentNode = this.head
        while (position > 0) {
            currentNode = currentNode.next
            position--
        }
        return currentNode.data
    }

    indexOf(element) {
        let index = 0
        let currentNode = this.head
        while (currentNode) {
            if (currentNode.data === element) {
                return index
            }
            currentNode = currentNode.next
            index++
        }

        return -1
    }

    update(position, element) {
        if (position >= this.length || position < 0) return false
        let currentNode = this.head
        let newNode = new Node(element)

        while (position > 0) {
            currentNode = currentNode.next
            position--
        }

        currentNode.data = newNode.data
        return currentNode
    }

    removeAt(position) {

        if (position >= this.length || position < 0) return false
        let currentNode = this.head

        if (position === 0) {
            this.head = this.head.next
        } else {
            let previousNode;

            while (position > 0) {
                previousNode = currentNode
                currentNode = currentNode.next
                position--

            }
            previousNode.next = currentNode.next
        }

        this.length--
        return currentNode
    }

    remove(element) {
        this.removeAt(this.indexOf(element))
    }

    isEmpty() {
        return this.length === 0
    }

    size() {
        return this.length
    }

    toString() {
        let str = ''
        let currentNode = this.head
        while (currentNode) {
            str += currentNode.data + ' '
            currentNode = currentNode.next
        }
        return str
    }
}
let link = new LinkedList()
link.apped(2)
link.apped(5)
link.insert(2, 4)   // 2 -> 5 -> 4
console.log(link.get(1))    // 5
console.log(link.indexOf(5))    // 1
console.log(link.removeAt(1))   // 删掉了：5  链表：2 -> 4
link.remove(2)
console.log(link.toString())    // 4

双向链表

  • 既可以从头遍历到尾，也可以从尾遍历到头。
  • 链表相连的过程是双向的。实现原理是一个节点既有向前连接的引用，也有一个向后连接的引用。
  • 双向链表可以有效的解决单向链表存在的问题。
  • 双向链表缺点：
    • 每次在插入或删除某个节点时，都需要处理四个引用，而不是两个，实现起来会困难些。
    • 相对于单向链表，所占内存空间更大一些。
      双向链表结构
      常用操作
  • append(element) 向链表尾部追加一个新元素。
  • insert(position, element) 向链表的指定位置插入一个新元素。
  • get(position) 获取指定位置的元素。
  • indexOf(element) 返回元素在链表中的索引。如果链表中没有该元素就返回 -1。
  • update(position, element) 修改指定位置上的元素。
  • removeAt(position) 从链表中的删除指定位置的元素。
  • remove(element) 从链表删除指定的元素。
  • isEmpty() 如果链表中不包含任何元素，返回 trun，如果链表长度大于 0 则返回 false。
  • size() 返回链表包含的元素个数，与数组的 length 属性类似。
  • forwardString() 返回正向遍历节点字符串形式。
  • backwordString() 返回反向遍历的节点的字符串形式。
JavaScript实现双向链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
class Node {
    constructor(data) {
        this.data = data
        this.next = null
        this.prev = null
    }
}

class LinkedList {
    constructor() {
        this.length = 0
        this.head = null
        this.tail = null
    }
    append(element) {
        let newNode = new Node(element)

        if (this.length === 0) {
            this.head = newNode
            this.tail = newNode
        } else {
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
        }
        this.length++
    }

    insert(position, element) {

        if (position < 0 || position > this.length) return false
        let newNode = new Node(element)
        let currentNode = this.head
        let previousNode;
        if (position === 0) {
            if (this.head === null) {
                this.head = newNode
                this.tail = newNode
            } else {
                newNode.next = currentNode
                currentNode.prev = newNode
                this.head = newNode
            }

        } else if (position === this.length) {
            newNode.prev = this.tail
            this.tail.next = newNode
            this.tail = newNode

        } else {
            while (position > 0) {
                previousNode = currentNode
                currentNode = currentNode.next
                position--
            }
            newNode.prev = previousNode
            newNode.next = currentNode
            previousNode.next = newNode
            currentNode.prev = newNode

        }
        this.length++
        return currentNode
    }

    get(position) {
        if (position < 0 || position >= this.length) return false
        if (position === 0) {
            return this.head.data
        }
        if (position === this.length - 1) {
            return this.tail.data
        }
        let currentNode = this.head
        while (position > 0) {
            currentNode = currentNode.next
            position--
        }
        return currentNode.data

    }

    indexOf(element) {
        let currentNode = this.head
        let index = 0
        if (!this.length) return -1

        while (currentNode) {
            if (currentNode.data === element) {
                return index
            }
            currentNode = currentNode.next
            index++
        }
        return -1
    }

    update(position, element) {
        if (position < 0 || position >= this.length) return false
        let currentNode = this.head
        if (position === 0) {
            this.head.data = element
        }
        while (position > 0) {
            currentNode = currentNode.next
            position--
        }
        currentNode.data = element
        return currentNode
    }

    removeAt(position) {
        if (position < 0 || position >= this.length) return false
        let currentNode = this.head
        let prevNode;
        if (position === 0) {
            if (this.length === 1) {
                this.head = null
                this.tail = null
            } else {
                this.head = this.head.next
                this.head.prev = null
            }
        } else if (position === this.length - 1) {
            this.tail = this.tail.prev
            this.tail.next = null
        } else {
            while (position > 0) {
                prevNode = currentNode
                currentNode = currentNode.next
                position--
            }
            prevNode.next = currentNode.next
            currentNode.next.prev = prevNode
        }
        this.length--

    }

    remove(element) {
        return this.removeAt(this.indexOf(element))
    }
    isEmpty() {
        return this.length === 0
    }
    size() {
        return this.length
    }

    forwardString() {
        let str = ''
        let currentNode = this.head
        while (currentNode) {
            str += currentNode.data + ' '
            currentNode = currentNode.next
        }
        return str
    }
    backwordString() {
        let str = ''
        let currentNode = this.tail
        while (currentNode) {
            str += currentNode.data + ' '
            currentNode = currentNode.prev
        }
        return str
    }
}

let link = new LinkedList()
link.append(1)
link.append(2)
link.insert(2, 3)
// 1 2 3
link.update(2, 5) // 1 2 5
console.log(link.forwardString())   // 1 2 5
console.log(link.backwordString())  // 5 2 1

集合

集合比较常见的实现方式是哈希表，这里使用 JavaScript 的 Object 进行封装

集合特点

  • 集合通常是由一组无序的、不能重复的元素构成
  • 数学中常指的集合中的元素是可以重复的，但是计算机中集合的元素不能重复
  • 集合是特殊的数组
    • 特殊之处在于里面的元素没有顺序，也不能重复
    • 没有顺序意味着不能通过下标值进行访问，不能重复意味着相同的对象在集合中只会存在一份

常用操作

  • add(value)
  • remove(value)
  • has(value)
  • clear() 移除所有项
  • size()
  • values() 返回一个包含集合中所有值的数组

集合之间的操作

  • 并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。
  • 交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合。
  • 差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。
  • 子集：验证一个给定集合是否是另一个集合的子集。

JavaScript实现集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Set {
    constructor() {
        this.items = {}
    }
    has(value) {
        return this.items.hasOwnProperty(value)
    }
    add(value) {
        if (this.has(value)) return false
        this.items[value] = value
        return true
    }
    remove(value) {
        if (this.has(value)) return false
        delete this.items[value]
    }
    clear() {
        this.items = {}
    }
    size() {
        return Object.keys(this.items).length
    }
    values() {
        return Object.values(this.items)
    }

    // 集合间的操作

     // union() 求两个集合的并集
    union(other) {
        let unionSet = new Set()
        for (let value of this.values()) {
            unionSet.add(value)
        }
        for (let value of other.values()) {
            unionSet.add(value)
        }
        return unionSet
    }

    // intersection() 求两个集合的交集
    intersection(other) {
        let intersectionSet = new Set()
        for (let value of this.values()) {
            if (other.has(value)) {
                intersectionSet.add(value)
            }
        }
        return intersectionSet
    }

    // difference() 差集
    difference(other) {
        let differenceSet = new Set()
        for (let value of this.values()) {
            if (!other.has(value)) {
                differenceSet.add(value)
            }
        }
        return differenceSet
    }

    // subset() 子集
    subset(other) {
        for(let value of this.values()){
            if(!other.has(value)){
                return false
            }
        }
        return true
    }
}
let set = new Set()
set.add('abc')
set.add('abc')
set.add('123')
console.log(set) // {'abc':'abc','123':'123'}

字典

特点

  • 字典存储的是键值对，主要特点是一一对应
  • key是不能重复且无序的，而Value可以重复

常用操作

  • set(key,value) 向字典中添加新元素
  • remove(key) 通过使用键值来移除对应数据
  • has(key)
  • get(key)
  • clear()
  • size()
  • keys()
  • values()

JavaScript代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Map {
    constructor() {
        this.items = {}
    }

    has(key) {
        return this.items.hasOwnProperty(key)
    }

    set(key, value) {
        this.items[key] = value
    }

    remove(key) {
        if (this.has(key)) delete this.items[key]
    }

    get(key) {
        if (this.has(key)) return this.items[key]
        return undefined
    }

    clear() {
        this.items = {}
    }

    size() {
        return Object.keys(this.items).length
    }

    keys() {
        return Object.keys(this.items)
    }

    values() {
        return Object.values(this.items)
    }
}

散列[哈希]表（Hash）

哈希表的结构就是数组，但它神奇之处在于对下标值的一种变换，这种变换我们可以称之为哈希函数，通过哈希函数可以获取 HashCode

树（Tree）

堆（Heap）

算法

解决问题的方法/步骤逻辑

排序算法

冒泡排序

  • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 

1
2
3
4
5
6
7
8
9
10
function bubbleSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            let m = arr[j]
            let n = arr[j + 1]
            if (n < m) [arr[j + 1], arr[j]] = [m, n]
        }
    }
    return arr
}

快速排序

对冒泡排序的改进

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，
然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function quickSort(arr) {
    let array = arr
    function sort(array) {
        let left = [], center, right = []
        if (array.length <= 1) return array
        center = array[0]
        for (let i = 1; i < array.length; i++) {
            if (array[i] > center) {
                right.push(array[i])
            } else {
                left.push(array[i])
            }
        }
        return [...sort(left), center, ...sort(right)]
    }
    return sort(array)
}

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
function searchSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let m = i
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[m] > arr[j]) {
                m = j // 找到最小值所在的位置
            }
        }
        // 位置置换
        [arr[m], arr[i]] = [arr[i], arr[m]]
    }
    return arr
}

插入排序

在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
function insertSort(arr) {
    var j;
    for (var i = 1; i < arr.length; i++) {
        var temp = arr[i]
        j = i - 1
        while (temp < arr[j] && j >= 0) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = temp
    }
    return arr;
}

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2019-2023 John Doe
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信