基数排序

  1. —基数排序—
    1. 算法描述
    2. 代码实现
    3. 算法分析
    4. 稳定性

—基数排序—

​ 基数排序也是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数;

算法描述

具体算法描述如下:

  • <1>.取得数组中的最大数,并取得位数;

  • <2>.arr为原始数组,从最低位开始取每个位组成radix数组;

  • <3>.对radix进行计数排序(利用计数排序适用于小范围数的特点);

基数排序

代码实现

int Max_Radix(int a[], int n)    //辅助函数,求数据的最大位数
{
    int max = a[0];                /// 最大数
    for (int i = 1; i < n; ++i)      /// 先求出最大数,再求其位数,这样有原先依次每个数判断其位数
    {
        if (a[i] > max)
            max = a[i];
    }

    int count = 1;              //用于判断之后循环几次
    while ((max/=10) != 0)    
        count++;
    return count;
}


void Radix_Sort(int a[],int n)   //基数排序 类似于计数排序
{
    int count = Max_Radix(a, n);    //count =2
    int* temp = new int[n];         //存放临时数组
    int* index = new int[10];        // 计数器 0~9
    int p = 1;                //先从个位开始
    for (int i = 1; i <= count;++i)    //进行count次排序
    {
        for (int i = 0; i < 10; ++i)
            index[i] = 0;
    
        for (int i = 0; i < n; ++i)
            index[(a[i] / p) % 10]++;    

        for (int i = 1; i < 10; ++i)
            index[i] += index[i - 1];

        for (int i = 0; i < 10; ++i)      
            cout << index[i] << " ";
        cout << endl;

        for (int i =n-1; i >=0 ; --i)   // 一定从后往前遍历,这样不会乱序 从前往后会乱序。
        {
            temp[index[(a[i] / p) % 10] - 1] = a[i];  //注意不能写成  index[((a[i] / p) % 10)] - 1] 形式
            index[(a[i] / p) % 10]--;
        }

        for (int i = 0; i <n; i++)
            a[i] = temp[i];
        p *= 10;
    }
}

算法分析

  • 平均情况:T(n) = O(n * k)

  • 最佳情况:T(n) = O(n * k)

  • 最差情况:T(n) = O(n * k)

稳定性

  • 稳定

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 351134995@qq.com

×

喜欢就点赞,疼爱就打赏