TypeScript实现八大排序与搜索算法( 十 ) _TypeScript

编写测试代码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());