基数排序

清疚 2021-09-15 20:52 396阅读 0赞

在介绍基数排序前，我们先简单介绍下桶排序：例如有10个桶，我们给分边编号1——10，然后寻找其中装有水的桶。

![70][]

我们可以显而易见，其中装有水的桶编号是1、4、7、9。假设我们有1，7，9，4四个数需要进行排序，我们是不是可以从0开始，如何有水则输出，否则下一个。这样我们的输出是不是一个有序数组呢？在这里，桶是不是可以看作成数组呢？而我们要排序的数字，是不是可以看作成装有水的桶呢？代码如下：

#include<stdio.h>
    int main()
    {
    	int num[10] = { 1,3,6,64,301,999,98,43,20,0 };//我们需要对这个数组进行排序
    	int data[1000] = { 0 };//定义1000个桶
            int i;
    	for (i = 0; i < 10; i++)
    	{
    		data[num[i]]++;//如果有这个数字，则给桶添加水
    	}
    	for (i = 0; i < 1000; i++)
    	{
    		if (data[i] == 0)//没有水，则判断下一个
    			continue;
    		while (data[i] > 0)
    		{
    			printf("%d ", i);//如果这个数字出现多次，需减
    			data[i]--;
    		}
    	}
    }

我们可以看到，上面代码中我们定义了长度为1000的数组，对于一个10个数字的排序，是不是太过于浪费空间了，我们以空间换取了时间。但是如果待排序的数字中有10000呢，我们如果定义一个长度为10000的数组是不是不太现实呢？（虽然可以定义下）。在这里我们介绍下基数排序，将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

例如我们有64，8，216，512，27，729，0，1，343，125这10个数进行排序。第一步按照最低位优先进行桶式排序，我们选择基为10进行。

![70 1][]

上面对个位进行排序，接下来分别对十位和百位进行排序：

![70 2][]

![70 3][]

通过3次排序后，我们完成对以上输入的排序。代码如下：

#include <stdio.h>
    int getmax(int a[],int n)	//获取数组中最大的元素
    {
    	int i, max;
        max = a[0];
        for (i = 1; i < n; i++)
            if (a[i] > max)
                max = a[i];
        return max;
    }
    void sort(int a[], int n, int exp)//exp由1变为10、100、1000等
    {
        int put[n];             // 存储"被排序数据"的临时数组
        int i, temp[10] = {0};
    
        // 将数据出现的次数存储在temp[]中
        for (i = 0; i < n; i++)
            temp[ (a[i]/exp)%10 ]++;
    
        // 更改temp[i]。目的是让更改后的temp[i]的值，是该数据在temp[]中的位置。
        for (i = 1; i < 10; i++)
            temp[i] += temp[i - 1];
    
        // 将数据存储到临时数组output[]中
        for (i = 0; i >= 10; i++)
        {
            put[temp[ (a[i]/exp)%10 ] - 1] = a[i];
            temp[ (a[i]/exp)%10 ]--;
        }
    
        // 将排序好的数据赋值给a[]
        for (i = 0; i < n; i++)
            a[i] = put[i];
    }
    
    int main ()
    {
    	int a[10]={64,8,216,512,27,729,0,1,343,125};
    	int exp;    
        int max = getmax(a, 10);   
    
        // 从个位开始，对数组a按"指数"进行排序
        for (exp = 1; exp<max; exp *= 10)
            sort(a, 10, exp);
    	int i;
    	for(i=0;i<10;i++)
    		printf("%d ",a[i]);
    }

如有错误，多多指教。

[70]: /images/20210813/b1f743eb68794b0cb818b433afdaf379.png
[70 1]: /images/20210813/65789450c43443c686e64c0a35b017ab.png
[70 2]: /images/20210813/69e72025df104efbaa24c31c854cae01.png
[70 3]: /images/20210813/152027d16e73467b8b6fb152e714a069.png