基数排序

前言

基数排序是一种非常快且好写的排序。
以前一直以为基数排序就是桶排,现在发现自己很智慧,警钟长鸣。

思想

基数排序是一个以桶排为基础的排序。
桶排我就不多说了,简单且 \(O(n)\)
但是桶排有一个弊端,就是由于考试时空间限制是 \(10^8\) 左右,可需要排序的数据是 \(10^9\) 的,就不能用桶排了。
桶排中的空间其实有一大半都是浪费了的,那么换一种思路,我们可不可以将需要排序的 \(a_i\) 拆成一位一位的再做。
这里定义 \(x_i\)\(y_i\) 中,\(x_i\) 表示 \(a_i\) 的第 \(K\) 位的数,\(y_i\) 就表示第 \(K-1\) 位的数字。
然后分别对 \(x_i\)\(y_i\) 进行桶排,并对 \(x_i\) 的桶 \(c_i\) 做前缀和,这时 \(x_i\) 的排名就是 \(c_{x_i-1}+1 \sim c_{x_i}\)
再对 \(y_i\) 建立下标映射,设 \(p_{y_i}\)\(y_i\) 的下标。
这里 \(x_i\)\(y_i\) 因为下标相同,表示的就是 \(a_i\)
那么我们就可以用 \(x_{p_i}\) 来表示 \(y_i\) 所对应的 \(x_i\)
注意,这里我们从大到小\(i\) 进行遍历,\(y_i\) 就是从大到小的,其 \(a_{p_i}\) 就是 \(c_{x_{p_i}-1}+1 \sim c_{x_{p_i}}\) 范围中排名最大的。
\(c_{x_{p_i}}\) 就是 \(a_{p_i}\) 的排名。最后将 \(c_{x_{p_i}}\) 减一再进行下一次遍历。

热门相关:恭喜你被逮捕了   半仙   重生野性时代   半仙   变身蜘蛛侠