/typescript-algorithm

Primary LanguageTypeScript

TypeScript Algorithm

Relying on Deno environment.

Data Structure

List - QuickSelectFR

参考维基百科 - Floyd-Rivest Algorithm

算法

Floyd-Rivest算法是一个分治法的算法，通过使用采样的辅助将列表分成3组。然后在适当的集合中递归选择第k个最小的元素。

常规步骤：

  1. 从列表L中随机选择一个小的列表S
  2. 从S中，递归选取两个元素u和v，使u < v。这两个元素将成为分区的枢轴，并且包含它们之间整个列表（排序列表中）的第k个最小的元素。
  3. 使用u和v将S分区成三个集合：A、B、C；A将包含小于u的元素，B将包含u和v之间的元素，C将包含大于v的元素。
  4. 通过将L中的其余元素（即L - S的元素）与u或v进行比较，并将它们放入适当的集合中，从而对它们进行分区。如果k 小于L中四舍五入后的元素个数的一半，则应将其余元素先和v比较，然后将它们与u比较（如果它们小于v）。否则，将其余元素先与u比较，如果大于u则仅与v比较。
  5. 根据k的值，将算法递归应用于适当的集合，以选择L中的第k个最小的元素。