JavaScript版数据结构与算法——基础篇（二）

发表于 阅读次数：

JavaScript版数据结构与算法基础第二篇

本文是上一篇的续集，看上一篇，JavaScript版数据结构与算法——基础篇（一）

集合

集合是由一组无序且唯一的项组成。

无序意味着不能通过下标值进行访问，唯一意味着相同对象在集合中只存在一份

其实ES5中已经包含了Array类，ES6中已经包含了Set类，可直接使用

代码实现一个Set类

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
function Set() {
        this.item = {}
        Set.prototype.add = function (value) {
            if (this.has(value)) {
                return false
            }
            this.item[value] = value
            return true
        }
        Set.prototype.has = function (value) {
            return this.item.hasOwnProperty(value)
        }
        Set.prototype.remove = function (value) {
            if (!this.has(value)) {
                return false
            }
            delete this.item[value]
            return true
        }
        Set.prototype.clear = function () {
            this.item = {}
        }
        Set.prototype.size = function () {
            return Object.keys(this.item).length
        }
        Set.prototype.value = function () {
            return Object.keys(this.item)
        }
    }

我们可以对集合作如下的一些运算：

  • 交集：对于给定的两个集合，返回一个包含两个集合中 共有 元素的新集合。
  • 并集：对于给定的两个集合，返回一个包含两个集合中 所有 元素的新集合。
  • 差集：对于给定的两个集合，返回一个包含所有 存在于第一个集合且不存在于第二个集合 的元素的新集合。
  • 子集：验证一个给定集合是否是另一集合的子集。
    并集代码实现：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    Set.prototype.union = function (otherSet) {
        let unionSet = new Set()
        let value = this.value()
        for(let i = 0; i< value.length; i++){
            unionSet.add(value[i])
        }
        let v = otherSet.value()
        for(let i = 0; i< value.length; i++){
            unionSet.add(v[i])
        }
        return unionSet
    }
    交集代码实现：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    Set.prototype.intersection = function (otherSet) {
        let intersectionSet = new  Set()
        let value = this.value()
        for(let i = 0; i< value.length; i++){
            let it = value[i]
            if (otherSet.has(it)) {
                intersectionSet.add(it)
            }
        }
        return intersectionSet
    }
    差集代码实现：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    Set.prototype.difference = function (otherSet) {
        let differenceSet = new  Set()
        let value = this.value()
        for(let i = 0; i< value.length; i++){
            let it = value[i]
            if (!otherSet.has(it)) {
                differenceSet.add(it)
            }
        }
        return differenceSet
    }
    子集代码实现：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    Set.prototype.sub = function (otherSet) {
        let subSet = new  Set()
        let value = this.value()
        for(let i = 0; i< value.length; i++){
            let it = value[i]
            if (!otherSet.has(it)) {
                return false
            }
        }
        return true
    }

树

树是一种非线性的数据结构，以分层的方式存储数据。树被用来存储具有层级关系的数据，比如文件系统中的文件；树还被用来存储有序列表。

生活中常见的树结构：公司组织架构图、家族家谱

树和数组、链表、哈希表相比：

  1. 数组：
    • 根据下标值访问，效率高
    • 根据元素去查找对应的位置，效率很低。
  2. 链表：
    • 链表在插入和删除的效率相当高
    • 查找的效率很低，每次都需要从头部开始查找。
  3. 哈希表：
    • 插入、删除、查找效率都很高
    • 空间利用率不高；哈希表中的元素是无序的，不能按照固定的顺序来查找元素；不能快速的找到哈希表中的最大值\最小值这些特殊值。
  4. 树：
    • 每种数据结构都有特定的应用场景，不能说树结构比其他几种都要好。
    • 树综合了上面数据结构的优点（当然优点不足以超过其他数据结构，比如效率一般没有哈希表高）
    • 弥补了上面数据结构的一些缺点
    • 为了模拟某些应用场景，使用树结构会更加方便（1、树结构可以表示一对多的关系；2、来表示文件的目录结构。）

树的详细介绍看我之前的一篇文章：Javascript版数据结构与算法——二叉树

排序和搜索算法

大O复杂度表示法

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫「作渐进时间复杂度」（asymptotic time complexity），简称「时间复杂度」。

加法法则：总复杂度等于量级最大的那段代码的复杂度

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

排序算法

冒泡排序、选择排序、插入排序、归并排序、计数排序、基数排序、希尔排序、堆排序、桶排序

简单排序：冒泡排序、选择排序、插入排序

高级排序：希尔排序、快速排序

冒泡排序

比较所有相邻的两个项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序

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
class ArrList {
    constructor () {
     this.arr = []
    }
    insert(item) {
        this.arr.push(item)
    }
    toString(){
		return this.arr.join('-')
	}
    bubbleSort () {
         let len = this.arr.length
         
         for (let j = len - 1; j >= 0; j--) {
            // 内层循环每一轮会把最大（或者最小值）排到最右边，
            // 第二轮循环只需要操作除去最右边的剩下的值，所以外层循环逐渐减少。
             for (let i = 0; i < j; i++) {
                 if (this.arr[i] > this.arr[i + 1]) {
                     let temp = this.arr[i]
                     this.arr[i] = this.arr[i + 1]
                     this.arr[i + 1] = temp
                 }
             }
         }
    }
 }
 
 // 使用
 let list = new ArrList()
 
 // 添加数据
