江苏龙网

  1. 主页 > 生活百科 > >

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

TypeScript


const array = [12, 6, 3, 4, 1, 7];const sort = new Sort(array);const result = sort.mergeSort();console.log(result.join());

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

文章插图
 
快速排序快速排序与归并排序一样都是可用作实际应用的算法，它也是使用分而治之的方法，将原始数组分为较小的数组，但它没有像归并排序那样将他们分割开 。
实现思路我们需要三个函数：主函数、排序函数、切分函数 。
  • 主函数（quickSort），调用排序函数，返回排序函数最终排好的数组 。
  • 排序函数（quick），接收3个参数: 待排序数组（array）、数组的左边界（left）、数组的右边界（right）
    • 声明一个辅助变量index，用于存储分割子数组的的位置 。
    • 确立递归终止条件：array < 1，如果array.length > 1，就执行下述操作：
      执行划分函数，计算划分点，将得到的值赋值给index；
      如果left > index - 1，代表子数组中存在较小值的元素，从数组的left边界到index-1边界递归执行排序函数；
      如果index < right，代表子数组存在较大值的元素，从数组的index到right边界递归执行排序函数；
  • 划分函数（partition），与排序函数一样，它也接收3个参数 。
    • 从数组中选择一个主元pivot，选择数组的中间值
    • 声明两个指针：i, j，分别指向左边数组的第一个值和右边数组的第一个值 。
    • 如果i <= j，则代表left指针和right指针没有相互交错，则执行下述划分操作：
      移动left指针直至找到一个比主元大的元素，即array[i] > pivot；
      移动right指针直至找到一个比主元小的元素，即array[j] < pivot；
      当左指针指向的元素比主元大且右指针指向的元素比主元小，并且左指针索引没有右指针索引大时就交换i号和j号元素的位置，随后移动两个指针；
      最后，划分结束，返回i的值；
实现代码接下来我们将上述思路转换为代码:
    /**     *     * @param array 待排序数组     * @param left 左边界     * @param right 右边界     * @private     */    private quick(array: T[], left: number, right: number) {        // 该变量用于将子数组分离为较小值数组和较大值数组        let index;        if (array.length > 1) {            // 对给定子数组执行划分操作，得到正确的index            index = this.partition(array, left, right);            // 如果子数组存在较小值的元素，则对该数组重复这个过程            if (left < index - 1) {                this.quick(array, left, index - 1);            }            // 如果子数组存在较大值的元素，也对该数组重复这个过程            if (index < right) {                this.quick(array, index, right);            }        }        return array;    }    // 划分函数    private partition(array: T[], left: number, right: number): number {        // 从数组中选择一个值做主元，此处选择数组的中间值        const pivot = array[Math.floor((right + left) / 2)];        // 创建数组引用，分别指向左边数组的第一个值和右边数组的第一个值        let i = left;        let j = right;        // left指针和right指针没有相互交错，就执行划分操作        while (i <= j) {            // 移动left指针直至找到一个比主元大的元素            while (this.compareFn(array[i], pivot) === Compare.LESS_THAN) {                i++;            }            // 移动right指针直至找到一个比主元小的元素            while (this.compareFn(array[j], pivot) === Compare.BIGGER_THAN) {                j--;            }            // 当左指针指向的元素比主元大且右指针指向的元素比主元小，并且左指针索引没有右指针索引大时就交换i和j号元素的位置，随后移动两个指针            if (i <= j) {                this.swap(array, i, j);                i++;                j--;            }        }        // 划分结束，返回左指针索引        return i;    }


推荐阅读


上一篇：详解DBSCAN聚类

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