欢迎光临
我们一直在努力

MT5(C++)软件编程-基数排序算法

  1. MT5(C++)软件编程十大排序算法 - 冒泡排序算法 (bubble Sort)
  2. MT5(C++)软件编程十大排序算法 - 选择排序算法 (select Sort)
  3. MT5(C++)软件编程十大排序算法 - 插入排序算法 (insert Sort)
  4. MT5(C++)软件编程十大排序算法 - 快速排序算法 (quick Sort)
  5. MT5(C++)软件编程十大排序算法 - 希尔排序算法 (shell Sort)
  6. MT5(C++)软件编程十大排序算法 - 堆排序算法 (heap Sort)
  7. MT5(C++)软件编程十大排序算法 - 归并排序算法 (merge Sort)
  8. MT5(C++)软件编程十大排序算法 - 计数排序算法 (counting Sort)
  9. MT5(C++)软件编程十大排序算法 - 桶排序算法 (bucket Sort)
  10. MT5(C++)软件编程十大排序算法 - 基数排序算法 (radix Sort)

基数排序算法(radix Sort)
以二分之一分递归分割数组
arr: 需要排序的数组
seq: 排序的方向, true 为升序, false为降序

template < typename T>
void radixSort(T &data[]) //基数排序
{     
    int len = ArraySize(data);
    int d = maxbit(data, len);
    T tmp[];
    ArrayResize(tmp, len);
    int count[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < len; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = len - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < len; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
}

template < typename T>
int maxbit(T &data[], int n) //辅助函数,求数据的最大位数
{
    int maxData = data[0];              ///< 最大数
    /// 先求出最大数,再求其位数,这样有原先依次每个数判断其位数,稍微优化点。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        //p *= 10; // Maybe overflow
        maxData /= 10;
        ++d;
    }
    return d;
}


int merge_min(int x, int y) {
    return x < y ? x : y;
}

int merge_max(int x, int y) {
    return x > y ? x : y;
}
 收藏 (0) 打赏

您可以选择一种方式赞助本站

支付宝扫一扫赞助

微信钱包扫描赞助

未经允许不得转载:瓜皮猫量化编程 » MT5(C++)软件编程-基数排序算法
分享到: 生成海报

评论 抢沙发

瓜皮猫量化交易编程

QQ群: 492653640微信: guapitcom
切换注册

登录

忘记密码 ?

切换登录

注册

我们将发送一封验证邮件至你的邮箱, 请正确填写以完成账号注册和激活