list.insert(22)
list.insert(222)
list.insert(2)
list.insert(12)
alert(list)
list.bubbleSort()
alert(list)
选择排序

找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推

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
class ArrList {
    constructor () {
     this.arr = []
    }
    insert(item) {
        this.arr.push(item)
    }
    toString(){
		return this.arr.join('-')
	}
    selectionSort () {
         let len = this.arr.length
         for(let j = 0;j< len - 1; j++){
             let min = j // 保存最小值的下标，初始值为0
             for(let  i = min + 1; i < len; i++){
                 if (this.arr[min] > this.arr[i]) {
                     min = i // 取出最小值
                 }
             }
             // 交换min和j位置的元素
             if (min !== j) {
                let temp = this.arr[min]
                this.arr[min] = this.arr[j]
                this.arr[j] = temp 
             }
              
         }
    }
 }
 
 // 使用
 let list = new ArrList()
 
 // 添加数据
list.insert(22)
list.insert(222)
list.insert(2)
list.insert(12)
alert(list)
list.selectionSort()
alert(list)
插入排序

核心：局部有序。假定第一项已经排序了。接着， 它和第二项进行比较——第二项是应该待在原位还是插到第一项之前呢?这样，头两项就已正确排序，接着和第三项比较(它是该插入到第一、第二还是第三的位置呢)，以此类推

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 ArrList {
    constructor () {
     this.arr = []
    }
    insert(item) {
        this.arr.push(item)
    }
    toString(){
		return this.arr.join('-')
	}
    insertSort () {
         let len = this.arr.length
         for(let i = 1; i < len; i++){ // 默认左边第一个是排好序的
             let temp = this.arr[i] // 从下标为1开始取元素和该元素左边的依次比较
             // 如果该元素比左边的小，则把左边元素依次向右移动一位，直到找到该元素比左边大的位置，在这个位置放入该元素，即完成依次排序
             let j = i
             while(this.arr[j - 1] > temp && j > 0){
                 this.arr[j] = this.arr[j - 1]
                 j--
             }
             this.arr[j] = temp
         }
         
    }
 }
 
 // 使用
 let list = new ArrList()
 
 // 添加数据
list.insert(22)
list.insert(222)
list.insert(2)
list.insert(12)
alert(list)
list.insertSort()
alert(list)

前面几种排序算法的时间复杂度都是O(N^2)

希尔排序

是插入排序的一种高效改进版，并且效率比插入排序更快。又称缩小增量排序

原理：把需要排序的数据按一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组。—来自百度百科：希尔排序

共三层循环嵌套：

  1. 最外层：不断改变增量
  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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
 class ArrList {
    constructor () {
     this.arr = []
    }
    insert(item) {
        this.arr.push(item)
    }
    toString(){
		return this.arr.join('-')
	}
    shellSort () {
         let len = this.arr.length
         // 初始化增量
         let gap = Math.floor(len / 2)
         // 循环操作（gap在逐渐减小）
            while(gap >= 1) {
                // 以gap为间隔进行分组，对分组进行插入排序
                for (let i = gap; i < len; i++) {
                    let temp = this.arr[i]
                    let j = i
                    while(this.arr[j - gap] > temp && j - gap > 1){
                        this.arr[j] = this.arr[j - gap]
                        j -= gap
                    }
                    this.arr[j] = temp
                }
                gap = Math.floor( gap / 2)
            }
         
    }
 }
 
 // 使用
 let list = new ArrList()
 // 添加数据
list.insert(22)
list.insert(222)
list.insert(2)
list.insert(12)
alert(list)
list.shellSort()
alert(list)

快速排序

排序过程：

  1. 选出一个基准值
  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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
 class ArrList {
    constructor () {
     this.arr = []
    }
    insert(item) {
        this.arr.push(item)
    }
    toString(){
		return this.arr.join('-')
	}
    quickSort (arrData = this.arr) {
        if(arrData.length <= 1) return arrData
        let pivotIndex = Math.floor(arrData.length / 2)
        let pivot = arrData.splice(pivotIndex, 1)[0] // 取出基准值
        let left = [] // 将数据中比基准值小的放入
        let right = [] // 将数组中比基准值大的放入
        for(let i = 0; i < arrData.length; i++ ){
            if(arrData[i] < pivot){
                left.push(arrData[i] )
            } else {
                right.push(arrData[i] )
            }
        }
		this.arr = this.quickSort(left).concat([pivot], this.quickSort(right))
        return this.arr
    }
 }
 
 // 使用
 let list = new ArrList()
 // 添加数据
list.insert(22)
list.insert(222)
list.insert(2)
list.insert(12)
alert(list)
list.quickSort()
alert(list)

以上两篇文章就是个人认为前端工程师应该了解和学习的一些基本算法和数据结构

感谢您的阅读