基于Bucket Sort的k唯一元素排序：要求O(kn)时间复杂度实现

Alright, let's break down how to implement bucket sort for this specific scenario—where we have n elements with k unique values, need O(kn) time, can't use hash tables, and don't know the element range upfront. The core idea is to leverage the k unique elements using basic arrays (no fancy data structures) and combine linear scans with a small sort step for the unique values.

Here's the step-by-step plan, using only basic arrays and linear operations:

1. Collect all k unique elements

   • Initialize an empty array unique_elements to store distinct values.
   • Traverse the original input array:
     • For each element, perform a linear scan of unique_elements to check if it's already present.
     • If not found, append it to unique_elements (this ensures we only keep one copy of each unique value).
   • This step runs in O(nk) time: each of the n elements may require scanning up to k unique values.

2. Sort the unique elements array

   • Since we need the final sorted output, we have to sort the unique_elements array first. Use a basic comparison sort like insertion sort or bubble sort—both run in O(k²) time.
   • Since k ≤ n (you can't have more unique elements than total elements), O(k²) is asymptotically bounded by O(nk), so this doesn't break our time complexity requirement.

3. Count frequencies of each unique element

   • Create a counts array of length k (matching the size of unique_elements), initialized to 0.
   • Traverse the original input array again:
     • For each element, perform a linear scan of unique_elements to find its index i.
     • Increment counts[i] by 1 (this tracks how many times each unique element appears).
   • This step also runs in O(nk) time, same as the first collection step.

4. Reconstruct the sorted array

   • Initialize an empty result array.
   • Iterate over the sorted unique_elements array:
     • For each element at index i, append it to the result array counts[i] times.
   • This step runs in O(n) time, since we're just writing out all n elements.

Let's use the input array [5, 2, 5, 2, 3] (n=5, k=3) to see how this works:

1. Collect unique elements: After traversal, unique_elements becomes [5, 2, 3].
2. Sort unique elements: Sorted unique_elements is [2, 3, 5].
3. Count frequencies:
   • Traverse input: 5 → index 2 → counts[2] = 1; 2 → index 0 → counts[0] = 1; 5 → index 2 → counts[2] = 2; 2 → index 0 → counts[0] = 2; 3 → index 1 → counts[1] = 1.
   • Final counts array: [2, 1, 2].
4. Reconstruct sorted array: Append 2 twice, 3 once, 5 twice → [2, 2, 3, 5, 5].

Adding up all steps:

• O(nk) (collect unique) + O(k²) (sort unique) + O(nk) (count frequencies) + O(n) (reconstruct) = O(nk)
  Since k ≤ n, O(k²) ≤ O(nk), so the overall time complexity stays within the required O(kn) bound.

• No hash tables needed: We use basic arrays for both storing unique elements and their counts—perfect for meeting the "only basic data structures" requirement.
• No reliance on element range: We never care about the actual values of the elements (even if they're huge), only whether they match existing unique elements via linear scans.
• Uniqueness is critical: Knowing there are only k unique values lets us limit the linear scan length to k instead of n, which is what keeps the time complexity at O(nk) instead of O(n²).

内容的提问来源于stack exchange，提问作者Cauthon