10.Javascript检索算法

Javascript数据结构与算法 评论

10 检索算法

作为最基本的计算机编程任务，数据检索已经被研究了很多年。本章只介绍数据检索的一个方面：如何在列表中查找特定的值

10.1 工具函数

为了方便测试我们的程序，我们先定义一个工具函数，以减少我们的重复代码。这个工具函数其实跟上一节是一样的。

程序

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 cArray {
  constructor(numElements) {
    this.dataStore = new Array(numElements)
    this.init()
  }
  // 初始化数组
  init() {
    for (let i = 0; i < this.dataStore.length; i++) {
      this.dataStore[i] = i
    }
  }
  // 把数组设置成随机数组
  setData() {
    for (let i = 0; i < this.dataStore.length; i++) {
      this.dataStore[i] = Math.floor(
        Math.random() * (this.dataStore.length + 1)
      )
    }
  }
  // 清空数组
  clear() {
    for (let i = 0; i < this.dataStore.length; i++) {
      this.dataStore[i] = 0
    }
  }
  // 在数组顶部插入元素
  insert(ele) {
    this.dataStore.push(ele)
  }
  // 将数组转成字符串
  toString() {
    let result = ''
    for (let i = 0; i < this.dataStore.length; i++) {
      result += this.dataStore[i] + ' '
      if (i > 0 && i % 10 == 9) {
        result += '\n'
      }
    }
    return result
  }
  // 交换数组中的元素
  swap(index1, index2) {
    let temp = this.dataStore[index1]
    this.dataStore[index1] = this.dataStore[index2]
    this.dataStore[index2] = temp
  }
}

10.2 顺序查找

对于查找数据来说，最简单的方法就是从列表的第一个元素开始对列表元素逐个进行判断，直到找到了想要的结果，或者直到列表结尾也没有找到。这种方法称为顺序查找，有时也被称为线性查找 。

代码如下：

1
2
3
4
5
6
7
8
9
seqSearch(data) {
    let list = this.dataStore
    for (let i = 0; i < list.length; i++) {
      if (list[i] === data) {
        return i
      }
    }
    return false
  }

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 生成工具函数对象
let cArr = new cArray(100)
// 设置随机数据
cArr.setData()

cArr.seqSearch(50)
console.log(cArr.toString())
console.log('cArr.seqSearch(50):', cArr.seqSearch(50))
// 打印结果
26 73 9 4 64 39 25 76 19 57 
9 31 18 0 72 14 60 8 1 96 
23 58 10 94 61 15 29 48 97 87 
97 51 51 47 30 51 10 6 46 76 
3 8 87 3 98 22 75 92 61 80 
55 51 61 27 40 86 9 85 54 69 
40 8 98 63 32 28 11 42 37 44 
91 34 72 3 44 9 12 80 61 63 
2 25 80 11 81 77 37 11 96 17 
37 92 71 6 45 7 74 75 76 94 
cArr.seqSearch(50): false

这里的随机数组中没有50 所以返回false。我们再多运行几次，比如如下，我们就查找到50了。

1
2
3
4
5
6
7
8
9
10
11
98 95 50 75 86 0 13 9 53 43 
10 92 62 56 4 58 4 69 71 43 
91 29 22 30 69 51 53 42 15 1 
76 48 54 100 65 83 20 64 95 93 
98 3 87 83 99 3 60 66 55 63 
53 3 57 27 41 89 50 97 7 5 
68 76 53 55 85 41 95 7 32 70 
88 41 24 67 21 69 10 22 68 55 
81 26 68 14 4 82 3 97 11 66 
37 34 12 61 57 78 95 92 65 8 
cArr.seqSearch(50): 2

10.3 查找最大值，最小值

这个简直太简单，我就不多讲解了，程序如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 查找最小值
findMin() {
  let list = this.dataStore
  let min = list[0]
  for (let i = 0; i < list.length; i++) {
    if (list[i] < min) {
      min = list[i]
    }
  }
  return min
}
// 查找最大值
findMax() {
  let list = this.dataStore
  let max = list[0]
  for (let i = 0; i < list.length; i++) {
    if (list[i] > max) {
      max = list[i]
    }
  }
  return max
}

