一    总述

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：

 

 

 

 

 

 

 

 

基数排序

排序原理

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

动图演示

 

 

代码演示（C++）

/************************基数排序****************************/
int MaxBit(int data[] , int n)//求data数组中的最大值的位数
{
    int maxNum = data[0];
    for(int i=1;i<n;i++)//求出data数组的最大值
    {
        if(data[i] > maxNum)
        {
             maxNum = data[i];
        }
    }
    int maxDigit = 1;
    while(maxNum/10)//求最大值有几位
    {
        maxNum /= 10;
        maxDigit++;
    }

    return maxDigit;//返回最大值的位数
}

void RadixSort(int data[] , int n)//基数排序
{
    int circle = MaxBit(data , n);//计算总循环数
    int temp[n],count[10];
    int p = 1;//除数，每次循环变化一次，以便求一个数字的不同位数上的数字
    while(circle--)
    {

        memset(count , 0 , sizeof(count));//记载数组清零
        for(int i=0;i<n;i++)//记载每个data数组元素个位数的个数，循环一次后求十位，循环两次后......
        {
            int digit = (data[i]/p) % 10;
            count[digit]++;
        }
        for(int i=1;i<n;i++)//count数组用于记录data数组元素要放在temp数组的位置。假设个位为1的数有两个，个位为2的数有三个，那么个位为1的数分别放在temp[0]和temp[1]，个位数为2的则放在temp[2],temp[3],temp[4]，以此类推
        {
            count[i]+=count[i-1];
        }
        for(int i=n-1;i>=0;i--)//将data数组元素按位分别放入temp数组中
        {
            int digit = (data[i]/p)%10;
            temp[count[digit] - 1] = data[i];
            count[digit]--;
        }
        for(int i=0;i<n;i++)//再把按位放好的temp数组元素放回data数组中
        {
            data[i] = temp[i];
            cout<<data[i]<<" ";
        }
        cout<<endl;
        p*=10;//除数×10，新一轮循环排序更高位。
    }

}
/************************************************************/

int main()
{

    int a[11]={3,2,1,6,5,4,9,8,7,1};
    int b[11]={200,6,410,51,26,98,70089,852,1265,1000};
    RadixSort(b,10);

    cout<<endl<<"最终排序结果:";
    for(int i=0;i<10;i++)
    {
        cout<<b[i]<<" ";
    }
    cout<<endl;
    return 0;
}

 

 

 

 

 

 

参考文献

全部动态图片以及部分文字转载于菜鸟教程网站：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html