admin 管理员组

文章数量: 1184232

基数排序

基数排序也是一种稳定排序算法，且一般计数排序被用在基数排序过程中。
基数排序包括 LSD(Least significant digital) 和 MSD(Least significant digital) 两大类。

LSD 基数排序的思想非常直观：假设一个数组的最高位有 d d d 位，那么依次从低位向高位处理，先排好个位，然后在排好个位的基础上排十位，以此类推，直到遍历完最高位次，排序结束。每一次都使用一种稳定排序算法对该数组进行排序。

上图表示一个由 7 个 3 位数组成的列表的基数排序。最左边的一列是输入数据，其余各列显示了由低到高位连续进行排序后列表的情况。阴影指出了进行排序的位。

引理：给定 n n n 个最高位为 d d d 的数，其中每一个数位有 k k k 个可能的取值。如果基数排序使用的稳定排序方法耗时 O ( n + k ) O(n + k) O(n+k)，那么它就可以在 O ( d ( n + k ) ) O(d(n+k)) O(d(n+k)) 时间内将这些数排序。

在下面的代码中，我们假设 n n n 个 d d d 位的元素存放在数组 A A A 中，其中第一位是最低位，第 d d d 位是最高位。

Radix-Sort(A, d) {
    for i=1 to d
        use a stable sort to sort array A on digit i
}

本文标签： 基数 算法 简介

版权声明：本文标题：排序算法——基数排序简介 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1754940468a3052470.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。