データ構造アルゴリズムの並べ替えシリーズJava、Cソース実装(8)--基数並べ替え
ベースソート
これは前述のアルゴリズムとは全く異なるソート方法である.前述のアルゴリズムはいずれもキーワードの比較を行い,基数ソートは記録キーワード間の比較を必要としない.
チェーンベースソート
思想:低位から高位まで一度にソートのキーを割り当てて収集し、d回の割り当てと収集を経て、秩序あるシーケンスを得ることができる.
1.キーワードが10進整数であれば、個、十、百等位で分解し、基数rd=10、C 0=0、C 9=9、dは最長整数の桁数とする.
2.キーワードが小文字の英字であれば、rd＝26、C 0＝「a」、C 25＝「z」、dは文字列の最大長である.
JAvaコード:
cコード:
//基数ソート
これは前述のアルゴリズムとは全く異なるソート方法である.前述のアルゴリズムはいずれもキーワードの比較を行い,基数ソートは記録キーワード間の比較を必要としない.
チェーンベースソート
思想:低位から高位まで一度にソートのキーを割り当てて収集し、d回の割り当てと収集を経て、秩序あるシーケンスを得ることができる.
1.キーワードが10進整数であれば、個、十、百等位で分解し、基数rd=10、C 0=0、C 9=9、dは最長整数の桁数とする.
2.キーワードが小文字の英字であれば、rd＝26、C 0＝「a」、C 25＝「z」、dは文字列の最大長である.
JAvaコード:
public class RadixSort {
public static void main(String[] args) {
int array[] ={3,22,93,3,5,14,28,65,39,81,71,72,48,39,55,105,129,184,196,208};
showArray(array);
System.out.println("
");
radixSort(array,array.length);
showArray(array);
}
private static void radixSort(int[] a,int size) {
int[][] temp=new int[10][20]; // 10 0~9， 20 a size
int[] order=new int[10];
int i,j,k; //k
int n; //n=1,10,100,1000... a
int p;
n=1;
while(n <= 100)
{
for(i=0;i<size;i++)
{
k = (a[i]/n) % 10;
temp[k][order[k]] = a[i];
order[k]++;
}
p=0; //p ,a
for(i=0;i<10;i++)
{
if(order[i] != 0)
{
for(j=0;j<order[i];j++)
{
a[p] = temp[i][j];
p++;
}
order[i] = 0;
}
}
n *= 10;
}
}
private static void showArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}cコード:
//基数ソート
#include<stdio.h>
void radixSort(int *a,int size)
{
int temp[10][20]={0}; // 10 0~9， 20 a size
int order[10]={0};
int i,j,k; //k
int n; //n=1,10,100,1000... a
int p;
n=1;
while(n <= 100)
{
for(i=0;i<size;i++)
{
k = (a[i]/n) % 10;
temp[k][order[k]] = a[i];
order[k]++;
}
p=0; //p ,a
for(i=0;i<10;i++)
{
if(order[i] != 0)
{
for(j=0;j<order[i];j++)
{
a[p] = temp[i][j];
p++;
}
order[i] = 0;
}
}
n *= 10;
}
}
int main()
{
int a[20]={3,22,93,3,5,14,28,65,39,81,71,72,48,39,55,105,129,184,196,208};
int i;
radixSort(a,20);
for(i=0;i<20;i++)
printf("%d ",a[i]);
return 0;
}