基数排序
- 时间复杂度：平均、最好、最坏都为O(k*n),其中k为常数，n为元素个数
- 空间复杂度：O(n+k)
- 稳定性：稳定
算法解析：
- 基数排序的思想就是先排好各位，然后排好各位的基础上排十位，以此类推，直到遍历最高位 次，排序结束（仔细理解最后一句话）
- 基数排序不是比较排序，而是通过分配和收集的过程来实现排序
- 初始化10个桶(固定的)，桶下标为0-9
- 通过得到待排序数字的个十百等位的数字，把这个数字对应的item放到对应的桶中
- 基数排序有两种排序方式：LSD和MSD，最小位优先(从右边开始)和最大位优先(从左边开始)
动画演示
radixSort.gif
OC代码实现 LSD
- (void)radixSort:(NSMutableArray *)arr {// [@1,@2,@19,...]
NSNumber *max = arr[0];
for (NSNumber *num in arr) {
if ([num intValue] > [max intValue]) {
max = num;
}
}
int position = 0;
int maxDigital = [max intValue];
while (maxDigital > 0) {
maxDigital /= 10;
position++;
}
NSMutableArray *arrMutable = [NSMutableArray array];
for (int i = 0; i<10; i++) {
[arrMutable addObject:[NSMutableArray array]];
}
int divisor = 1;//除数
for (int i = 0; i<position; i++) {
for (NSNumber *n in arr) {
int digital = [n intValue];
int lastN = (digital/divisor)%10;
[((NSMutableArray *)arrMutable[lastN]) addObject:n];
}
int increase = 0;
for (int j = 0; j<arrMutable.count; j++) {
for (int k = 0; k<((NSArray *)arrMutable[j]).count; k++) {
arr[increase] = arrMutable[j][k];
increase++;
}
}
[arrMutable makeObjectsPerformSelector:@selector(removeAllObjects)];
divisor *= 10;
}
}
Swift实现 LSD
func radixSort(arr : inout [Int]) -> Void {
//0-9，10个桶
var bucket = [[Int]]()
for _ in 0..<10 {
bucket.append([Int]())
}
//获取最大值
var max = 0
for (_,item) in arr.enumerated() {
if max < item {
max = item
}
}
//获取最高位
var position = 0
while max > 0 {
max = max / 10
position += 1
}
var divisor = 1
var num = 0//位上的数字
for _ in 0..<position {
for (_,item) in arr.enumerated() {//入桶
num = (item / divisor) % 10
bucket[num].append(item)
}
//遍历完成，需要重置arr
var k = 0
for i in 0..<bucket.count {//把有数据的桶串起来
while !bucket[i].isEmpty {
arr[k] = bucket[i].remove(at: 0)
k += 1
}
}
divisor = divisor * 10 //位：1 10 100
}
}
以下代码实现均来源于网络，未验证
c++实现
/*
*求数据的最大位数,决定排序次数
*/
int maxbit(int data[], int n)
{
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[n];
int count[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;
}
JavaScript 代码实现
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]==null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
return arr;
}
Java 代码实现
public class RadixSort {
private static void radixSort(int[] array,int d)
{
int n=1;//代表位数对应的数：1,10,100...
int k=0;//保存每一位排序后的结果用于下一位的排序输入
int length=array.length;
int[][] bucket=new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
int[] order=new int[length];//用于保存每个桶里有多少个数字
while(n<d)
{
for(int num:array) //将数组array里的每个数字放在相应的桶里
{
int digit=(num/n)%10;
bucket[digit][order[digit]]=num;
order[digit]++;
}
for(int i=0;i<length;i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
{
if(order[i]!=0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
{
for(int j=0;j<order[i];j++)
{
array[k]=bucket[i][j];
k++;
}
}
order[i]=0;//将桶里计数器置0，用于下一次位排序
}
n*=10;
k=0;//将k置0，用于下一轮保存位排序结果
}
}
php实现
function radixSort($arr, $maxDigit = null)
{
if ($maxDigit === null) {
$maxDigit = max($arr);
}
$counter = [];
for ($i = 0; $i < $maxDigit; $i++) {
for ($j = 0; $j < count($arr); $j++) {
preg_match_all('/\d/', (string) $arr[$j], $matches);
$numArr = $matches[0];
$lenTmp = count($numArr);
$bucket = array_key_exists($lenTmp - $i - 1, $numArr)
? intval($numArr[$lenTmp - $i - 1])
: 0;
if (!array_key_exists($bucket, $counter)) {
$counter[$bucket] = [];
}
$counter[$bucket][] = $arr[$j];
}
$pos = 0;
for ($j = 0; $j < count($counter); $j++) {
$value = null;
if ($counter[$j] !== null) {
while (($value = array_shift($counter[$j])) !== null) {
$arr[$pos++] = $value;
}
}
}
}
return $arr;
}
