作者：神奇的程序员K
转发链接：https://mp.weixin.qq.com/s/3B8dZRfbIuktSBeArXlmcQ
我们在页面上渲染数据时，通常会根据特定规则来对数据进行一个排序，然后再将其渲染到页面展示给用户。哪么对数据进行排序有很多种方式，哪一种效率高？哪一种稳定性好？那一种占用内存小？本文将详解经典的八大排序算法以及三种搜索算法，并用TypeScript将其实现，欢迎各位对上述问题迷惑的开发者阅读本文。
我们先来学习下排序算法，八大排序包括：冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、同排序、基数排序其中有几个排序我在之前的文章中已经讲解了其图解实现，本文将注重讲解其实现，另外几篇文章链接如下:
冒泡排序是排序算法中最简单、最好理解的一个排序算法，但是从运行时间的角度来看，它的效率是最低的。本文中所有函数实现的代码地址: Sort.ts
它会比较相邻的两个项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序。为了让排序算法更灵活，不仅仅只是用于数字的排序，因此本文中讲解的排序算法都会有一个比对函数作为参数传进来，用于定义两个值的比较方式。
我们通过一个例子来描述下上述思路，如下图所示，将一个乱序数组执行冒泡排序后，将其从小到大排列。
为了让函数便于维护，我们新建一个类名为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());
选择排序是一种原址比较排序算法，它的大致思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值将其放在第二位，依次类推。
下图中的示例描述了上述思路
// 选择排序
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());
插入排序会将数组分为已排序区域和未排序区域，将未排序区域的数组项和已排序区域的数组进行大小比较，确立要插入的位置，然后将其插入到对应的位置。
如下图所示，我们通过一个例子描述了上述插入排序的过程
接下来我们将上述思路转换为代码。
// 插入排序
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引擎使用快速排序实现，火狐浏览器使用归并排序实现。
归并排序是一个分而治之算法，就是将原始数组切分成比较小的数组，直到每个小数组只有一个位置，接着将小数组归并成比较大的数组，直到最后只有一个排序完毕的大数组。由于是分治法，归并排序也是递归的。我们要将算法分为两个函数：一个用于将函数分割成小数组，一个用于将小数组合并成大数组。我们先来看看主函数，将数组分割成小数组。
接下来，我们再来看下合并函数的实现
下图用一个例子描述了上述归并排序的过程
接下来，我们将上述思路转换为代码。
// 归并排序
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());
快速排序与归并排序一样都是可用作实际应用的算法，它也是使用分而治之的方法，将原始数组分为较小的数组，但它没有像归并排序那样将他们分割开。
我们需要三个函数：主函数、排序函数、切分函数。
接下来我们将上述思路转换为代码:
/**
*
* @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());
计数排序是一个分布式排序，它是用来排序整数的优秀算法。分布式排序使用已组织好的辅助数据结构，然后进行合并，得到排好序的数组。计数排序使用一个用来存储每个元素在原始数组中出现次数的临时数组。在所有元素都计数完成后，临时数组已排好序并可迭代以构建排序后的结果数组。
接下来我们通过一个例子来讲解下上述过程，如下图所示：
接下来我们将上述思路转换为代码
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个桶。桶排序在所有元素平分到各个桶中时的表现最好。如果元素非常稀疏，则使用更多的桶会更好。如果元素非常密集，则使用较少的桶会更好。因此我们为了算法的效率，会让调用者根据实际需求将桶的数量作为参数传进来。我们将算法分为两个部分：
我们先来看看创建桶的思路
接下来我们来看看对每个桶里的元素进行排序的思路
我们通过一个例子，来讲解上述思路，如下图所示
接下来，我们将上述思路转换为代码。
// 桶排序
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），即根据有效位对数组进行排序。接下来，我们先来看下基数排序主函数的实现思路。
接下来，我们来看下基于有效位进行排序的函数实现思路。
我们通过一个例子来描述上述过程，如下图所示。
接下来，我们将上述思路转换为代码.
/**
* 基数排序
* @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);
二分搜索要求被搜索的数据结构已经排好序，它的基本原理就是找到数组的中间值，然后将目标值和找到的值进行大小比较，如果比中间值大就往中间值的右边找，否则就往中间值的左边找。
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位置上的值，而内插搜索可能会根据要搜索的值检查数组中的不同地方。
它遵循以下步骤：
/**
* 内插搜索
* 二分查找的优化，通过特定算法计算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 创造。
该算法的核心思想就是，从数组的最后一位开始迭代数组，将迭代到的元素和一个随机位置进行交换。这个随机位置比当前位置小。这样这个就算法可以保证随机过的位置不会再被随机一次。下图展示了这个算法的操作过程
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
京公网安备 11010802035086号