江苏龙网

  1. 主页 > 生活百科 > >

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

TypeScript

编写测试代码接下来，我们将上图中的例子放进代码中，观察函数是否正确执行 。
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());

TypeScript实现八大排序与搜索算法

文章插图
 
搜索算法接下来，我们来学习搜索算法，搜索算法分为两种：顺序(线性)搜索和二分搜索 。在之前文章中，我已经详细讲解了这两种搜索算法的基础原理以及图解实现，所以此处只讲其代码实现 。文章传送门：数组查找: 线性查找与二分查找本文示例代码地址：SearchArithmetic.ts
顺序搜索【TypeScript实现八大排序与搜索算法】顺序搜索是最基本的搜索算法，它会将每一个数据结构中的元素和我们要找的元素做比较 。它也是最低效的一种搜索算法 。
实现代码    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);
TypeScript实现八大排序与搜索算法

文章插图
 
二分搜索二分搜索要求被搜索的数据结构已经排好序，它的基本原理就是找到数组的中间值，然后将目标值和找到的值进行大小比较，如果比中间值大就往中间值的右边找，否则就往中间值的左边找 。
实现思路
  • 选择数组的中间值
  • 如果选中值是待搜索值，那么算法执行完毕
  • 如果待搜索值比选中值要小，则返回步骤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;    }


推荐阅读


上一篇：详解DBSCAN聚类

下一篇：面向对象编程OOP的基本概念