求数组按元素重复出现次数多少重新排列算法（200分） ( 积分: 200 )

有一个巨型数组，元素为泛型数据（可能是字符串，也可能是指针...），现要求按元素重复出现次数的多少进行重新排列，要求不用数据库的SQL查询（很慢...），数组中的元素可能超过一千万个，请高手给段代码指点迷津，效率第一，谢谢！
另：不必告诉我先排序再求重复，因为元素不便于排序，只能按重复次数进行重新排列。

首先定义一个记录链表
record:
元素名:泛型数据
出现次数：integer;
pev:指针;
next:指针
首先查找元素出现的次数，并存在记录链表中。然后对链表按出现次数进行排序。
根据记录链表中的元素再从巨型数组中查找记录链表中的数据进行移位操作逐步将重复元素
排列在一起。

感谢ww20000309参与探讨，但这样的效率恐怕很低，1000万个元素查找出现次数，然后排序，再移动元素....实在不敢想像需要消耗的时间

借鉴分批提交批量数据库数据的思想，
我觉得，把大数组分成一千个小的，或一百个，
先对每一个小的数组进行次数分析，再进行最后大的归并工作。
再提个建议可否把最终的一个数组变成一个二维数组或用两个数组来表示。
比如
array: [a,a,a,a,a,a,b,b,b,b,b,c,c,c,c]
表示成：
array_1: [a,b,c] ：数组元素
array_2: [6,5,4] ：数组元素对应的次数
两个数组来表示，
这样可以减少很多内存空间。

构造哈希表来处理，只要做一次扫描，时间复杂度接近O。对于元素个数远远大于元素种类时更是合适。扫描到每一元素时做两个操作，计数；进相应的表。
在哈希表构造完成后，按照元素种类的出现频度对哈希表进行排序。排序时间复杂度做到O(nlgn)是很容易的，而且此n已不再是元素个数，而是元素种类的个数了。
最后将排好序的哈希展开既可。

干脆进一步降低要求吧，元素的重复次数就不需要统计了，只需要将相同的元素重新排列在一起就可以了，重新排列后，重复次数可以在下一步处理，数组遍历一次即可得到，请对算法精通的朋友给个相同元素重排在一起的实例，谢谢！

不排序的话只要将第一步中的"计数;进相应的表"改为仅进相应的表,再去掉整个第二步就可以了.
不过,你既然迟早是要完成排序,不如就在第二步中排了,比你重新排列后再扫描要快多了.

十分感谢LeeChange版主，俺对算法实在很菜，对哈希表更是一无所知（汗～），版主能否百忙中抽空给点代码学习学习？

以下是找到的delphi下的hashtable单元，哪位达人能帮忙针对我的问题给出个应用实例？本人水平实在有限，没搞懂该如何应用。
Hashtable.pas
--------------------------------------------------------------------------------
unit Hashtable;
interface
uses SysUtils, Classes;
type
{ THashTable }
PPHashItem = ^PHashItem;
PHashItem = ^THashItem;
THashItem = record
Next: PHashItem;
Key: string;
Value: String;
end;

THashTable = class
private
Buckets: array of PHashItem;
protected
function Find(const Key: string): PPHashItem;
function HashOf(const Key: string): Cardinal;
virtual;
public
constructor Create(Size: Integer = 256);
destructor Destroy;
override;
procedure Put(const Key: string;
Value: String);
procedure Clear;
procedure Remove(const Key: string);
function Modify(const Key: string;
Value: String): Boolean;
function Get(const Key: string): String;
end;

implementation
{ THashTable }
procedure THashTable.Put(const Key: string;
Value: String);
var
Hash: Integer;
Bucket: PHashItem;
begin
Hash := HashOf(Key) mod Cardinal(Length(Buckets));
New(Bucket);
Bucket^.Key := Key;
Bucket^.Value := Value;
Bucket^.Next := Buckets[Hash];
Buckets[Hash] := Bucket;
end;

procedure THashTable.Clear;
var
I: Integer;
P, N: PHashItem;
begin
for I := 0 to Length(Buckets) - 1do
begin
P := Buckets;
while P <> nildo
begin
N := P^.Next;
Dispose(P);
P := N;
end;
Buckets := nil;
end;
end;