测试：

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
// 生成工具函数对象
let cArr = new cArray(100)
// 设置随机数据
cArr.setData()

cArr.seqSearch(50)
console.log(cArr.toString())
console.log('cArr.seqSearch(50):', cArr.seqSearch(50))
console.log('最小值:', cArr.findMin())
console.log('最大值:', cArr.findMax())

// 打印结果
76 39 19 99 11 23 41 78 95 46 
29 84 13 76 98 78 71 4 74 80 
70 25 89 72 74 92 10 33 31 16 
93 60 92 8 12 73 71 91 43 60 
24 32 95 74 52 37 5 7 26 26 
28 22 80 51 95 98 76 83 14 73 
29 51 80 20 38 82 70 58 65 78 
65 55 47 98 7 88 8 67 69 10 
27 12 11 84 59 25 12 51 30 59 
94 68 56 31 55 29 27 33 21 8 
cArr.seqSearch(50): false
最小值: 4
最大值: 99

10.4 使用自组织数据

对于未排序的数据集来说，当被查找的数据位于数据集的起始位置时，查找是最快、最成功的。通过将成功找到的元素置于数据集的起始位置，可以保证在以后的操作中该元素能被更快地查找到。

对数据的查找遵循“80-20 原则” 。“80-20 原则”是指对某一数据集执行的 80% 的查找操作都是对其中 20% 的数据元素进行查找。自组织的方式最终会把这 20% 的数据置于数据集的起始位置，这样便可以通过一个简单的顺序查找快速找到它们 。每次查找数据都会向前移动

这个也很简单，程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 自组织顺序查找
selfSeqSearch(data) {
  let list = this.dataStore
  let secondNum = Math.floor(list.length * 0.2)
  for (let i = 0; i < list.length; i++) {
    if (list[i] === data) {
      if (i > secondNum) {
        this.swap(i, i - secondNum)
      }
      return i
    }
  }
  return false
}

10.5 二分查找

如果你要查找的数据是有序的，二分查找算法比顺序查找算法更高效 。这个算法的规则如下：

  1. 将数组的第一个位置设置为下边界 (0)
  2. 将数组最后一个元素所在的位置设置为上边界（数组的长度减 1）
  3. 若下边界等于或小于上边界，则做如下操作：
    • 将中点设置为（上边界加上下边界）除以 2
    • 如果中点的元素小于查询的值，则将下边界设置为中点元素所在下标加 1
    • 如果中点的元素大于查询的值，则将上边界设置为中点元素所在下标减 1
    • 否则中点元素即为要查找的数据，可以进行返回

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 二分查找
binSearch(data) {
  let list = this.dataStore
  let upperBound = list.length - 1
  let lowerBound = 0
  while (lowerBound <= upperBound) {
    let mid = Math.floor((upperBound + lowerBound) / 2)
    if (list[mid] < data) {
      lowerBound = mid + 1
    } else if (list[mid] > data) {
      upperBound = mid - 1
    } else {
      return mid
    }
  }
  return -1
}

因为二分查找的前提是有序数组，因此我们还需要实现一个排序方法，对数据进行排序。这里我们选择快速排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 快速排序
qSort() {
  this.dataStore = this.qSortArr(this.dataStore)
}
qSortArr(list) {
  if (list.length == 0) {
    return []
  }
  let lesser = []
  let greater = []
  let pivot = list[0]
  for (let i = 1; i < list.length; i++) {
    if (list[i] < pivot) {
      lesser.push(list[i])
    } else {
      greater.push(list[i])
    }
  }
  return this.qSortArr(lesser).concat(pivot, this.qSortArr(greater))
}

测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 生成工具函数对象
let cArr = new cArray(100)
// 设置随机数据
cArr.setData()
cArr.qSort()
console.log(cArr.toString())
console.log('cArr.binSearch(50):', cArr.binSearch(50))

