代码之家  ›  专栏  ›  技术社区  ›  Enriquev

部分排序算法

  •  6
  • Enriquev  · 技术社区  · 15 年前

    假设我有5000万个特性,每个特性都来自磁盘。

    在我的程序开始时,我处理每个特性,并根据某些条件,对某些特性应用一些修改。

    A在我的程序中,这一点,我正在从磁盘读取一个特性,处理它,然后写回去,因为我没有足够的RAM来同时打开所有5000万个特性。

    现在假设我要对这5000万个特性进行排序,有没有最佳的算法可以做到这一点,因为我不能同时加载每个特性?

    比如部分排序算法之类的?

    2 回复  |  直到 15 年前
        1
  •  7
  •   Tomas Petricek    15 年前

    通常,您要查找的算法类称为 external sorting . 也许这种排序算法最广为人知的例子被称为 Merge sort .

    这个算法(外部版本)的思想是将数据分割成若干块,您可以在内存中就地排序(例如100000),并独立地对每个块排序(使用一些标准算法,例如 Quick sort )然后,取块并合并它们(所以将两个100K块合并为一个200K块),这可以通过将两个块中的元素读取到缓冲区中来完成(因为这些块已经排序)。最后,将两个较小的块合并为一个块,该块将按正确的顺序包含所有元素。

        2
  •  2
  •   Matthieu M.    15 年前

    如果您在Unix上,请使用 sort ;)

    这可能看起来很愚蠢,但是命令行工具已经被编程来处理这个案例,您不必重新编程。