基數(shù)排序思想
如果我們有N個(gè)整數(shù)递雀，范圍從1到M（或從1到M - 1）柄延，我們可以利用這個(gè)信息得到一種快速的排序，叫做桶式排序（bucket sort）缀程。我們留置一個(gè)數(shù)組搜吧，稱之為Count,大小為M市俊，并初始化為0。于是滤奈，Count有M個(gè)單元摆昧，開始時(shí)他們都是空的。當(dāng)A[i]被讀入時(shí)Count[A[i]]增1蜒程。在所有的輸入被讀進(jìn)后绅你，掃描數(shù)組Count,打印輸出排好的表。
代碼實(shí)現(xiàn)（C語(yǔ)言）
LMD（最低位優(yōu)先法）
#include<stdio.h>
#include<math.h>
int main(void)
{
int a [] = {3,15,18,10,34,20,13,20,100,254,486,598 };
int * p = a;
//計(jì)算數(shù)組長(zhǎng)度
int size = sizeof(a) / sizeof(int);
//基數(shù)排序
bucketSort3(p,size);
//打印排序結(jié)果
int i;
for(i = 0; i < size; i++)
printf("%d\n",a[i]);
return 0;
}
//基數(shù)排序
void bucketSort3(int * p, int n)
{
//獲取數(shù)組中的最大數(shù)
int maxNum = findMax(p,n);
//獲取分配次數(shù)
int times = getTimes(maxNum);
int i;
printf("times:%d\n",times);
for(i = 1; i <= times; i++)
sort2(p,n,i);
}
int getTimes(int num)
{
int count = 1;
int temp = num / 10;
while(temp != 0)
{
count++;
temp= temp / 10;
}
return count;
}
int findMax(int * p,int n)
{
int i;
int max = 0;
for(i = 0;i < n; i++)
{
if (p[i] > max)
max = p[i];
}
return max;
}
//將數(shù)字按位數(shù)分配到各自的桶中搞糕，按桶的順序輸出排序結(jié)果
void sort2(int * p,int n, int loop)
{
// 預(yù)設(shè)桶的大小
int buckets[10][20] = {};
int tempNum = (int)pow(10,loop - 1);
int i,j;
for(i = 0; i < n; i++ )
{
int index = (p[i] / tempNum) % 10;
for(j = 0; j < 20; j++)
{
if(buckets[index][j] == NULL)
{
buckets[index][j] = p[i];
break;
}
}
}
//將桶中的數(shù)勇吊，倒回到原有數(shù)組中
int k = 0;
for (i = 0; i < 10; i++)
{
for (j = 0; j < 20; j++)
{
if (buckets[i][j] != NULL)
{
p[k] = buckets[i][j];
buckets[i][j] = NULL;
k++;
}
}
}
}
測(cè)試結(jié)果
image.png
