基数用C排序++实现 [英] Radix Sort implemented in C++
问题描述
更新：我设法从头开始重新工作，我的code，这里是我想出了。它的工作原理，但唯一的问题是速度。有没有什么办法，我可以用更好的内存管理，加快我目前的设置？如果是这样，这将是最好的方法？
的#include＆LT;的iostream＆GT;
＃包括＆LT;载体＆GT;
＃包括＆LT;文件math.h＆GT;
使用名字空间std;
无效printSorted（INT X []，INT的长度）;
矢量＆lt;矢量＆lt; int的＆GT; ＆GT;桶;
无效radixSort（INT X []，INT的长度）{
INT温度;
INT米= 0;
//开始基数排序
的for（int i = 0;我7;;我++）{
//确定哪个桶的每个元素应该进入
对于（INT J = 0; J＆LT;长度; J ++）{
临时=（INT）（（X [J]）/ POW（10，I））％10;
水桶[临时] .push_back（（X [J]））;
}
//将水桶的结果返回到主阵列
为（中间体K = 0; K＆小于10; k ++）{
为（中间体升= 0; L＆其中;桶[k]的.size（）;升++）{
X [米] =水桶[k]的[升];
M +;
}
//清除previous桶
水桶[k]的.clear（）;
}
米= 0;
}
buckets.clear（）;
printSorted（X，长度）;
}
无效printSorted（INT X []，INT的长度）{
的for（int i = 0; I＆LT;长度;我++）
的cout＆其中;＆其中; X [1] - ;＆所述; ENDL;
}
诠释的main（）{
INT测试案例;
CIN＆GT;＆GT;测试用例;
INT输入[测试用例]
buckets.resize（10）;
INT编号;
的for（int i = 0; I＆LT;测试用例;我++）{
CIN＆GT;＆GT;数;
输入[I] =号;
}
radixSort（输入，测试用例）;
返回0;
}
我觉得你狠狠过于复杂的解决方案。您可以使用输入接收一个数组，通过索引，标志着输入数组中每个桶的起始索引的数组psented每一步重新$ P $水桶实施基数。
事实上，你甚至可以做到这一点递归的：
//排序尺寸编号整数开始在输入根据digit'th位
//对于参数数字，0表示至少显著数字和随意义不
无效radixSort（INT *输入，诠释大小，INT位）
{
如果（大小== 0）
返回;
INT [10]水桶; //假设小数
//排序数组中的位置，同时跟踪桶开始指数。
//如果桶[i]的意思是空的（我没有数字在指定的数字），
//然后让桶[I + 1] =斗[I]
对（INT I = 0; I＆小于10; ++ i的）
{
radixSort（输入+水桶[I]，水桶[I + 1] - 料斗[I]中，数字+ 1）;
}
}
当然桶[I + 1] - 桶[I] 会导致缓冲区溢出，当我是9，但我省略了额外的检查和可读性的缘故;我相信你知道如何处理。
通过这一点，你只需要调用 radixSort（测试用例，的sizeof（测试用例）/ sizeof的（测试用例[0]），0）和阵列应当加以分类。
UPDATE: I managed to re-work my code from scratch, and here is what I came up with. It works, but the only problem is speed. Is there any way that I can speed up my current set up using better memory management? If so, what would be the best approach?
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
void printSorted(int x[], int length);
vector < vector <int> > buckets;
void radixSort(int x[],int length){
int temp;
int m=0;
//Begin Radix Sort
for(int i=0;i<7;i++){
//Determine which bucket each element should enter
for(int j=0;j<length;j++){
temp=(int)((x[j])/pow(10,i))%10;
buckets[temp].push_back((x[j]));
}
//Transfer results of buckets back into main array
for(int k=0;k<10;k++){
for(int l=0;l<buckets[k].size();l++){
x[m]=buckets[k][l];
m++;
}
//Clear previous bucket
buckets[k].clear();
}
m=0;
}
buckets.clear();
printSorted(x,length);
}
void printSorted(int x[], int length){
for(int i=0;i<length;i++)
cout<<x[i]<<endl;
}
int main(){
int testcases;
cin>>testcases;
int input[testcases];
buckets.resize(10);
int number;
for(int i=0;i<testcases;i++){
cin>>number;
input[i]=number;
}
radixSort(input,testcases);
return 0;
}
I think you're severely overcomplicating your solution. You can implement radix using the single array received in the input, with the buckets in each step represented by an array of indices that mark the starting index of each bucket in the input array.
In fact, you could even do it recursively:
// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
if (size == 0)
return;
int[10] buckets; // assuming decimal numbers
// Sort the array in place while keeping track of bucket starting indices.
// If bucket[i] is meant to be empty (no numbers with i at the specified digit),
// then let bucket[i+1] = bucket[i]
for (int i = 0; i < 10; ++i)
{
radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
}
}
Of course buckets[i+1] - buckets[i] will cause a buffer overflow when i is 9, but I omitted the extra check or readability's sake; I trust you know how to handle that.
With that, you just have to call radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0) and your array should be sorted.
这篇关于基数用C排序++实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
