基数排序算法实现

本文概述

• 复杂
• 例
• 算法
• C程序
• Java程序
• C＃程序

基数排序处理元素的方式与根据学生姓名的字母顺序对其排序的方式相同。在这种情况下, 由于英语中有26个字母, 因此有26个基数。在第一遍中, 根据名称的第一个字母的升序对名称进行分组。

在第二遍中, 根据第二个字母的升序对名称进行分组。继续相同的过程, 直到找到名称的排序列表。存储桶用于存储每次通过时产生的名称。通过次数取决于带有最大字母的姓名的长度。

对于整数, 基数排序会根据数字对数字进行排序。在从LSB到MSB的数字位数之间进行比较。通过的次数取决于位数最多的号码的长度。

复杂

例

考虑下面给出的长度为6的数组。使用Radix排序对数组进行排序。

A = {10, 2, 901, 803, 1024}

传递1 ：（按0位置的数字排序列表）

10, 901, 2, 803, 1024.

第二遍：（按10位数字对列表进行排序）

02, 10, 901, 803, 1024

第三遍：（按100位数字对列表进行排序）

02, 10, 1024, 803, 901.

第4遍：（按1000位数字对列表进行排序）

02, 10, 803, 901, 1024

因此, 在步骤4中生成的列表是按基数排序排列的排序列表。

算法

• 第1步：将ARR中的最大数字查找为LARGE
• 步骤2：[INITIALIZE] SET NOP =大位数
• 步骤3：SET PASS = 0
• 步骤4：在PASS <= NOP-1时重复步骤5
• 步骤5：SET I = 0并初始化值区
• 步骤6：在我重覆步骤7至9
• 第7步：在A [I]中的第PASS位设置数字位=数字
• 步骤8：将A [I]添加到编号为DIGIT的存储桶中
• 第9步：编号为DIGIT的存储桶的增量存储桶计数[LOOP结束]
• 第10步：在存储桶中收集数字[结束循环]
• 步骤11：结束

C程序

#include <stdio.h>
int largest(int a[]);
void radix_sort(int a[]);
void main()
{
	int i;
	int a[10]={90, 23, 101, 45, 65, 23, 67, 89, 34, 23}; 	
	radix_sort(a);	
	printf("\n The sorted array is: \n");
	for(i=0;i<10;i++)
		printf(" %d\t", a[i]);
}

int largest(int a[])
{	
	int larger=a[0], i;	
	for(i=1;i<10;i++)
	{
		if(a[i]>larger)
		larger = a[i];
	}
	return larger;
}
void radix_sort(int a[])
{
	int bucket[10][10], bucket_count[10];
	int i, j, k, remainder, NOP=0, divisor=1, larger, pass;
	larger = largest(a);
	while(larger>0)
	{
		NOP++;
		larger/=10;
	}
	for(pass=0;pass<NOP;pass++) // Initialize the buckets
	{
		for(i=0;i<10;i++)
		bucket_count[i]=0;
		for(i=0;i<10;i++)
		{
			// sort the numbers according to the digit at passth place			
			remainder = (a[i]/divisor)%10;
			bucket[remainder][bucket_count[remainder]] = a[i];
			bucket_count[remainder] += 1;
		}
		// collect the numbers after PASS pass
		i=0;
		for(k=0;k<10;k++)
		{
			for(j=0;j<bucket_count[k];j++)
			{
				a[i] = bucket[k][j];
				i++;
			}
		}
		divisor *= 10;
	
}
}

输出：

The sorted array is:
23
23
23
34
45
65
67
89
90
101

Java程序

public class Radix_Sort {
public static void main(String[] args) {
		int i;
		Scanner sc = new Scanner(System.in);
		int[] a = {90, 23, 101, 45, 65, 23, 67, 89, 34, 23};
		radix_sort(a);	
		System.out.println("\n The sorted array is: \n");
		for(i=0;i<10;i++)
			System.out.println(a[i]);
	}

	static int largest(inta[])
	{	
		int larger=a[0], i;	
		for(i=1;i<10;i++)
		{
			if(a[i]>larger)
			larger = a[i];
		}
		returnlarger;
	}
	static void radix_sort(inta[])
	{
		int bucket[][]=newint[10][10];
		int bucket_count[]=newint[10];
		int i, j, k, remainder, NOP=0, divisor=1, larger, pass;
		larger = largest(a);
		while(larger>0)
		{
			NOP++;
			larger/=10;
		}
		for(pass=0;pass<NOP;pass++) // Initialize the buckets
		{
			for(i=0;i<10;i++)
			bucket_count[i]=0;
			for(i=0;i<10;i++)
			{
				// sort the numbers according to the digit at passth place			
				remainder = (a[i]/divisor)%10;
				bucket[remainder][bucket_count[remainder]] = a[i];
				bucket_count[remainder] += 1;
			}
			// collect the numbers after PASS pass
			i=0;
			for(k=0;k<10;k++)
			{
				for(j=0;j<bucket_count[k];j++)
				{
					a[i] = bucket[k][j];
					i++;
				}
			}
			divisor *= 10;
		}
	}
}

输出：

The sorted array is:
23
23
23
34
45
65
67
89
90
101

C＃程序

using System;
public class Radix_Sort {
public static void Main() 
{
		int i;
		int[] a = {90, 23, 101, 45, 65, 23, 67, 89, 34, 23};
		radix_sort(a);	
		Console.WriteLine("\n The sorted array is: \n");
		for(i=0;i<10;i++)
			Console.WriteLine(a[i]);
	}

	static int largest(int[] a)
	{	
		int larger=a[0], i;	
		for(i=1;i<10;i++)
		{
			if(a[i]>larger)
			larger = a[i];
		}
		return larger;
	}
	static void radix_sort(int[] a)
	{
		int[, ] bucket=new int[10, 10];
		int[] bucket_count=new int[10];
		int i, j, k, remainder, NOP=0, divisor=1, larger, pass;
		larger = largest(a);
		while(larger>0)
		{
			NOP++;
			larger/=10;
		}
		for(pass=0;pass<NOP;pass++) // Initialize the buckets
		{
			for(i=0;i<10;i++)
			bucket_count[i]=0;
			for(i=0;i<10;i++)
			{
				// sort the numbers according to the digit at passth place			
				remainder = (a[i]/divisor)%10;
				bucket[remainder, bucket_count[remainder]] = a[i];
				bucket_count[remainder] += 1;
			}
			// collect the numbers after PASS pass
			i=0;
			for(k=0;k<10;k++)
			{
				for(j=0;j<bucket_count[k];j++)
				{
					a[i] = bucket[k, j];
					i++;
				}
			}
			divisor *= 10;
		}
	}
}

输出：

The sorted array is:
23
23
23
34
45
65
67
89
90
101