constructor THashTable.Create(Size: Integer);
begin
inherited Create;
SetLength(Buckets, Size);
end;

destructor THashTable.Destroy;
begin
Clear;
inherited;
end;

function THashTable.Find(const Key: string): PPHashItem;
var
Hash: Integer;
begin
Hash := HashOf(Key) mod Cardinal(Length(Buckets));
Result := @Buckets[Hash];
while Result^ <> nildo
begin
if Result^.Key = Key then
Exit
else
Result := @Result^.Next;
end;
end;

function THashTable.HashOf(const Key: string): Cardinal;
var
I: Integer;
begin
Result := 0;
for I := 1 to Length(Key)do
Result := ((Result shl 2) or (Result shr (SizeOf(Result) * 8 - 2))) xor
ord(Key);
end;

function THashTable.Modify(const Key: string;
Value: String): Boolean;
var
P: PHashItem;
begin
P := Find(Key)^;
if P <> nil then
begin
Result := True;
P^.Value := Value;
end
else
Result := False;
end;

procedure THashTable.Remove(const Key: string);
var
P: PHashItem;
Prev: PPHashItem;
begin
Prev := Find(Key);
P := Prev^;
if P <> nil then
begin
Prev^ := P^.Next;
Dispose(P);
end;
end;

function THashTable.Get(const Key: string): String;
var
P: PHashItem;
begin
P := Find(Key)^;
if P <> nil then
Result := P^.Value else
Result := '';
end;
end.

顶，希望LeeChange版主和其他朋友能指点一下[]

元素的值都长什么样啊?不知道的话不好设计哈希函数.
另外,&quot;扫描到每一元素时做两个操作，计数；进相应的表。&quot;进相应表的操作可以不要了,直接记下频度就可以.

元素的值必须唯一才能使用哈希 吧

感谢LeeChange版主！
元素的定义：
type
Myel:array of Integer;
Myel的长度在所有元素中是相同的，但每次使用中可能不同，所以需要在hashtable中设定这个长度

To kk2000:
hashtable应该是key的值是唯一[]

用hashtable测试了一下，不知道是hash函数的原因还是其他的问题，往hashtable中通过key索引并赋值，大量数据操作下，非常缓慢，在前述单元没有作太多改动的情况下，作如下测试：
...
Myhash:Thashtable;
....
Myhash:=Thashtable.create(1000000);//初始化table可容纳一百万个元素
for i:=0 to 999999do
Myhash.put(inttostr(i),i);
//填充表，其中表的值已经改为元素可能出现的次数，整型，key设置为元素值，暂时设置为string类型，因为元素的可能值是恒定的，在下次添加元素时根据元素值对应的key，将出现次数＋1，全部元素添加完毕后，其重复出现的次数统计也就完成了。
for i:=1 to 10do
for j:=0 to 999999do
Myhash.modify(inttostr(j),Myhash.get(inttostr(j))+1);//测试添加元素，如果找到该元素，将出现记数＋1，10次循环测试。
在这种情况下，速度非常缓慢，一千万个元素下，耗时约120″，不能接受，不知道版主和各位朋友有什么更好的解决办法？或者是我对hashtable的应用有不当的地方？

思考了一下这个问题本身，要取得数组内符合重复次数范围的元素，应该只要将所有元素中相同的都排列在一起（可以不管大小顺序），然后一次遍历数组就可以得到结果。但本人算法设计能力有限，不知道在这么巨大的数组中，怎样快速实现相同元素的重排？请大家指点。

大富翁帖子沉的快，自己顶一下

对于没有排过序的数据，我觉得120秒已经是不错的结果了。
数据库之所以能够在很短的时间内从海量数据中准确找到数据，前提之一就是事先做好了各式各样的索引，也就是排过序了。
我的一点愚见，如果楼主认为有理，就可以不再在上面花工夫了。

to: arhaha
你好，还记得我吗。。。呵呵

To arhaha：
您的说法我同意，但针对这个特定的数学模型，我相信应该有比较好的解决办法，只是本人对数据结构和算法不太在行，所以想请教一下数据结构版块的高手。