前言
基數排序是一種非常快且好寫的排序，
以前一直以為基數排序就是桶排，現在發現自己很智慧，警鐘長鳴，
思想
基數排序是一個以桶排為基礎的排序，
桶排我就不多說了，簡單且 \(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}}\) 減一再進行下一次遍歷，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/556684.html
標籤：其他
上一篇：2023 年 7 個適合初學者的 Vue.js 教程
下一篇：返回列表