无锡高端网站建设机构,移动建站平台,wordpress a 登录,十堰专业网站建设公司文章目录 1. 定义2. 算法步骤2.1 MSD基数排序2.2 LSD基数排序 3. LSD 基数排序动图演示4. 性质5. 算法分析6. 代码实现C语言PythonJavaCGo 结语 ⚠本节要介绍的不是计数排序 1. 定义
基数排序#xff08;英语#xff1a;Radix sort#xff09;是一种非比较型的排序算法Go 结语 ⚠本节要介绍的不是计数排序 1. 定义
基数排序英语Radix sort是一种非比较型的排序算法最早用于解决卡片排序的问题。基数排序将待排序的元素拆分为k个关键字逐一对各个关键字排序后完成对所有元素的排序。 如果是从第1关键字到第k关键字顺序进行比较则该基数排序称为 MSDMost Significant Digit first)基数排序——最高位优先法从高位到低位 如果是从第k关键字到第1关键字顺序进行比较则该基数排序称为 LSDLeast Significant Digit first)基数排序——最低位优先法从低位到高位。
基数排序是将整数按位数切割成不同的数字然后按每个位数分别比较由于整数也可以表达字符串比如名字或日期和特定格式的浮点数所以基数排序也不是只能使用于整数。
2. 算法步骤
2.1 MSD基数排序
将待排序的元素拆分为k个关键字先对第1关键字进行稳定排序然后对于每组 具有相同关键字的元素 再对第2关键字进行稳定排序递归执行……最后对于每组 具有相同关键字的元素 再对第k关键字进行稳定排序。 一般而言我们默认基数排序是稳定的所以在 MSD 基数排序中我们也仅仅考虑借助 稳定算法通常使用计数排序完成内层对关键字的排序。
2.2 LSD基数排序
将待排序的元素拆分为k个关键字然后先对 所有元素 的第k关键字进行稳定排序再对 所有元素 的第k-1关键字进行稳定排序再对 所有元素 的第k-2关键字进行稳定排序……最后对 所有元素 的第1关键字进行稳定排序这样就完成了对整个待排序序列的稳定排序。 LSD 基数排序也需要借助一种 稳定算法 完成内层对关键字的排序。同样的通常使用计数排序来完成。
3. LSD 基数排序动图演示 4. 性质
稳定性
如果对内层关键字的排序是稳定的则 MSD 基数排序和 LSD 基数排序都是稳定的排序算法。
空间复杂度
MSD 基数排序和 LSD 基数排序的空间复杂度都为 O ( k n ) O(kn) O(kn)。
时间复杂度
基数排序每一位的比较可以使用线性排序比如桶排序或者计数排序当然需要保证如计数排序的稳定性。每次排序时间复杂度O(n)那么如果有k位则时间复杂度为 O ( k ∗ n ) O(k*n) O(k∗n),如果k不大比如手机号11位那么时间复杂度就是 O ( n ) O(n) O(n) 通常而言基数排序比基于比较的排序算法比如快速排序要快。但由于需要额外的内存空间因此当内存空间稀缺时原地置换算法比如快速排序或许是个更好的选择。 一般来说如果每个关键字的值域都不大就可以使用 [计数排序]作为内层排序此时的复杂度为 O ( k n ∑ i 1 k w i ) O(kn{\sum_{i1}^k}wi) O(kn∑i1kwi)其中 w i wi wi为第i关键字的值域大小。如果关键字值域很大就可以直接使用基于比较的 O ( n k l o g n ) O(nklogn) O(nklogn)排序而无需使用基数排序了。 5. 算法分析
基数排序基于分别排序分别收集所以是稳定的。但基数排序的性能比桶排序要略差每一次关键字的桶分配都需要 O ( n ) O(n) O(n)的时间复杂度而且分配之后得到新的关键字序列又需要 O ( n ) O(n) O(n)的时间复杂度。假如待排数据可以分为d个关键字则基数排序的时间复杂度将是 O ( d ∗ 2 n ) O(d*2n) O(d∗2n)当然d要远远小于n因此基本上还是线性级别的。
基数排序的空间复杂度为O(nk)其中k为桶的数量。一般来说 n k nk nk因此额外空间需要大概n个左右。
6. 代码实现
C语言
#includestdio.h
#define MAX 20
//#define SHOWPASS
#define BASE 10void print(int *a, int n) {int i;for (i 0; i n; i) {printf(%d\t, a[i]);}
}void radixsort(int *a, int n) {int i, b[MAX], m a[0], exp 1;for (i 1; i n; i) {if (a[i] m) {m a[i];}}while (m / exp 0) {int bucket[BASE] { 0 };for (i 0; i n; i) {bucket[(a[i] / exp) % BASE];}for (i 1; i BASE; i) {bucket[i] bucket[i - 1];}for (i n - 1; i 0; i--) {b[--bucket[(a[i] / exp) % BASE]] a[i];}for (i 0; i n; i) {a[i] b[i];}exp * BASE;#ifdef SHOWPASSprintf(\nPASS : );print(a, n);
#endif}
}int main() {int arr[MAX];int i, n;printf(Enter total elements (n %d) : , MAX);scanf(%d, n);n n MAX ? n : MAX;printf(Enter %d Elements : , n);for (i 0; i n; i) {scanf(%d, arr[i]);}printf(\nARRAY : );print(arr[0], n);radixsort(arr[0], n);printf(\nSORTED : );print(arr[0], n);printf(\n);return 0;
}Python
# codingutf-8
def radix_sort(array):max_num max(array)place 1while max_num 10**place:place 1for i in range(place):buckets [[] for _ in range(10)]for num in array:radix int(num/(10**i) % 10)buckets[radix].append(num)j 0for k in range(10):for num in buckets[k]:array[j] numj 1return arrayif __name__ __main__:array [25, 17, 33, 17, 22, 13, 32, 15, 9, 25, 27, 18]print(radix_sort(array))Java
/*** 基数排序* 考虑负数的情况还可以参考 https://code.i-harness.com/zh-CN/q/e98fa9*/
public class RadixSort implements IArraySort {Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝不改变参数内容int[] arr Arrays.copyOf(sourceArray, sourceArray.length);int maxDigit getMaxDigit(arr);return radixSort(arr, maxDigit);}/*** 获取最高位数*/private int getMaxDigit(int[] arr) {int maxValue getMaxValue(arr);return getNumLenght(maxValue);}private int getMaxValue(int[] arr) {int maxValue arr[0];for (int value : arr) {if (maxValue value) {maxValue value;}}return maxValue;}protected int getNumLenght(long num) {if (num 0) {return 1;}int lenght 0;for (long temp num; temp ! 0; temp / 10) {lenght;}return lenght;}private int[] radixSort(int[] arr, int maxDigit) {int mod 10;int dev 1;for (int i 0; i maxDigit; i, dev * 10, mod * 10) {// 考虑负数的情况这里扩展一倍队列数其中 [0-9]对应负数[10-19]对应正数 (bucket 10)int[][] counter new int[mod * 2][0];for (int j 0; j arr.length; j) {int bucket ((arr[j] % mod) / dev) mod;counter[bucket] arrayAppend(counter[bucket], arr[j]);}int pos 0;for (int[] bucket : counter) {for (int value : bucket) {arr[pos] value;}}}return arr;}/*** 自动扩容并保存数据** param arr* param value*/private int[] arrayAppend(int[] arr, int value) {arr Arrays.copyOf(arr, arr.length 1);arr[arr.length - 1] value;return arr;}
}C
int maxbit(int data[], int n) //辅助函数求数据的最大位数
{int maxData data[0]; /// 最大数/// 先求出最大数再求其位数这样有原先依次每个数判断其位数稍微优化点。for (int i 1; i n; i){if (maxData data[i])maxData data[i];}int d 1;int p 10;while (maxData p){//p * 10; // Maybe overflowmaxData / 10;d;}return d;
/* int d 1; //保存最大的位数int p 10;for(int i 0; i n; i){while(data[i] p){p * 10;d;}}return d;*/
}
void radixsort(int data[], int n) //基数排序
{int d maxbit(data, n);int *tmp new int[n];int *count new int[10]; //计数器int i, j, k;int radix 1;for(i 1; i d; i) //进行d次排序{for(j 0; j 10; j)count[j] 0; //每次分配前清空计数器for(j 0; j n; j){k (data[j] / radix) % 10; //统计每个桶中的记录数count[k];}for(j 1; j 10; j)count[j] count[j - 1] count[j]; //将tmp中的位置依次分配给每个桶for(j n - 1; j 0; j--) //将所有桶中记录依次收集到tmp中{k (data[j] / radix) % 10;tmp[count[k] - 1] data[j];count[k]--;}for(j 0; j n; j) //将临时数组的内容复制到data中data[j] tmp[j];radix radix * 10;}delete []tmp;delete []count;
}Go
var (K int 3 // 基数排序需要的全局变量RADIX int 10queue [][]int
)
func radix_sort_queue_pop(qu []int) []int {if len(qu) 0 {return qu // 如果数组为空不做任何操作}// 删除第一个元素qu qu[1:]return qu
}
func radix_sort_queue_push(qu []int, data int) []int {qu append(qu, data)return qu
}
func radix_sort_get_key(value int, k int) int {key : 0for k 0 {key value % 10value / 10k--}return key
}
func radix_sort_distribute(arr []int, left int, right int, k int){// k表示是第几次分发数据for i:left; iright; i {key : radix_sort_get_key(arr[i], k)queue[key] radix_sort_queue_push(queue[key], arr[i])}
}
func radix_sort_collect(arr []int) {k : 0for i:0; i RADIX; i {for len(queue[i]) ! 0 {arr[k] queue[i][0] // 先进先出kqueue[i] radix_sort_queue_pop(queue[i])}}
}
func radix_sort_by_group(arr []int, left int, right int) {for i:0; iK; i {// 分发数据radix_sort_distribute(arr, left, right, i)// 回收数据radix_sort_collect(arr)}
}
func radix_sort(arr []int, sz int) {// 初始化队列queue make([][]int, RADIX)left : 0right : sz;radix_sort_by_group(arr, left, right)
}结语
今天的分享到这里就结束啦如果觉得文章还不错的话可以三连支持一下。
也可以点点关注避免以后找不到我哦
Crossoads主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就是作者前进的动力 带你初步了解排序算法https://blog.csdn.net/2301_80191662/article/details/142211265 直接插入排序https://blog.csdn.net/2301_80191662/article/details/142300973 希尔排序https://blog.csdn.net/2301_80191662/article/details/142302553 直接选择排序https://blog.csdn.net/2301_80191662/article/details/142312028 堆排序https://blog.csdn.net/2301_80191662/article/details/142312338 冒泡排序https://blog.csdn.net/2301_80191662/article/details/142324131 快速排序https://blog.csdn.net/2301_80191662/article/details/142324307 归并排序https://blog.csdn.net/2301_80191662/article/details/142350640 计数排序https://blog.csdn.net/2301_80191662/article/details/142350741 桶排序https://blog.csdn.net/2301_80191662/article/details/142375338 基数排序https://blog.csdn.net/2301_80191662/article/details/142375592 十大经典排序算法总结与分析https://blog.csdn.net/2301_80191662/article/details/142211564
