[周一要去YY面试]100万个数据，数据值在0~65535之间，请用尽可能少的内存和最快的速度从小到大排序 这个题如何解呀，求大侠们打救小弟我一下，应届生苦B
[周一要去YY面试]100万个数据，数据值在0~65535之间，请用尽可能少的内存和最快的速度从小到大排序 这个题怎么解呀，求大侠们打救我一下，应届生苦B啊
100万个数据，数据值在0~65535之间，请用尽可能少的内存和最快的速度从小到大排序
------解决方案--------------------
楼上说得对，数据在哪里，这点很重要。
少占内存，如果数据已经在内存，那就建议用快速排序。不要用一般的递归算法，因为数据范围小（0-65535），容易造成堆栈溢出。我以前写过一个非递归的快速排序，考虑了几个方面：
1、堆栈尽可能小；
2、对已排好序的数据不要再浪费时间。
（后面代码中的QuickSort）
如果数据是放在其他地方（比如数据文件），因为数值只有0-65535，所以可以开个数组来计数，计算各个数值的个数，然后按照这个计数从小到大输出。只需要遍历一次数据。
（后面代码中的MySort）
------解决方案--------------------
晕S，没改完整，还存在UINT。重新传过。
100万个数据，数据值在0~65535之间，请用尽可能少的内存和最快的速度从小到大排序
------解决方案--------------------
楼上说得对，数据在哪里，这点很重要。
少占内存，如果数据已经在内存，那就建议用快速排序。不要用一般的递归算法，因为数据范围小（0-65535），容易造成堆栈溢出。我以前写过一个非递归的快速排序，考虑了几个方面：
1、堆栈尽可能小；
2、对已排好序的数据不要再浪费时间。
（后面代码中的QuickSort）
如果数据是放在其他地方（比如数据文件），因为数值只有0-65535，所以可以开个数组来计数，计算各个数值的个数，然后按照这个计数从小到大输出。只需要遍历一次数据。
（后面代码中的MySort）
void MySort(int* pValue, int Length)
{
int* Count = new int[0x10000];
ZeroMemory(Count, 0x10000 * sizeof(int));
// 第一遍：先计算各个数值的个数
for (int i = 0; i < Length; ++i)
{
++Count[pValue[i]];// 这里简单把数字放在数组中，可以根据情况从文件中读数据
}
// 第二遍：从小到大输出数值
// 因为已经知道各个数值的个数，所以可以直接写，不必再查原来的数字
int Index = 0;
for (int value = 0; value < 0x10000; ++value)
{
for (int i = 0; i < Count[value]; ++i)
{
// 这里简单把数字写入数组中，可以根据情况把值写到文件
pValue[Index++] = value;
}
}
delete[] Count;
}
void QuickSort(int* pValue, int Length)
{
if (Length <2)
{
return;
}
int LoStack[64];
int HiStack[64];
LoStack[0] = 0;
HiStack[0] = Length - 1;
UINT Index = 1;
while (Index > 0)
{
int Lo = LoStack[--Index];
int Hi = HiStack[Index];
int Value = pValue[Lo];
int L = Lo;
int H = Hi;
while (L < H)
{
while (pValue[H] > Value && L < H)
{
--H;
}
pValue[L] = pValue[H];
while (pValue[L] <= Value && L < H)
{
++L;
}
pValue[H] = pValue[L];
}
pValue[L] = Value;
bool Equ = true;
for (int x = Lo; Equ && x < L; ++x)
{
Equ = (pValue[x] == Value);
}
if (Equ)
{
Lo = L;
}
UINT Left = L - Lo;
UINT Right = Hi - L;
if (Left < Right)
{
if (Right > 1)
{
LoStack[Index] = L + 1;
HiStack[Index++] = Hi;
}
if (Left > 1)
{
LoStack[Index] = Lo;
HiStack[Index++] = L - 1;
}
}
else
{
if (Left > 1)
{
LoStack[Index] = Lo;
HiStack[Index++] = L - 1;
}
if (Right > 1)
{
LoStack[Index] = L + 1;
HiStack[Index++] = Hi;
}
}
}
}
int main()
{
int Length = 1000000;
int* Value = new int[Length];
srand(GetTickCount());
for (int i = 0; i < Length; ++i)
{
Value[i] = ((rand() & 0xFF) << 8)
------解决方案--------------------
(rand() & 0xFF);//数值在0-65535之间
}
QuickSort(Value, Length);
for (int i = 1; i < Length; ++i)
{
if (Value[i - 1] > Value[i])
{
printf_s("QuickSort: (Value[%d]=%d) > (Value[%d]=%d)\n", i - 1, Value[i - 1], i, Value[i]);
system("pause");
}
}
printf_s("QuickSort Completed\n");
srand(GetTickCount());
for (int i = 0; i < Length; ++i)
{
Value[i] = ((rand() & 0xFF) << 8)
------解决方案--------------------
(rand() & 0xFF);//数值在0-65535之间
}
MySort(Value, Length);
for (int i = 1; i < Length; ++i)
{
if (Value[i - 1] > Value[i])
{
printf_s("MySort: (Value[%d]=%d) > (Value[%d]=%d)\n", i - 1, Value[i - 1], i, Value[i]);
system("pause");
}
}
printf_s("MySort Completed\n");
delete[] Value;
system("pause");
}
------解决方案--------------------
晕S，没改完整，还存在UINT。重新传过。
void MySort(int* pValue, int Length)
{