TypeScript实现八大排序与搜索算法
2020-08-17
加入收藏
作者：神奇的程序员K
转发链接：https://mp.weixin.qq.com/s/3B8dZRfbIuktSBeArXlmcQ
前言
我们在页面上渲染数据时，通常会根据特定规则来对数据进行一个排序，然后再将其渲染到页面展示给用户。哪么对数据进行排序有很多种方式，哪一种效率高？哪一种稳定性好？那一种占用内存小？本文将详解经典的八大排序算法以及三种搜索算法，并用TypeScript将其实现，欢迎各位对上述问题迷惑的开发者阅读本文。
排序算法
我们先来学习下排序算法，八大排序包括：冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、同排序、基数排序其中有几个排序我在之前的文章中已经讲解了其图解实现，本文将注重讲解其实现，另外几篇文章链接如下:
- 排序算法:冒泡排序
- 排序算法:选择排序
- 排序算法:插入排序
- 排序算法:归并排序
- 排序算法:快速排序
冒泡排序
冒泡排序是排序算法中最简单、最好理解的一个排序算法，但是从运行时间的角度来看，它的效率是最低的。本文中所有函数实现的代码地址: Sort.ts
实现思路
它会比较相邻的两个项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序。为了让排序算法更灵活，不仅仅只是用于数字的排序，因此本文中讲解的排序算法都会有一个比对函数作为参数传进来，用于定义两个值的比较方式。
- 声明一个函数其接受两个参数：待排序数组 & 比对函数
- 第一层循环i：从待排序数组的0号元素开始遍历数组，遍历到最后一位，用于控制数组需要经过多少轮排序
- 第二层循环j：从数组的0号元素开始遍历，遍历至数组的倒数第二位元素再减去第一层循环i。
- 比较大小，在第二层循环中，将当前遍历到的元素和其下一个元素比较大小，如果 j > j + 1就交换两个元素的位置。
我们通过一个例子来描述下上述思路，如下图所示，将一个乱序数组执行冒泡排序后，将其从小到大排列。
实现代码
为了让函数便于维护，我们新建一个类名为Sort，本文中实现的所有函数都为这个类内部的方法。
- 为了函数的可扩展性，我们需要实现一个默认的比对函数，此比对函数作用于本文中的所有排序方法
export function defaultCompare<T>(a: T, b: T): number {
if (a === b) {
return Compare.EQUALS;
} else if (a > b) {
return Compare.BIGGER_THAN;
} else {
return Compare.LESS_THAN;
}
}
// 枚举类：定义比对返回值
export enum Compare {
LESS_THAN = -1,
BIGGER_THAN = 1,
EQUALS = 0
}
- 在类中声明需要的变量，并在构造器中声明需要传的参数类型，此处适用于本文实现的所有函数
/**
* 排序算法
* @param array 需要进行排序的数组
* @param compareFn 比对函数
*/
constructor(private array: T[] = [], private compareFn: ICompareFunction<T> = defaultCompare) {}
- 实现冒泡排序
// 冒泡排序
bubbleSort(): void {
// 获取数组长度
const { length } = this.array;
for (let i = 0; i < length; i++) {
// 从数组的0号元素遍历到数组的倒数第2号元素，然后减去外层已经遍历的轮数
for (let j = 0; j < length - 1 - i; j++) {
// 如果j > j + 1位置的元素就交换他们两个元素的位置
if (this.compareFn(this.array[j], this.array[j + 1]) === Compare.BIGGER_THAN) {
this.swap(this.array, j, j + 1);
}
}
}
}
编写测试代码
我们将上图中的例子放在代码中，测试下执行结果是否正确。
const array = [12, 6, 3, 4, 1, 7];
const sort = new Sort(array);
sort.bubbleSort();
console.log(array.join());
选择排序
选择排序是一种原址比较排序算法，它的大致思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值将其放在第二位，依次类推。
实现思路
- 声明一个辅助变量:indexMin用于存储数组中的最小值
- 第一层循环i，从数组的0号元素遍历到数组的倒数第二位。indexMin默认赋值为i，用于控制轮数
- 第二层循环j，从数组的i号元素遍历到数组的末尾，用于寻找数组的最小值，如果indexMin位置的元素大于j号位置的元素就覆盖indxMin的值为j
- 在第二层循环结束后，比较i与indexMin是否相等，如果不相等就交换两个元素的位置。
下图中的示例描述了上述思路
实现代码
// 选择排序
selectionSort(): void {
const { length } = this.array;
// 声明一个变量用于存储最小元素的位置
let indexMin = 0;
for (let i = 0; i < length; i++) {
// 初始值为外层循环当前遍历到的位置i
indexMin = i;
for (let j = i; j < length; j++) {
// 如果当前遍历到元素小于indexMin位置的元素，就将当前遍历到的位置j赋值给indexMin
if (this.compareFn(this.array[indexMin], this.array[j]) === Compare.BIGGER_THAN) {
indexMin = j;
}
}
if (i !== indexMin) {
this.swap(this.array, i, indexMin);
}
}
}
编写测试代码
我们将图中的示例，放在代码中，测试排序函数是否都正确执行。
const array = [12, 6, 3, 4, 1, 7];
const sort = new Sort(array);
// const result = sort.radixSort(array);
// console.log(result.join());
sort.selectionSort();
console.log(array.join());
插入排序
插入排序会将数组分为已排序区域和未排序区域，将未排序区域的数组项和已排序区域的数组进行大小比较，确立要插入的位置，然后将其插入到对应的位置。
实现思路
- 第一层循环i：从数组的1号元素开始，遍历到数组末尾，因为我们会先假设0号元素已经排好序，所以从1号元素开始。
- 用一个临时变量temp存储当前i号位置的元素，用一个变量j存储i
- while循环: j > 0且j - 1位置的元素大于temp，就把j位置的值设置为j - 1 位置的值，最后j--，继续下一轮遍历。
- while循环结束后，将temp放到正确的位置array[ j ]
如下图所示，我们通过一个例子描述了上述插入排序的过程
实现代码
接下来我们将上述思路转换为代码。
// 插入排序
insertionSort(array: T[] = this.array): void {
const { length } = array;
let temp;
// 假设0号元素已经排好序，从1号元素开始遍历数组
for (let i = 1; i < length; i++) {
// 声明辅助变量存储当前i的位置以及其对应的值
let j = i;
temp = array[i];
// j大于0且j-1位置的元素大于i号位置的元素就把j-1处的值移动到j处，最后j--
while (j > 0 && this.compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) {
array[j] = array[j - 1];
j--;
}
// 将temp放到正确的位置
array[j] = temp;
}
}
编写测试代码
我们将图中的例子放在代码里，执行下查看排序函数是否正常运行。
const array = [12, 6, 3, 4, 1, 7];
const sort = new Sort(array);
sort.insertionSort(array);
console.log(array.join());
归并排序
归并排序是一个可以实际使用的排序算法，在JAVAScript中Array类定义了一个Sort函数，用以排序JavaScript数组。ECMScript没有定义用哪个排序算法，所以浏览器厂商可以自己去实现算法。谷歌浏览器的V8引擎使用快速排序实现，火狐浏览器使用归并排序实现。
实现思路
归并排序是一个分而治之算法，就是将原始数组切分成比较小的数组，直到每个小数组只有一个位置，接着将小数组归并成比较大的数组，直到最后只有一个排序完毕的大数组。由于是分治法，归并排序也是递归的。我们要将算法分为两个函数：一个用于将函数分割成小数组，一个用于将小数组合并成大数组。我们先来看看主函数，将数组分割成小数组。
- 递归终止条件：由于是递归，所以我们需要先设立递归终止条件，当数组的长度大于1时就进行归并排序。
- 获取数组的中间值: 我们通过数组的中间值来切割数组，将其分成左、右两部分。对左右两部分继续执行分割
- 合并数组: 我们将数组分割完后，对小数组进行排序，然后将其合并成大数组并返回。
接下来，我们再来看下合并函数的实现
- 合并函数接收两个参数：左、右数组
- 声明三个辅助变量: i, j, result，分别表示左、右数组的指针以及存储合并后的数组
- 如果i < left.length && j < right.length，代表指针数组尚未排序完，因此执行下述逻辑
- 如果lef[i] < right[j]，就往result中放left[i]的值随后i++，否则就放right[j]的值随后j++
- 最后，将left或right数组的剩余项添加进result中
下图用一个例子描述了上述归并排序的过程
实现代码
接下来，我们将上述思路转换为代码。
// 归并排序
mergeSort(array: T[] = this.array): T[] {
if (array.length > 1) {
const { length } = array;
// 获取中间值
const middle = Math.floor(length / 2);
// 递归填充左右数组
const left = this.mergeSort(array.slice(0, middle));
const right = this.mergeSort(array.slice(middle, length));
// 合并左右数组
array = this.merge(left, right);
}
return array;
}
private merge(left: T[], right: T[]) {
let i = 0;
let j = 0;
const result: T[] = [];
while (i < left.length && j < right.length) {
// 如果left[i] < right[j]将left[i]加进result中，随后i自增，否则把right[j]加进result中，随后j自增
result.push(this.compareFn(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);
}
// 将left或right数组的剩余项添加进result中
return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}
编写测试代码
我们将上图中的例子放到代码中执行用以验证我们的函数是否正确执行
const array = [12, 6, 3, 4, 1, 7];
const sort = new Sort(array);
const result = sort.mergeSort();
console.log(result.join());
快速排序
快速排序与归并排序一样都是可用作实际应用的算法，它也是使用分而治之的方法，将原始数组分为较小的数组，但它没有像归并排序那样将他们分割开。
实现思路
我们需要三个函数：主函数、排序函数、切分函数。
- 主函数（quickSort），调用排序函数，返回排序函数最终排好的数组。
- 排序函数（quick），接收3个参数: 待排序数组（array）、数组的左边界（left）、数组的右边界（right）
- 声明一个辅助变量index，用于存储分割子数组的的位置。
- 确立递归终止条件：array < 1 ，如果array.length > 1，就执行下述操作：
执行划分函数，计算划分点，将得到的值赋值给index；
如果left > index - 1，代表子数组中存在较小值的元素，从数组的left边界到index-1边界递归执行排序函数；
如果index < right，代表子数组存在较大值的元素，从数组的index到right边界递归执行排序函数；
- 划分函数（partition），与排序函数一样，它也接收3个参数。
- 从数组中选择一个主元pivot，选择数组的中间值
- 声明两个指针：i, j，分别指向左边数组的第一个值和右边数组的第一个值。
- 如果i <= j，则代表left指针和right指针没有相互交错，则执行下述划分操作：
移动left指针直至找到一个比主元大的元素，即array[i] > pivot；
移动right指针直至找到一个比主元小的元素，即array[j] < pivot；
当左指针指向的元素比主元大且右指针指向的元素比主元小，并且左指针索引没有右指针索引大时就交换i号和j号元素的位置，随后移动两个指针；
最后，划分结束，返回i的值；
实现代码
接下来我们将上述思路转换为代码:
/**
*
* @param array 待排序数组
* @param left 左边界
* @param right 右边界
* @private
*/
private quick(array: T[], left: number, right: number) {
// 该变量用于将子数组分离为较小值数组和较大值数组
let index;
if (array.length > 1) {
// 对给定子数组执行划分操作，得到正确的index
index = this.partition(array, left, right);
// 如果子数组存在较小值的元素，则对该数组重复这个过程
if (left < index - 1) {
this.quick(array, left, index - 1);
}
// 如果子数组存在较大值的元素，也对该数组重复这个过程
if (index < right) {
this.quick(array, index, right);
}
}
return array;
}
// 划分函数
private partition(array: T[], left: number, right: number): number {
// 从数组中选择一个值做主元，此处选择数组的中间值
const pivot = array[Math.floor((right + left) / 2)];
// 创建数组引用，分别指向左边数组的第一个值和右边数组的第一个值
let i = left;
let j = right;
// left指针和right指针没有相互交错，就执行划分操作
while (i <= j) {
// 移动left指针直至找到一个比主元大的元素
while (this.compareFn(array[i], pivot) === Compare.LESS_THAN) {
i++;
}
// 移动right指针直至找到一个比主元小的元素
while (this.compareFn(array[j], pivot) === Compare.BIGGER_THAN) {
j--;
}
// 当左指针指向的元素比主元大且右指针指向的元素比主元小，并且左指针索引没有右指针索引大时就交换i和j号元素的位置，随后移动两个指针
if (i <= j) {
this.swap(array, i, j);
i++;
j--;
}
}
// 划分结束，返回左指针索引
return i;
}
编写测试代码
我们通过一个例子，来测试下上述代码是否都正确执行。
const array = [12, 6, 3, 4, 1, 7];
const sort = new Sort(array);
const result = sort.quickSort();
console.log(result.join());
计数排序
计数排序是一个分布式排序，它是用来排序整数的优秀算法。分布式排序使用已组织好的辅助数据结构，然后进行合并，得到排好序的数组。计数排序使用一个用来存储每个元素在原始数组中出现次数的临时数组。在所有元素都计数完成后，临时数组已排好序并可迭代以构建排序后的结果数组。
实现思路
- 找到要排序数组的最大值
- 以上一步找到的最大值+1为长度创建一个计数数组
- 遍历要排序的数组，以当前遍历的元素为索引，寻找计数数组中对应的位置将其初始化为0，如果此处位置有相同元素的话就自增
- 遍历计数数组，判断当前遍历到的元素是否大于0，如果大于0就取当前遍历到的索引，替换待排序数组中的元素
接下来我们通过一个例子来讲解下上述过程，如下图所示：
实现代码
接下来我们将上述思路转换为代码
countingSort(array: number[]): number[] {
// 待排序数组为空或只有一个元素则不用排序
if (array.length < 2) {
return array;
}
// 找到待排序数组中的最大值
const maxValue = this.findMaxValue(array);
// 创建计数数组，数组长度为待排序数组的最大值+1
const counts = new Array(maxValue + 1);
// 遍历待排序数组，为计数数组赋值
array.forEach((element) => {
// 以当前遍历到的元素值为索引将对应位置元素值初始化为0
if (!counts[element]) {
counts[element] = 0;
}
// 当前位置的值进行自增，顺便应对数组中有重复值的情况，有重复值时当前位置的值必定大于1
counts[element]++;
});
// 声明一个变量用于数组最终排序
let sortedIndex = 0;
// 遍历计数数组，根据计数数组的元素位置对待排序数组进行排序
counts.forEach((count, i) => {
// 如果当前遍历到的元素值大于0，则执行替换操作进行排序
while (count > 0) {
// 将当前元素索引赋值给array的sortedIndex号元素，随后sortedIndex自增
array[sortedIndex++] = i;
// 当前元素值自减，如果其值大于1，证明此处有重复元素，那么我们就继续执行while循环
count--;
}
});
// 最后，排序完成，返回排序好的数组
return array;
}
编写测试代码
我们将上述图中的例子放进代码中执行，看看我们写的函数是否正确执行。
const array = [12, 6, 3, 4, 1, 7];
const sort = new Sort(array);
const result = sort.countingSort(array);
console.log(result.join());
桶排序
桶排序也是一种分布式排序算法，它将元素分为不同的桶，再使用一个简单的排序算法，例如插入排序，来对每个桶进行排序，最后，它将所有的桶合并为结果数组。
实现思路
首先，我们需要指定需要多个桶来排序各个元素，默认情况，我们会使用5个桶。桶排序在所有元素平分到各个桶中时的表现最好。如果元素非常稀疏，则使用更多的桶会更好。如果元素非常密集，则使用较少的桶会更好。因此我们为了算法的效率，会让调用者根据实际需求将桶的数量作为参数传进来。我们将算法分为两个部分：
- 创建桶，并将桶分布到不同的桶中
- 对每个桶中的元素执行排序算法并将所有桶合并成排序好后的结果数组
我们先来看看创建桶的思路
- 声明创建桶函数（createBuckets），接收两个参数：待排序数组（array），桶大小（bucketSize）
- 计算array中的最大值（maxValue）和最小值（minValue）
- 计算每个需要的桶数量，公式为：(maxValue - minValue) / bucketSize)+1
- 声明一个二维数组buckets，用于存放所有桶
- 根据桶数量，初始化每个桶
- 遍历array，将每个元素分布到桶中
- 计算需要将元素放到哪个桶中(bucketIndex)，公式为：(array[i] - minValue) / bucketSize
- 将元素与放进合适的桶中，即buckets[bucketIndex].push(array[i])
- 将桶返回
接下来我们来看看对每个桶里的元素进行排序的思路
- 创建排序桶函数（sortBuckets），接收一个参数: 桶buckets
- 需要一个辅助数组sortedArray，用于存放排序好的结果数组
- 遍历sortedArray
- 如果当前桶内存储的桶buckets[i]不为null，就对其执行插入排序
- 将排序好的桶buckets[i]解构后放进sortedArray中
- 最后，返回sortedArray
我们通过一个例子，来讲解上述思路，如下图所示
实现代码
接下来，我们将上述思路转换为代码。
// 桶排序
bucketSort(array: number[], bucketSize = 5): T[] | number[] {
if (array.length < 2) {
return array;
}
// 创建桶，对桶进行排序
return this.sortBuckets(<[][]>this.createBuckets(array, bucketSize));
}
/**
* 创建桶
* @param array 待排序数组
* @param bucketSize 桶大小，即每个桶里的元素数量
*
* @return 二维数组类型的桶
*/
private createBuckets = (array: number[], bucketSize: number): number[][] => {
// 计算数组最大值与最小值
let minValue = array[0];
let maxValue = array[0];
for (let i = 1; i < array.length; i++) {
if (array[i] < minValue) {
minValue = array[i];
} else if (array[i] > maxValue) {
maxValue = array[i];
}
}
// 计算需要的桶数量，公式为: 数组最大值与最小值的差值与桶大小进行除法运算
const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
// 用于存放桶的二维数组
const buckets: number[][] = [];
// 计算出桶数量后，初始化每个桶
for (let i = 0; i < bucketCount; i++) {
buckets[i] = [];
}
// 遍历数组，将每个元素分布到桶中
for (let i = 0; i < array.length; i++) {
// 计算需要将元素放到哪个桶中，公式为: 当前遍历到的元素值与数组的最小值的差值与桶大小进行除法运算
const bucketIndex: number = Math.floor((array[i] - minValue) / bucketSize);
// 将元素放进合适的桶中
buckets[bucketIndex].push(array[i]);
}
// 将桶返回
return buckets;
};
// 对每个桶进行排序
private sortBuckets(buckets: T[][]): T[] {
const sortedArray: T[] = [];
for (let i = 0; i < buckets.length; i++) {
if (buckets[i] != null) {
// 调用插入排序
this.insertionSort(buckets[i]);
// 将排序好的桶取出来，放进sortedArray中
sortedArray.push(...buckets[i]);
}
}
return sortedArray;
}
编写测试代码
我们将上述图中的例子放进代码中看其是否能正确执行。
const array = [12, 5, 6, 7, 8, 9, 11, 3, 4, 19];
const sort = new Sort(array);
const result = sort.bucketSort(array);
console.log(result.join());
基数排序
基数排序也是一个分布式排序算法，它根据数字的有效位或基数将整数分布到桶中。比如，十进制数，使用的基数是10.因此，算法将会使用10个桶用来分布元素并且首先基于各位数字进行排序，然后基于十位数字，然后基于百位数字，以此类推。
实现思路
基数排序也是用来排序整数，因此我们从最后一位开始排序所有的数。首先，只会基于最后一位有效位对数字进行排序，在下次迭代时，我们会基于第二个有效位进行排序（十位数字），然后是第三个有效位（百位数字），以此类推。我们继续这个过程直到没有待排序的有效位，因此我们需要知道数组中的最小值和最大值。实现基数排序我们需要一个辅助函数（countingSortForRadix），即根据有效位对数组进行排序。接下来，我们先来看下基数排序主函数的实现思路。
- 创建基数排序函数（radixSort），接受2个参数：待排序数组array，基数radixBash
- 首先，获取array的最大值maxValue和最小值minValue
- 声明一个辅助变量significantDigit，用于存储当前有效数字，默认从最后一位有效数字，即1
- 计算有效位，公式为：(maxValue - minValue) / significantDigit，计算出的值如果大于等于1执行下述逻辑：
- 以当前有效位作为参数调用singnificantDigit函数对数组进行排序
- 当前有效数字*基数，继续执行上述过程
- 最后，执行完成返回排序好多的数组
接下来，我们来看下基于有效位进行排序的函数实现思路。
- 创建countingSortForRadix函数，接受4个参数：待排序数组array，基数radixBase、有效位significantDigit、数组的最小值minValue
- 声明桶索引bucketsIndex以及桶buckets以及辅助数组aux
- 通过radixBase来初始化桶，默认初始化为0
- 遍历array，基于有效位计算桶索引执行计数排序
- 计算桶索引，公式为：((array[i] - minValue) / significantDigt) % radixBase
- 根据桶索引，执行计数操作，即buckets[bucketsIndex++]
- 计算累积结果得到正确的计数值，从1开始遍历到radixBase位置。
- buckets[i]等于buckets[i] 加上buckrts[i - 1]的值
- 计数完成，遍历array将值移回原始数组中，用aux辅助数组来存储
- 计算当前元素的桶索引bucketsIndex，公式为：((array[i] - minValue) / significantDigit) % radixBase
- 对当前桶索引内的元素执行自检操作，得到其在数组中的正确位置index
- 计算出索引后，在aux中的对应位置存储当前遍历到的元素
- 最后排序完成，返回axu。
我们通过一个例子来描述上述过程，如下图所示。
实现代码
接下来，我们将上述思路转换为代码.
/**
* 基数排序
* @param array 待排序数组
* @param radixBase 10进制排序，基数为10
*/
radixSort(array: number[], radixBase = 10): number[] {
if (array.length < 2) {
return array;
}
// 获取数组的最小值和最大值
const minValue = this.findMinValue(array);
const maxValue = this.findMaxValue(array);
// 当前有效数字,默认会从最后一位有效数字开始排序
let significantDigit = 1;
/**
* 计算有效位
* 最大值和最小值的差与有效数字进行除法运算，其值大于等于1就代表还有待排序的有效位
*/
while ((maxValue - minValue) / significantDigit >= 1) {
// 以当前有效位为参数对数组进行排序
array = this.countingSortForRadix(array, radixBase, significantDigit, minValue);
// 当前有效数字乘以基数，继续执行while循环进行基数排序
significantDigit *= radixBase;
}
return array;
}
/**
* 基于有效位进行排序
* @param array 待排序数组
* @param radixBase 基数
* @param significantDigit 有效位
* @param minValue 待排序数组的最小值
*/
private countingSortForRadix = (array: number[], radixBase: number, significantDigit: number, minValue: number) => {
// 声明桶索引以及桶
let bucketsIndex;
const buckets = [];
// 辅助数组，用于计数完成的值移动会原数组
const aux = [];
// 通过基数来初始化桶
for (let i = 0; i < radixBase; i++) {
buckets[i] = 0;
}
// 遍历待排序数组，基于有效位计算桶索引执行计数排序
for (let i = 0; i < array.length; i++) {
// 计算桶索引
bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase);
// 执行计数操作
buckets[bucketsIndex]++;
}
// 计算累积结果得到正确的计数值
for (let i = 1; i < radixBase; i++) {
buckets[i] = buckets[i] + buckets[i - 1];
}
// 计数完成，将值移回原始数组中,用aux辅助数组来存储
for (let i = array.length - 1; i >= 0; i--) {
// 计算当前元素的桶索引
bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase);
// 对当前桶索引内的元素执行自减操作,得到其在数组中的正确的位置
const index = --buckets[bucketsIndex];
// 计算出索引后，在aux中的对应位置存储当前遍历到的元素
aux[index] = array[i];
}
console.log(aux);
return aux;
};
编写测试代码
接下来，我们将上图中的例子放进代码中，观察函数是否正确执行。
const array = [12, 5, 6, 7, 8, 9, 11, 3, 4, 19];
const sort = new Sort(array);
const result = sort.radixSort(array);
console.log(result.join());
搜索算法
接下来，我们来学习搜索算法，搜索算法分为两种：顺序(线性)搜索和二分搜索。在之前文章中，我已经详细讲解了这两种搜索算法的基础原理以及图解实现，所以此处只讲其代码实现。文章传送门：数组查找: 线性查找与二分查找本文示例代码地址：SearchArithmetic.ts
顺序搜索
顺序搜索是最基本的搜索算法，它会将每一个数据结构中的元素和我们要找的元素做比较。它也是最低效的一种搜索算法。
实现代码
linearSearch(): number | null {
for (let i = 0; i < this.array.length; i++) {
if (this.array[i] === this.target) {
return i;
}
}
return null;
}
编写测试代码
const array = [7, 8, 1, 2, 3, 5, 12, 13, 16, 19];
const searchArithmetic = new SearchArithmetic(array, 7);
const mid = searchArithmetic.linearSearch();
console.log(mid);
二分搜索
二分搜索要求被搜索的数据结构已经排好序，它的基本原理就是找到数组的中间值，然后将目标值和找到的值进行大小比较，如果比中间值大就往中间值的右边找，否则就往中间值的左边找。
实现思路
- 选择数组的中间值
- 如果选中值是待搜索值，那么算法执行完毕
- 如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找（较小）
- 如果待搜索值比选中值要大，则返回步骤1并在选中值右边的子数组中寻找（较大）
实现代码
binarySearch(): number | null {
// 对数组进行排序
this.sort.quickSort();
// 设置指针作为数组边界
let low = 0;
let high = this.array.length - 1;
while (low <= high) {
// 获取数组中间值
const mid = Math.floor((low + high) / 2);
// 获取数组的中间值
const element = this.array[mid];
// 如果数组中间值小于目标值，low+1,向其右边继续找
if (this.compareFn(element, this.target) === Compare.LESS_THAN) {
low = mid + 1;
} else if (this.compareFn(element, this.target) === Compare.BIGGER_THAN) {
// 如果中间值大于目标值,向其左边继续找
high = mid - 1;
} else {
// 中间值等于目标值，元素找到，返回mid即当前元素在数组的位置
return mid;
}
}
// 未找到，返回null
return null;
}
编写测试代码
const array = [7, 8, 1, 2, 3, 5, 12, 13, 16, 19];
const searchArithmetic = new SearchArithmetic(array, 7);
const mid = searchArithmetic.binarySearch();
console.log(mid);
内插搜索
内插搜索是改良版的二分搜索。二分搜索总是检查mid位置上的值，而内插搜索可能会根据要搜索的值检查数组中的不同地方。
实现思路
它遵循以下步骤：
- 使用position公式选中一个值
- 如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找（较小）
- 如果待搜索值比选中值要大，则返回步骤1并在选中值右边的子数组中寻找（较大）
实现代码
/**
* 内插搜索
* 二分查找的优化，通过特定算法计算delta和position的值优化掉二分查找的寻找中间值做法
* @param equalsFn 校验两个值是否相等函数
* @param diffFn 计算两个数的差值函数
*/
interpolationSearch(equalsFn = defaultEquals, diffFn: IDiffFunction<T> = defaultDiff): number | null {
// 排序
this.sort.quickSort();
// 获取数组程度
const { length } = this.array;
// 定义指针，确定数组边界
let low = 0;
let high = length - 1;
// 声明position，用于公式
let position = -1;
let delta = -1;
// 目标值大于等于数组的low边界值且目标值小于等于high边界值就执行循环里的内容
while (low <= high && biggerEquals(this.target, this.array[low], this.compareFn) && lesserEquals(this.target, this.array[high], this.compareFn)) {
// 目标值与array的low边界的值做差
// 与array的high边界的值和low边界的值做差
// 最后将二者得出的值做除法运算，计算出delta值
delta = diffFn(this.target, this.array[low]) / diffFn(this.array[high], this.array[low]);
// 计算比较值的位置
position = low + Math.floor((high - low) * delta);
// 如果比较值位置的元素等于目标值，则返回当前索引
if (equalsFn(this.array[position], this.target)) {
return position;
}
// 如果比较值位置的元素小于目标值，则向其右边继续找
if (this.compareFn(this.array[position], this.target) === Compare.LESS_THAN) {
low = position + 1;
} else {
// 如果比较值位置的元素大于目标值，则向其左边继续查找
high = position - 1;
}
}
// 未找到
return null;
}
编写测试代码
const array = [7, 8, 1, 2, 3, 5, 12, 13, 16, 19];
const searchArithmetic = new SearchArithmetic(array, 7);
const mid = searchArithmetic.interpolationSearch();
console.log(mid);
随机算法
在日常开发中，我们会遇到将数组中的元素打乱位置，这样的场景，那么此时我们就需要设计一种随机算法来实现了，现实中一个很常见的场景就是洗扑克牌。
Fisher-Yates算法
此处我们讲解一种随机算法，名为Fisher-Yates，顾名思义，该算法就是由Fisher 和 Yates 创造。
实现思路
该算法的核心思想就是，从数组的最后一位开始迭代数组，将迭代到的元素和一个随机位置进行交换。这个随机位置比当前位置小。这样这个就算法可以保证随机过的位置不会再被随机一次。下图展示了这个算法的操作过程
实现代码
export class ShuffleArithmetic<T> {
constructor(private array: T[]) {}
// Fisher-Yates随机算法
fisherYates(): T[] {
// 从数组的最后一位向前遍历数组
for (let i = this.array.length - 1; i > 0; i--) {
// 计算随机位置,用一个随机数与i+1相加,得出的随机位置一定比当前位置小
const randomIndex = Math.floor(Math.random() * (i + 1));
// 交换当前位置的元素和随机位置的元素
this.swap(i, randomIndex);
}
return this.array;
}
/**
* 交换数组的元素
* @param a
* @param b
* @private
*/
private swap(a: number, b: number) {
const temp: T = this.array[a];
this.array[a] = this.array[b];
this.array[b] = temp;
}
}
编写测试代码
import { ShuffleArithmetic } from "./lib/ShuffleArithmetic.ts";
const array = [4, 5, 6, 1, 2, 3, 4, 5, 8, 9, 0, 11, 22, 41];
const shuffleArithmetic = new ShuffleArithmetic(array);
shuffleArithmetic.fisherYates();
console.log("随机排序后的数组元素", array.join());
作者：神奇的程序员K
转发链接：https://mp.weixin.qq.com/s/3B8dZRfbIuktSBeArXlmcQ
