- MT5(C++)软件编程十大排序算法 - 冒泡排序算法 (bubble Sort)
- MT5(C++)软件编程十大排序算法 - 选择排序算法 (select Sort)
- MT5(C++)软件编程十大排序算法 - 插入排序算法 (insert Sort)
- MT5(C++)软件编程十大排序算法 - 快速排序算法 (quick Sort)
- MT5(C++)软件编程十大排序算法 - 希尔排序算法 (shell Sort)
- MT5(C++)软件编程十大排序算法 - 堆排序算法 (heap Sort)
- MT5(C++)软件编程十大排序算法 - 归并排序算法 (merge Sort)
- MT5(C++)软件编程十大排序算法 - 计数排序算法 (counting Sort)
- MT5(C++)软件编程十大排序算法 - 桶排序算法 (bucket Sort)
- 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;
}