// 打印结果
0 0 1 1 2 4 4 5 8 8 
11 12 12 13 14 14 15 16 16 17 
17 21 22 24 25 26 26 26 27 28 
29 31 31 33 33 35 35 37 38 39 
40 42 42 42 43 44 45 48 50 50 
50 50 51 51 55 56 57 58 61 61 
62 62 62 66 66 67 71 71 73 73 
73 74 75 76 78 79 80 80 80 80 
80 81 82 82 84 85 86 86 86 88 
89 91 94 96 97 97 98 99 99 99 
cArr.binSearch(50): 49

关于检索的内容还有查找数字的重复次数，查找字符串。不过这些都是很简单的内容，我这里就不一一实现了。这一章还是蛮简单的。

完整代码如下：

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
class cArray {
  constructor(numElements) {
    this.dataStore = new Array(numElements)
    this.init()
  }
  // 初始化数组
  init() {
    for (let i = 0; i < this.dataStore.length; i++) {
      this.dataStore[i] = i
    }
  }
  // 把数组设置成随机数组
  setData() {
    for (let i = 0; i < this.dataStore.length; i++) {
      this.dataStore[i] = Math.floor(
        Math.random() * (this.dataStore.length + 1)
      )
    }
  }
  // 清空数组
  clear() {
    for (let i = 0; i < this.dataStore.length; i++) {
      this.dataStore[i] = 0
    }
  }
  // 在数组顶部插入元素
  insert(ele) {
    this.dataStore.push(ele)
  }
  // 将数组转成字符串
  toString() {
    let result = ''
    for (let i = 0; i < this.dataStore.length; i++) {
      result += this.dataStore[i] + ' '
      if (i > 0 && i % 10 == 9) {
        result += '\n'
      }
    }
    return result
  }
  // 交换数组中的元素
  swap(index1, index2) {
    let temp = this.dataStore[index1]
    this.dataStore[index1] = this.dataStore[index2]
    this.dataStore[index2] = temp
  }
  // 顺序查找
  seqSearch(data) {
    let list = this.dataStore
    for (let i = 0; i < list.length; i++) {
      if (list[i] === data) {
        return i
      }
    }
    return false
  }
  // 查找最小值
  findMin() {
    let list = this.dataStore
    let min = list[0]
    for (let i = 0; i < list.length; i++) {
      if (list[i] < min) {
        min = list[i]
      }
    }
    return min
  }
  // 查找最大值
  findMax() {
    let list = this.dataStore
    let max = list[0]
    for (let i = 0; i < list.length; i++) {
      if (list[i] > max) {
        max = list[i]
      }
    }
    return max
  }
  // 自组织顺序查找
  selfSeqSearch(data) {
    let list = this.dataStore
    let secondNum = Math.floor(list.length * 0.2)
    for (let i = 0; i < list.length; i++) {
      if (list[i] === data) {
        if (i > secondNum) {
          this.swap(i, i - secondNum)
        }
        return i
      }
    }
    return false
  }
  // 二分查找
  binSearch(data) {
    let list = this.dataStore
    let upperBound = list.length - 1
    let lowerBound = 0
    while (lowerBound <= upperBound) {
      let mid = Math.floor((upperBound + lowerBound) / 2)
      if (list[mid] < data) {
        lowerBound = mid + 1
      } else if (list[mid] > data) {
        upperBound = mid - 1
      } else {
        return mid
      }
    }
    return -1
  }
  // 快速排序
  qSort() {
    this.dataStore = this.qSortArr(this.dataStore)
  }
  qSortArr(list) {
    if (list.length == 0) {
      return []
    }
    let lesser = []
    let greater = []
    let pivot = list[0]
    for (let i = 1; i < list.length; i++) {
      if (list[i] < pivot) {
        lesser.push(list[i])
      } else {
        greater.push(list[i])
      }
    }
    return this.qSortArr(lesser).concat(pivot, this.qSortArr(greater))
  }
}
// 生成工具函数对象
let cArr = new cArray(100)
// 设置随机数据
cArr.setData()
cArr.qSort()
console.log(cArr.toString())
console.log('cArr.binSearch(50):', cArr.binSearch(50))

锅锅复锅锅

中国贫困人口，特别需要关爱人群，微信guo330504。