存储器类型及DDR相关简介

---

—基数排序—

​ 基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为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