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

编写测试代码我们将图中的例子放在代码里，执行下查看排序函数是否正常运行。
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));    }

编写测试代码我们将上图中的例子放到代码中执行用以验证我们的函数是否正确执行