排序算法9：基数排序

基数排序算法是一种有趣的排序算法。因为这种排序不是基于比较，而是基于存储桶。

基数排序是一种线性排序算法。通过次数取决于阵列中最大数目中的位数。

以下是在Radix排序中要执行的步骤。

第1步： 我们知道0到9之间有10位数字。

因此，我们将10个标记为0到9的存储桶存储为已排序的数字。

第2步： 然后，我们将在给定列表中使用最大数量。然后，我们将从最右边的数字开始算法，并将其放入适当的编号存储桶中。

第三步： 一旦将所有元素放入特定的存储桶中，我们将把它们取出并按照它们的最低有效位排序排列，这样就完成了第一遍。

步骤4： 然后，我们将重复步骤2和3，直到所有遍均完成。

下面是实现相同的算法可视化：

我们的未排序数组：{10，15，1，60，5，100，25，50}

在这里，100是最高的元素，具有3位数字。算法最多需要3次通过。

由于最高元素有3位数字，因此我们使数组中的所有元素都具有3位数字。结果数组如下所示：

Pass 1:

{010, 015, 001, 060, 005, 100, 025, 050}

First we take the digits from 上 e’s place and place it in the according bucket.

0: 010, 060, 100, 050
1: 001, 
2:
3:
4:
5: 015, 005, 025
6:
7:
8:
9:
Sorted array:
{010, 060, 100, 050, 001, 015, 005, 025}

Pass 2:

我们将10的位置放到相应的存储桶中：

{010, 060, 100, 050, 001, 015, 005, 025}

0:100, 001, 005
1: 010, 015, 
2: 025
3:
4:
5: 050, 
6:060, 
7:
8:
9:
Sorted array: {100, 001, 005, 010, 015, 025, 050, 060}

Pass 3:

最后，我们在所有数字中排第100位。

{100, 001, 005, 010, 015, 025, 050, 060}

0:001, 005, 010, 015, 025, 050, 060
1: 100
2:
3:
4:
5: 
6:
7:
8:
9:
Final sorted array: {001, 005, 010, 015, 025, 050, 060}

解决方案在C：

#include<stdio.h>


int get_max_element(int arr[], int length)
{
	int itr;
    int max_element = arr[0];
    for (itr = 1; itr < length; itr++){
        if (arr[itr] > max_element)
            max_element = arr[itr];
    }
    return max_element;
}


void RadixSort(int arr[], int length)
{
	int max_element = get_max_element(arr, length);
	int result_array[100] = {0}; // To store intermediate sorted array
	int itr = 0;// iterator
	int digit_place = 1; // initially it will be in 1's later goes to 10's and 100's etc

	while ( (max_element/digit_place) > 0 )
	{
		int digits_bucket [10] = {0}; // we have 10 digits, hence take 10 buckets

		for (itr = 0; itr < length; itr++)
		{
			// get the digit in the digit_place and increment the counter in digits_bucket
			digits_bucket[ (arr[itr] / digit_place ) % 10 ]++; 
		}

		for (itr = 1; itr < 10; itr++)
		{
			// counting the actual count
			digits_bucket[itr] += digits_bucket[itr - 1];
		}		

		for(itr = length - 1; itr >= 0 ; itr --)
		{
			result_array[ digits_bucket[ (arr[itr]/digit_place) % 10 ] - 1] = arr[itr];
			digits_bucket[(arr[itr]/digit_place) % 10 ] --;
		}

		//copy output form temp array to original array
		for (itr = 0; itr < length; itr++)
		{
			arr[itr] = result_array[itr];
		}		

		digit_place *= 10;

	}

}

void print_array(int array[], int length)
{
	int index = 0;

	printf("The sorted array is: \n");

	for(index = 0 ; index < length ; index++)
	{
		printf("%d\n",array[index] );
	}
}


int main(int argc, char const *argv[])
{
	
	int length = 0;
	int array[100];
	int index = 0;

	printf("Enter the length of the array\n");
	scanf("%d", &length);

	printf("Enter the array elements of length %d = \n", length);

	for (index = 0; index < length; ++index)
	{
		scanf("%d", &array[index]);
	}

	RadixSort(array, length);

	print_array(array, length);

	return 0;
}

#include<stdio.h>


int get_max_element(int arr[], int length)
{
	int itr;
    int max_element = arr[0];
    for (itr = 1; itr < length; itr++){
        if (arr[itr] > max_element)
            max_element = arr[itr];
    }
    return max_element;
}


void RadixSort(int arr[], int length)
{
	int max_element = get_max_element(arr, length);
	int result_array[100] = {0}; // To store intermediate sorted array
	int itr = 0;// iterator
	int digit_place = 1; // initially it will be in 1's later goes to 10's and 100's etc

	while ( (max_element/digit_place) > 0 )
	{
		int digits_bucket [10] = {0}; // we have 10 digits, hence take 10 buckets

		for (itr = 0; itr < length; itr++)
		{
			// get the digit in the digit_place and increment the counter in digits_bucket
			digits_bucket[ (arr[itr] / digit_place ) % 10 ]++; 
		}

		for (itr = 1; itr < 10; itr++)
		{
			// counting the actual count
			digits_bucket[itr] += digits_bucket[itr - 1];
		}		

		for(itr = length - 1; itr >= 0 ; itr --)
		{
			result_array[ digits_bucket[ (arr[itr]/digit_place) % 10 ] - 1] = arr[itr];
			digits_bucket[(arr[itr]/digit_place) % 10 ] --;
		}

		//copy output form temp array to original array
		for (itr = 0; itr < length; itr++)
		{
			arr[itr] = result_array[itr];
		}		

		digit_place *= 10;

	}

}

void print_array(int array[], int length)
{
	int index = 0;

	printf("The sorted array is: \n");

	for(index = 0 ; index < length ; index++)
	{
		printf("%d\n",array[index] );
	}
}


int main(int argc, char const *argv[])
{
	
	int length = 0;
	int array[100];
	int index = 0;

	printf("Enter the length of the array\n");
	scanf("%d", &length);

	printf("Enter the array elements of length %d = \n", length);

	for (index = 0; index < length; ++index)
	{
		scanf("%d", &array[index]);
	}

	RadixSort(array, length);

	print_array(array, length);

	return 0;
}

输出：

Enter the length of the array
4
Enter the array elements of length 4 =
4
3
2
1
The sorted array is:
1
2
3
4

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：