Radix Sort
Radix Sort
复制标题
基数排序
DOI：
10.1007/978-0-387-09766-4_2042
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Parosh Aziz Abdulla
中科院分区：
文献类型：
--
作者：
Parosh Aziz Abdulla
Ω(n log n) 排序下限不适用于使用比比较更强的运算的算法。一个基本的例子是用于对整数进行排序的计数排序。输入：（多）集 R = {k1, k2,. .. kn} 范围内的整数 [0..σ)。输出：R 在数组 J[0..n) 中按非降序排列。 (1) for i ← 0 to σ − 1 do C[i] ← 0 (2) for i ← 1 to n do C[ki] ← C[ki] + 1 (3) sum ← 0 (4) for i ← 0 to σ − 1 do // 累积和 (5) tmp ← C[i]; C[i] ← 总和； sum ← sum + tmp (6) for i ← 1 to n do // 分布 (7) J[C[ki]] ← ki; C[ki] ← C[ki] + 1 (8) 返回J • 时间复杂度为O(n + σ)。 • 计数排序是一种稳定的排序算法，即相等元素的相对顺序保持不变。 41 同样，Ω(ΣLCP (R) + n log n) 下限不适用于使用比符号比较更强的操作的字符串排序算法。基数排序就是这样一种整数字母表算法。基数排序是为对大整数进行排序而开发的，但它将整数视为一串数字，因此它实际上是一种字符串排序算法。
The Ω(n log n) sorting lower bound does not apply to algorithms that use stronger operations than comparisons. A basic example is counting sort for sorting integers. Input: (Multi)set R = {k1, k2,. .. kn} of integers from the range [0..σ). Output: R in nondecreasing order in array J[0..n). (1) for i ← 0 to σ − 1 do C[i] ← 0 (2) for i ← 1 to n do C[ki] ← C[ki] + 1 (3) sum ← 0 (4) for i ← 0 to σ − 1 do // cumulative sums (5) tmp ← C[i]; C[i] ← sum; sum ← sum + tmp (6) for i ← 1 to n do // distribute (7) J[C[ki]] ← ki; C[ki] ← C[ki] + 1 (8) return J • The time complexity is O(n + σ). • Counting sort is a stable sorting algorithm, i.e., the relative order of equal elements stays the same. 41 Similarly, the Ω(ΣLCP (R) + n log n) lower bound does not apply to string sorting algorithms that use stronger operations than symbol comparisons. Radix sort is such an algorithm for integer alphabets. Radix sort was developed for sorting large integers, but it treats an integer as a string of digits, so it is really a string sorting algorithm.