江苏龙网

  1. 主页 > 生活百科 > >

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

TypeScript


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

文章插图
 
作者：神奇的程序员K
转发链接：https://mp.weixin.qq.com/s/3B8dZRfbIuktSBeArXlmcQ
前言我们在页面上渲染数据时，通常会根据特定规则来对数据进行一个排序，然后再将其渲染到页面展示给用户 。哪么对数据进行排序有很多种方式，哪一种效率高？哪一种稳定性好？那一种占用内存小？本文将详解经典的八大排序算法以及三种搜索算法，并用TypeScript将其实现，欢迎各位对上述问题迷惑的开发者阅读本文 。
排序算法我们先来学习下排序算法，八大排序包括：冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、同排序、基数排序其中有几个排序我在之前的文章中已经讲解了其图解实现，本文将注重讲解其实现，另外几篇文章链接如下:
  • 排序算法:冒泡排序
  • 排序算法:选择排序
  • 排序算法:插入排序
  • 排序算法:归并排序
  • 排序算法:快速排序
冒泡排序冒泡排序是排序算法中最简单、最好理解的一个排序算法，但是从运行时间的角度来看，它的效率是最低的 。本文中所有函数实现的代码地址: Sort.ts
实现思路它会比较相邻的两个项，如果第一个比第二个大，则交换它们 。元素项向上移动至正确的顺序 。为了让排序算法更灵活，不仅仅只是用于数字的排序，因此本文中讲解的排序算法都会有一个比对函数作为参数传进来，用于定义两个值的比较方式 。
  • 声明一个函数其接受两个参数：待排序数组 & 比对函数
  • 第一层循环i：从待排序数组的0号元素开始遍历数组，遍历到最后一位，用于控制数组需要经过多少轮排序
  • 第二层循环j：从数组的0号元素开始遍历，遍历至数组的倒数第二位元素再减去第一层循环i 。
  • 比较大小，在第二层循环中，将当前遍历到的元素和其下一个元素比较大小，如果 j > j + 1就交换两个元素的位置 。
我们通过一个例子来描述下上述思路，如下图所示，将一个乱序数组执行冒泡排序后，将其从小到大排列 。
实现代码为了让函数便于维护，我们新建一个类名为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);                }            }        }    }


推荐阅读


上一篇：详解DBSCAN聚类

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