c - 分页排序算法

Question

我想对条目列表进行排序，然后选择该排序列表的子集（页面）。例如; 我有 10.000 个项目，并且希望从 101 到 200 个项目。一种天真的方法是首先对所有 10.000 个项目进行排序，然后选择页面；这意味着项目 1 - 100 和 201 - 10.000 都不必要地完全排序。是否存在一种现有算法，它只会对页面中的项目进行完全排序，一旦明确条目不在页面中，就会停止进一步排序？C中的源代码会很棒，但描述也可以

Answer 1

假设你想要 n 中的 p 到 q 项。虽然排序会花费 O(n·log n) 时间，但您提到的操作可以在 O(n) 时间内完成（只要 qp « n），如下所示：应用O(n) 时间方法来查找 pᵗʰ和 qᵗʰ 值。然后只选择值从 p 到 q 的项目，如果 k=qp，则在时间 O(n+k) 或大约 O(n) 时间，并在时间 O(k·log k) 中对这些项目进行排序，大约是 O (1)，如果 k 为 O(1)，则净时间 O(n)。

Answer 2

Suppose the page you want starts with the nth "smallest" element (or largest or whatever ordinal scale you prefer). Then you need to divide your partial sorting algorithm into two steps:

1. Find the nth element
2. Sort elements {n, n+1, ..., n+s} (where s is the page size)

Quicksort is a sorting algorithm that can be conveniently modified to suit your needs. Basically, it works as follows:

• Given: a list L of ordinally related elements.
• If L contains exactly one element, return L.
• Choose a pivot element p from L at random.
• Divide L into two sets: A and B such that A contains all the elements from L which are smaller than p and B contains all the elements from L which are larger.
• Apply the algorithm recursively to A and B to obtain the sorted sublists A' and B'.
• Return the list A || p || B, where || denotes appending lists or elements.

What you want to do in step #1, is run Quicksort until you've found the nth element. So step #1 will look like this:

• Given: a list L of ordinally related elements, a page offset n and a page size s.
• Choose a pivot element p from L at random.
• Divide L into A and B.
• If the size of A, #A = n-1, then return p || B.
• If #A < n-1, then apply the algorithm recursively for L' = B and n' = n - #A
• If #A > n-1, then apply the algorithm recursively for L' = A and n' = n

This algorithm returns an unsorted list of elements starting with the nth element. Next, run Quicksort on this list but keep ignoring B unless #A < s. At the end, you should have a list of s sorted elements which are larger than n elements from the original list but not larger than n+1 elements from the original list.

The term you want to research is partial sorting. There is likely to be an implementation of it in C or any sufficiently popular language.