江苏龙网

  1. 主页 > 生活百科 > >

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

TypeScript

编写测试代码我们将上图中的例子放在代码中，测试下执行结果是否正确 。
const array = [12, 6, 3, 4, 1, 7];const sort = new Sort(array);sort.bubbleSort();console.log(array.join());

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

文章插图
 
选择排序选择排序是一种原址比较排序算法，它的大致思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值将其放在第二位，依次类推 。
实现思路
  • 声明一个辅助变量:indexMin用于存储数组中的最小值
  • 第一层循环i，从数组的0号元素遍历到数组的倒数第二位 。indexMin默认赋值为i，用于控制轮数
  • 第二层循环j，从数组的i号元素遍历到数组的末尾，用于寻找数组的最小值，如果indexMin位置的元素大于j号位置的元素就覆盖indxMin的值为j
  • 在第二层循环结束后，比较i与indexMin是否相等，如果不相等就交换两个元素的位置 。
下图中的示例描述了上述思路![7d4cc6a280d6d13955475ae268e50a2f](https://www.kaisir.cn/uploads/MarkDownImg/202008140013/Image 3.png)
实现代码    // 选择排序    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());
TypeScript实现八大排序与搜索算法

文章插图
 
插入排序插入排序会将数组分为已排序区域和未排序区域，将未排序区域的数组项和已排序区域的数组进行大小比较，确立要插入的位置，然后将其插入到对应的位置 。
实现思路
  • 第一层循环i：从数组的1号元素开始，遍历到数组末尾，因为我们会先假设0号元素已经排好序，所以从1号元素开始 。
  • 用一个临时变量temp存储当前i号位置的元素，用一个变量j存储i
  • while循环: j > 0且j - 1位置的元素大于temp，就把j位置的值设置为j - 1 位置的值，最后j--，继续下一轮遍历 。
  • while循环结束后，将temp放到正确的位置array[ j ]
如下图所示，我们通过一个例子描述了上述插入排序的过程
TypeScript实现八大排序与搜索算法

文章插图
 
实现代码接下来我们将上述思路转换为代码 。
    // 插入排序    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;        }    }


推荐阅读


上一篇：详解DBSCAN聚类

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