使用Redis实现令牌桶算法
324 2023-04-03 03:53:45
其他章节请看:
前端学习 数据结构与算法 快速入门 系列
本篇,我们将一起学习最常用的搜索和排序算法,如冒泡排序、选择排序、插入排序、归并排序、快速排序,以及二分搜索、插值搜索。
同时我们得理解,首先得排好序,才能更好的搜索需要的信息。
https://visualgo.net/
- 数据结构和算法动态可视化。比如有本文介绍的排序算法的动画版本。
冒泡排序 是所有排序算法中最简单的一种。
冒泡排序算法的原理:比较相邻的元素,如果左侧比右侧元素大(或小),则交换他们。元素向上移至正确的位置,就好像气泡升至表面。
笔者实现如下:
function bubbleSort(arr) { // 比较轮数,每轮都会将一个值冒泡到正确的位置 arr.forEach(() => { // {1} arr.forEach((item, index) => { // 出界则为 false,不会交换 if (arr[index] > arr[index + 1]) { [arr[index], arr[index + 1]] = [arr[index + 1], arr[index]] } }) }) return arr}// [ 1, 2, 3, 4 ]console.log(bubbleSort([4, 3, 2, 1]))
这个实现可以再优化两点:
即使我们对其进行改进,还是不推荐此算法。它的时间复杂度是O(n²)
选择排序算法大致思路:找到最小(大)值并放在第一位,接着找到第二小的值并将其放在第二位,依此类推
笔者实现如下:
function selectionSort(arr) { let { length } = arr // 例如有三个元素,那么只需遍历 2 次就能确定第一位和第二位的值,第三个值也就在正确的位置上了 for (let i = 0; i < length - 1; i++) { // 默认第一是最小值 let min = i for (let j = i + 1; j < length; j++) { // 如果最小值不是最小值,更新最小值索引 if (arr[min] > arr[j]) { min = j } } // 最小值不是最小值,则交互值 if (min !== i) { [arr[i], arr[min]] = [arr[min], arr[i]] } } return arr}// [ 1, 2, 3, 4 ]console.log(selectionSort([4, 3, 2, 1]));
时间复杂度和冒泡排序一样,也是 O(n²)。
插入排序:是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入,直到整个序列排为有序
笔者实现如下:
function insertionSort(arr) { let { length } = arr // 比如三个元素,第一个默认已经排好序了,只要给剩余两个元素排序即可 for (let i = 1; i < length; i++) { let endIndex = i while (endIndex) { // endIndex 的元素如果不比前一个值要小,说明已经在正确位置,无需更换 if (arr[endIndex - 1] <= arr[endIndex]) { break } // 更换值 [arr[endIndex - 1], arr[endIndex]] = [arr[endIndex], arr[endIndex - 1]] --endIndex } } return arr}// [ 1, 2, 3, 4 ]console.log(insertionSort([4, 3, 2, 1]))
时间复杂度O(N^(1-2))。
Tip:最好的情况(如待排数组有序),一共需要比较 N - 1 次,时间复杂度为 O(N);最坏的情况(如待排数组是逆序),需要比较的总次数为 1+2+3+...+(N-1),时间复杂度为 O(N²);排序小型数组,此算法比选择选择和冒泡排序的性能要好。
归并排序 是一个可以实际使用的排序算法。性能比前面介绍的三种排序算法要好,时间复杂度为 O(n log n)。
Tip:对于 javascript 中 Array.prototype.sort()
方法,firefox 使用的就是 并归排序
,而 Chrome(V8 引擎)使用的是 快速排序
的变体。
归并排序是一种分而治之算法。比如要将 [3, 1, 4, 2, 5]
排序,可以将其分为两个数组(left = [3, 1]
; right = [4, 2, 5]
),分别对两个数组排序,然后再将两个数组合并。
笔者实现如下:
function mergeSort(arr) { let { length } = arr // 一个元素,直接返回 if (length === 1) { return arr } // 例如三个元素,middleIndex 为 1 const middleIndex = Math.floor(length / 2) const left = arr.slice(0, middleIndex) const right = arr.slice(middleIndex) return merge(mergeSort(left), mergeSort(right))}// 将 left 数组和 right 数组合并// left 和 right 都已经是拍好序的数组// 例如 left = [1, 3] right = [2, 4, 5]function merge(left, right) { let leftIndex = 0 let rightIndex = 0 const { length: leftLen } = left const { length: rightLen } = right // 存储结果 const result = [] while ((leftIndex < leftLen) && (rightIndex < rightLen)) { if (left[leftIndex] <= right[rightIndex]) { result.push(left[leftIndex++]) } else { result.push(right[rightIndex++]) } } // 此时 result = [1, 2, 3] if (leftIndex === leftLen) { // 将 right 剩余的 4、5 放入 result result.push(...right.slice(rightIndex)) } // 如果 right 先一步遍历完毕,则将 left 剩余元素放入 result if (rightIndex === rightLen) { result.push(...left.slice(leftIndex)) } return result}console.log(mergeSort([3, 1, 4, 2, 5]))// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]// console.log(mergeSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]))
快速排序 也是比较常见的排序算法。时间复杂度为 O(n log n)。和并归算法一样,快速排序也使用分而治之的方法,但不需要合并。
排序流程如下:
前 2 步叫做划分操作。我们通过一个小示例来说明一下:
// 划分function partition(array) { // 随便选取一个值作为分界值 let mainValue = array[0] let leftIndex = 0 let rightIndex = array.length - 1 while (leftIndex <= rightIndex) { while (array[leftIndex] <= mainValue) { leftIndex++ } while (array[rightIndex] >= mainValue) { rightIndex-- } if (leftIndex <= rightIndex) { [array[leftIndex], array[rightIndex]] = [array[rightIndex], array[leftIndex]] } } return leftIndex}
测试:
let arr = [3, 5, 1, 6, 4, 7, 2]let middleIndex = partition(arr)// 3console.log(middleIndex)// [3, 2, 1, 6, 4, 7, 5]console.log(arr)// 左侧数组:[ 3, 2, 1 ]console.log(arr.slice(0, middleIndex))// 右侧数组:[ 6, 4, 7, 5 ]console.log(arr.slice(middleIndex))
通过 partition() 方法,会返回一个索引,并会更新原数组(arr),得到的左侧数组都小于等于分界值,右侧数组都大于等于分界值。
接着对左侧数组和后侧数组在进行划分操作,最后,数组就会完成排序。
注:此方法有一个问题,比如 arr = [13, 12, 11]
,返回的 leftIndex 为 3,明显不对(arr 的 leftIndex 只会为 0、1或2)。修复方法很简单,将等号去掉即可:
+ while (array[leftIndex] < mainValue) {- while (array[leftIndex] <= mainValue) { leftIndex++ }+ while (array[rightIndex] > mainValue) {- while (array[rightIndex] >= mainValue) { rightIndex-- }
// 在上面的 partition() 方法的基础上进行稍微调整function partition(array, leftIndex, rightIndex) { let mainValue = array[Math.floor((leftIndex + rightIndex) / 2)] while (leftIndex <= rightIndex) { // 注:不能包括等于,否则会出界。 // 例如 let arr = [3, 2, 1]; partition(arr, 0, arr.length - 1) 返回 3 while (array[leftIndex] < mainValue) { leftIndex++ } while (array[rightIndex] > mainValue) { rightIndex-- } if (leftIndex <= rightIndex) { [array[leftIndex], array[rightIndex]] = [array[rightIndex], array[leftIndex]] rightIndex-- leftIndex++ } } return leftIndex}function quickSort(arr, left = 0, right = arr.length - 1) { // 1 个值 if ((right - left) <= 0) { return } // 进行划分操作 const partitionIndex = partition(arr, left, right) // partitionIndex 需要减 1,否则 right 值没变,会造成无限循环 quickSort(arr, left, partitionIndex - 1) quickSort(arr, partitionIndex, right) return arr}// [ 1, 2, 3 ]console.log(quickSort([3, 2, 1]))// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]console.log(quickSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]))
注:选择分界值(称主元)有几种方式,最简单是选择数组的第一个值,但研究表明,这会导致该算法最差表现,另一种是随机选择或者选择中间值。
算法我们暂且先学习这几种,我们接着看搜索。
顺序(或线性)搜索是最基本的搜索算法。也是最低效的一种搜索算法。
它的机制是:将数据结构的每一项和我们要找的元素比较。
二分搜索 要求被搜索的数据结构已排序。算法的步骤如下:
// 自定义排序// 你也可以使用其他排序算法function customSort(arr) { return [...arr.sort((a, b) => a - b)]}// 二分搜索function binarySearch(array, v) { // 首先得将数组排序 let sortedArray = customSort(array) let start = 0; let end = sortedArray.length - 1; let middle // 可在加上一个条件来提交算法性能:要搜索的值在 [array[start], array[end]] 之间,否则直接返回 -1 while (start <= end) { middle = Math.floor((start + end) / 2) if (sortedArray[middle] === v) { return middle } else if (v < sortedArray[middle]) { end = middle - 1 } else { start = middle + 1 } } return -1;}console.log(binarySearch([1], 1)) // 0console.log(binarySearch([], 1)) // -1// 排序后:[2, 4, 6, 7, 8, 9, 111]console.log(binarySearch([2, 8, 9, 7, 6, 4, 111], 9)) // 5
注:必须先对数组进行排序,否则此算法有时就会失效。例如 binarySearch([2, 8, 9, 7, 6, 4, 111], 9)
就会返回 -1。
插值搜索(或称 插值查找、或称内插搜索)是改良版的 二分搜索
。二分搜索总是检查 middle 位置上的值,而插值搜索将查找点的选择改进为按公式查找,提高了查找效率。
同样要求被搜索的数据结构已排序。算法的步骤与二分搜索类似:
笔者实现如下:
// 根据一定规则返回 position// 规则由你决定function getPosition(arr, start, end, searchVal) { // 占比 // 注:需要处理 arr[end] 等于 arr[start] 的情况 // 否则 `0 + Math.floor(0*Infinity)` => NaN let percentage = !Object.is(arr[end], arr[start]) ? (searchVal - arr[start]) / (arr[end] - arr[start]) : 0 return start + Math.floor((end - start) * percentage)}// 插值搜索function interpolationSearch(array, v) { // 首先得将数组排序 let sortedArray = customSort(array) let start = 0; let end = sortedArray.length - 1; let position while (start <= end && (v >= array[start]) && (v <= array[end])) { // 使用公式选中一个索引进行比较 position = getPosition(array, start, end, v) if (sortedArray[position] === v) { return position } else if (v < sortedArray[position]) { end = position - 1 } else { start = position + 1 } } return -1;}console.log(interpolationSearch([1], 1)) // 0console.log(binarySearch([], 1)) // -1// 排序后:[2, 4, 6, 7, 8, 9, 111]console.log(interpolationSearch([2, 8, 9, 7, 6, 4, 111], 9)) // 5
Fisher-Yates 随机算法由 Fisher 和 Yates 创造。原理直接看代码更加直观:
// 洗牌:迭代数组,从最后一位开始并将当前元素和一个随机位置的值进行交换function shuffle(arr) { for (let i = arr.length - 1; i > 0; i--) { // 取得随机位置:[0, i] let randomPosition = Math.floor(Math.random() * (i + 1)); // 将当前元素和随机位置的值进行交换 [arr[randomPosition], arr[i]] = [arr[i], arr[randomPosition]] } return arr}console.log(shuffle(['a', 'b', 'c', 'd', 'e']))// 三次洗牌的输出:// [ 'e', 'a', 'c', 'b', 'd' ]// [ 'a', 'c', 'd', 'e', 'b' ]// [ 'd', 'e', 'a', 'b', 'c' ]
其他章节请看:
前端学习 数据结构与算法 快速入门 系列