在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。(Cf. Leetcode,2020)。
有一种做法是这样的：
1 | int* Count = new int[n](); |
这样的做法，我们同样可以用在排序中。对于上下界确定的欲排序数组，我们建立一个计数数组，遍历整个数组，进行计数，就可以直接输出对应的有序数组。我们称这种排序方法为鸽巢排序。这种排序方法在特殊的情况下可以实现时间复杂度 $O(n)$ 。
有些时候计数数组显得过于庞大，而且，例如对于一个双精度数组，就无法建立这样的对应数组。这个时候我们设立一系列“容量”相等的集合，将数组进行有序分割，再对被分割的子数组实施排序。这样的集合称为桶，这样的排序方法称为桶排序。
桶排序继承了鸽巢排序的优点，但是鸽巢排序占用空间大的问题仍然解决得不好。而且桶排序仍然有先决条件，可以说是一种特殊情况下的排序。
桶排序是一种分配排序。分配排序不需要进行关键码的比较，但需要知道待排序列的一些具体情况。(Cf.Jin-nuo,2016)
Author: Victrid
Permanent Link: https://victrid.dev/2020/ge-chao-pai-xu-yu-tong-pai-xu/
License: Copyright (c) 2025 victrid Terms of Use
Read our privacy policy on how these personalized advertisements are delivered to you.
For your reading experience, we provide full-text RSS feeds. Although math formulas cannot be displayed well, the interface can be adjusted as you like and there are no ads.
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。