描述

基数排序法则是属于分配式排序， 基数排序法又称桶排序法顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些「桶」中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度O(nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。

示例

/*
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
1
2
3
4
5
6
7
8
9
10
temp
1
73
2
22
3
93
4
43
5
55
6
14
7
28
8
65
9
39
10 81
按照顺序重新排列：
81 22 73 93 43 14 55 65 28 39
再按照十位数排列：
1
2
3
4
5
6
7
8
9
10
temp
1
81
2
22
3
73
4
93
5
43
6
14
7
55
8
65
9
28
10
39
再次重排得到正确的顺序：
14 22 28 39 43 55 65 73 81 93
*/

代码实现

C++实现：

// CardinalSort.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
/*
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
1
2
3
4
5
6
7
8
9
10
temp
1
73
2
22
3
93
4
43
5
55
6
14
7
28
8
65
9
39
10 81
按照顺序重新排列：
81 22 73 93 43 14 55 65 28 39
再按照十位数排列：
1
2
3
4
5
6
7
8
9
10
temp
1
81
2
22
3
73
4
93
5
43
6
14
7
55
8
65
9
28
10
39
再次重排得到正确的顺序：
14 22 28 39 43 55 65 73 81 93
*/
int main(void) {
int data[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
int temp[10][10] = {0};
int order[10] = {0};
int i, j, k, n, lsd;
k = 0;
n = 1;
printf("n排序前: ");
for(i = 0; i < 10; i++)
printf("%d ", data[i]);
putchar('n');
while(n <= 10) {
for(i = 0; i < 10; i++) {
//拿到个位数数字
lsd = ((data[i] / n) % 10);
//将该数据存放在对应的列上，21就放在第一列，89就放在第9列
temp[lsd][order[lsd]] = data[i];
//order[lsd]表示行数，行数递增
order[lsd]++;
}
printf("n重新排列: ");
for(i = 0; i < 10; i++) {
//重新排列，先列后行
if(order[i] != 0){
//先列再行，每一行只有一个数据，每一列的数据按照行序排列
for(j = 0; j < order[i]; j++) {
data[k] = temp[i][j];
printf("%d ", data[k]);
k++;
}
}
order[i] = 0;
}
//n变为10控制转换为取十位数
n *= 10;
k = 0;
}
putchar('n');
printf("n排序后: ");
for(i = 0; i < 10; i++)
printf("%d ", data[i]);
return 0;
}

Java实现：

package com.immunize.Arithmetic;
/**
* 基数排序法
*
* @author Mr IMMUNIZE
*
*/
public class RadixSort {
public static void main(String[] args) {
int[] data = { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 };
int[][] temp = new int[10][10];
int[] order = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
int i, j, k, n, lsd;
k = 0;
n = 1;
System.out.println("排序前：");
Print(data);
System.out.println();
while (n <= 10) {
for (i = 0; i < 10; i++) {
// 拿到个位数数字
lsd = ((data[i] / n) % 10);
// 将该数据存放在对应的列上，21就放在第一列，89就放在第9列
temp[lsd][order[lsd]] = data[i];
// order[lsd]表示行数，行数递增
order[lsd]++;
}
for (i = 0; i < 10; i++) {
// 重新排列，先列后行
if (order[i] != 0) {
// 先列再行，每一行只有一个数据，每一列的数据按照行序排列
for (j = 0; j < order[i]; j++) {
data[k] = temp[i][j];
k++;
}
}
order[i] = 0;
}
n *= 10;
k = 0;
}
System.out.println("排序后：");
Print(data);
}
public static void Print(int[] number) {
for (int i = 0; i < number.length; i++) {
System.out.print(number[i] + " ");
}
}
}

最后

以上就是俊逸故事为你收集整理的20191015：基数排序法描述示例代码实现的全部内容，希望文章能够帮你解决20191015：基数排序法描述示例代码实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。