- 技术
- C++实现基数排序
C++基数排序
#include <iostream>
#include <list>
using namespace std
;
int maxdigit(int data
[],int n
)
{
int d
= 1;
int p
= 10;
for (int i
= 0; i
< n
; i
++)
{
while (data
[i
] >= p
)
{
p
*= 10;
++d
;
}
}
return d
;
}
void RadixSort(int data
[], int len
)
{
int dig
= maxdigit(data
, len
);
list
<int> lists
[10];
for (int i
= 0,factor
=1; i
<= dig
; i
++,factor
*=10)
{
for (int j
= 0; j
< len
; j
++)
{
int k
= (data
[j
] / factor
) % 10;
lists
[k
].push_back(data
[j
]);
}
int k
= 0;
for (int j
= 0; j
< 10; j
++)
{
while (!lists
[j
].empty())
{
data
[k
++] = lists
[j
].front();
lists
[j
].pop_front();
}
}
for (int i
=0;i
<len
;i
++)
{
cout
<< data
[i
] << " ";
}
cout
<< endl
;
}
}
int main()
{
int data
[10] = { 189,12,445,64,743,986,246,54,775,666 };
RadixSort(data
, 10);
cout
<< "排序后" << endl
;
for (int i
: data
)
cout
<< i
<<" ";
cout
<< endl
;
system("pause");
return 0;
}
运行结果:
Processed:
0.039, SQL:
9
