求快速排序方法(100分)

一个记录集：
Type TMyRec = Record
Num:array[1..4000000] of Integer;//存放序号
Strs:array[1..4000000] of String[11];//字符串
eValue:array[1..4000000] of Extended;//计算用
end;
....
上述记录假定已经有了以下数据：
Num strs eValue
1 13112025487 0.5457
2 13324589717 11.2287
3 13023548465 6.2588
...
112021 13321548752 1.8545
...
要求：
1.按eValue降序排序得到如下结果：
Num strs eValue
1 13324589717 11.2287
2 13023548465 6.2588
3 13321548752 1.8545
4 13112025487 0.5457
...
2.查找 strs = '13321548752' 并求得序号为 3
那位大侠能提供快速排序及查找的算法，最好有源码。

400W那
mark一下

曾经尝试用数据库做，但太慢，只好放弃。

数据库加了索引还慢？不会吧老兄，400W来说相对正常

private
TL:TList;
//排序规则
function CompareNames(Item1, Item2: Pointer): Integer;
begin
Result := CompareText(PFC(Item1).FileName, PFC(Item2).FileName);
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
TL.Sort(CompareNames);
for i:=0 to TL.Count-1 do ...
end;

数据库中加索引排序相当快，没有问题，但是在往里添加数据或编辑数据时（上述的eValue每次都得重新生成），速度可慢的跟牛一样。

1.用插入法排序，用指针保存，这样对大量数据应该最好，循环一次排好序。
2.为了快速按strs读取，做一张按strs排序的索引，用1的方法。然后采用二分法定位。

To dey-999：
Tlist.Sort后,寻找原序号是否得遍历一遍，没试过，一会试试...

>>做一张按strs排序的索引
czcn,如果做索引？学习学习

To czcn:
能给出源码说明一下吗？谢谢！

400W*8Byte
4,000,000
SizeOf(TMyRec) = 25
光这个全部弄出来要100M的内存了，呵呵，如果量再多点你就得加内存了，呵。
将手机号弄成Int64来处理吧，少几个字节。

To errorcode:
单位机器内存2G，没问题，以内存空间换取速度！

基本的算法
http://www.delphibbs.com/delphibbs/dispq.asp?lid=3582791

你这个record定义得可用性很差，strs与value其实是一一对应的，而num在排序后还会变

冒泡不行吗``乾坤大挪移唉``

unit u_QuickSort;

interface



uses
sysUtils,classes,Dialogs;




type
TtdCompareFunc = function (aData1, aData2 : pointer) : Longint; {函数类型}



procedure QSS(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
{-基本QuickSort}



procedure TDQuickSortStd(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
{-基本QuickSort的驱动过程}





procedure QSNR(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
{-非递归QuickSort}
procedure TDQuickSortNoRecurse(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
{-非递归QuickSort的驱动过程}




procedure QSR(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
{-随机支点的Quicksort}
procedure TDQuickSortRandom(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
{-随机支点的Quicksort的驱动过程}




procedure TDQuickSortMedian(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
{-3个支点QuickSort的驱动过程}




procedure QSInsertionSort(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
{-为究极QuickSort服务的InsertionSort}
procedure QS(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
{-究极QuickSort}



procedure TDQuickSort(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
{-究极QuickSort的驱动过程}





{比较例程}
{检查范围的过程}
procedure TDValidateListRange(aList : TList;
aStart, aEnd : Longint;
aMessage : string);



implementation
{===基本QuickSort===============================================}
procedure QSS(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
var
L, R : Longint;
Pivot : pointer;
Temp : pointer;
begin
{若至少有两个元素}
while (aFirst < aLast) do begin
{支点为中点元素}
Pivot := aList.List[(aFirst+aLast) div 2];
{设置引索进行划分}
L := pred(aFirst);
R := succ(aLast);
while true do begin
repeat dec(R); until (aCompare(aList.List[R], Pivot) <= 0);
repeat inc(L); until (aCompare(aList.List[L], Pivot) >= 0);
if (L >= R) then Break;
Temp := aList.List[L];
aList.List[L] := aList.List[R];
aList.List[R] := Temp;
end;
{对第一个子集进行quicksort}
if (aFirst < R) then
QSS(aList, aFirst, R, aCompare);
{对第二个子集进行quicksort}
aFirst := succ(R);
end;
end;
procedure TDQuickSortStd(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
begin
TDValidateListRange(aList, aFirst, aLast, 'TDQuickSortStd');
QSS(aList, aFirst, aLast, aCompare);
end;
{====================================================================}



procedure QSNR(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
var
L, R : Longint;
Pivot : pointer;
Temp : pointer;
Stack : array [0..63] of Longint;
SP : Longint;
begin
{初始化栈}
Stack[0] := aFirst;
Stack[1] := aLast;
SP := 2;
while (SP <> 0) do begin
{弹出栈顶子表}
dec(SP, 2);
aFirst := Stack[SP];
aLast := Stack[SP+1];
{若至少有两个元素}
while (aFirst < aLast) do begin
{支点为中间元素}
Pivot := aList.List[(aFirst+aLast) div 2];
{设置引索并进行划分}
L := pred(aFirst);
R := succ(aLast);
while true do begin
repeat dec(R); until (aCompare(aList.List[R], Pivot) <= 0);
repeat inc(L); until (aCompare(aList.List[L], Pivot) >= 0);
if (L >= R) then Break;
Temp := aList.List[L];
aList.List[L] := aList.List[R];
aList.List[R] := Temp;
end;
{将大一些的子表压入栈，并对小子表处理}
if (R - aFirst) < (aLast - R) then begin
Stack[SP] := succ(R);
Stack[SP+1] := aLast;
inc(SP, 2);
aLast := R;
end
else begin
Stack[SP] := aFirst;
Stack[SP+1] := R;
inc(SP, 2);
aFirst := succ(R);
end;
end;
end;
end;
procedure TDQuickSortNoRecurse(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
begin
TDValidateListRange(aList, aFirst, aLast, 'TDQuickSortNoRecurse');
QSNR(aList, aFirst, aLast, aCompare);
end;
{====================================================================}



procedure QSR(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
var
L, R : Longint;
Pivot : pointer;
Temp : pointer;
begin
while (aFirst < aLast) do begin
{选择一个随机元素做支点}
R := aFirst + Random(aLast - aFirst + 1);
L := (aFirst + aLast) div 2;
Pivot := aList.List[R];
aList.List[R] := aList.List[L];
aList.List[L] := Pivot;
{设置引索并进行划分}
L := pred(aFirst);
R := succ(aLast);
while true do begin
repeat dec(R); until (aCompare(aList.List[R], Pivot) <= 0);
repeat inc(L); until (aCompare(aList.List[L], Pivot) >= 0);
if (L >= R) then Break;
Temp := aList.List[L];
aList.List[L] := aList.List[R];
aList.List[R] := Temp;
end;
{对第一个子集进行quicksort}
if (aFirst < R) then
QSR(aList, aFirst, R, aCompare);
{对第二个子集进行quicksort}
aFirst := succ(R);
end;
end;
procedure TDQuickSortRandom(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
begin
TDValidateListRange(aList, aFirst, aLast, 'TDQuickSortRandom');
QSR(aList, aFirst, aLast, aCompare);
end;
{====================================================================}



procedure QSM(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
var
L, R : Longint;
Pivot : pointer;
Temp : pointer;
begin
while (aFirst < aLast) do begin
{若有3个或更多的元素，选择第一个元素，最后一个元素，中间元素做支点}
if (aLast - aFirst) >= 2 then begin
R := (aFirst + aLast) div 2;
if (aCompare(aList.List[aFirst], aList.List[R]) > 0) then begin
Temp := aList.List[aFirst];
aList.List[aFirst] := aList.List[R];
aList.List[R] := Temp;
end;
if (aCompare(aList.List[aFirst], aList.List[aLast]) > 0) then begin
Temp := aList.List[aFirst];
aList.List[aFirst] := aList.List[aLast];
aList.List[aLast] := Temp;
end;
if (aCompare(aList.List[R], aList.List[aLast]) > 0) then begin
Temp := aList.List[R];
aList.List[R] := aList.List[aLast];
aList.List[aLast] := Temp;
end;
Pivot := aList.List[R];
end
{若只有两个元素，选第一个做支点}
else
Pivot := aList.List[aFirst];
{设置引索并进行划分}
L := pred(aFirst);
R := succ(aLast);
while true do begin
repeat dec(R); until (aCompare(aList.List[R], Pivot) <= 0);
repeat inc(L); until (aCompare(aList.List[L], Pivot) >= 0);
if (L >= R) then Break;
Temp := aList.List[L];
aList.List[L] := aList.List[R];
aList.List[R] := Temp;
end;
{ 对第一个子集进行quicksort}
if (aFirst < R) then
QSM(aList, aFirst, R, aCompare);
{对第二个子集进行quicksort}
aFirst := succ(R);
end;
end;
{--------}
procedure TDQuickSortMedian(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
begin
TDValidateListRange(aList, aFirst, aLast, 'TDQuickSortMedian');
QSM(aList, aFirst, aLast, aCompare);
end;
{====================================================================}



const
QSCutOff = 15;
procedure QSInsertionSort(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
var
i, j : Longint;
IndexOfMin : Longint;
Temp : pointer;
begin
{找到最小元素，并将其放到第一位}
IndexOfMin := aFirst;
j := QSCutOff;
if (j > aLast) then
j := aLast;
for i := succ(aFirst) to j do
if (aCompare(aList.List, aList.List[IndexOfMin]) < 0) then
IndexOfMin := i;
if (aFirst <> IndexOfMin) then begin
Temp := aList.List[aFirst];
aList.List[aFirst] := aList.List[IndexOfMin];
aList.List[IndexOfMin] := Temp;
end;
{进行quicksort}
for i := aFirst+2 to aLast do begin
Temp := aList.List;
j := i;
while (aCompare(Temp, aList.List[j-1]) < 0) do begin
aList.List[j] := aList.List[j-1];
Dec(j);
end;
aList.List[j] := Temp;
end;
end;


{--------}
procedure QS(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
var
L, R : Longint;
Pivot : pointer;
Temp : pointer;
Stack : array [0..63] of Longint;
SP : Longint;
begin
{初始化栈}
Stack[0] := aFirst;
Stack[1] := aLast;
SP := 2;



{栈中有子表时}
while (SP <> 0) do begin



{弹出栈顶子表}
dec(SP, 2);
aFirst := Stack[SP];
aLast := Stack[SP+1];



{若子表有足够元素，则进行循环}
while ((aLast - aFirst) > QSCutOff) do begin



{若有3个或更多的元素，选择第一个元素，最后一个元素，中间元素做支点}
R := (aFirst + aLast) div 2;
if (aCompare(aList.List[aFirst], aList.List[R]) > 0) then begin
Temp := aList.List[aFirst];
aList.List[aFirst] := aList.List[R];
aList.List[R] := Temp;
end;
if (aCompare(aList.List[aFirst], aList.List[aLast]) > 0) then begin
Temp := aList.List[aFirst];
aList.List[aFirst] := aList.List[aLast];
aList.List[aLast] := Temp;
end;
if (aCompare(aList.List[R], aList.List[aLast]) > 0) then begin
Temp := aList.List[R];
aList.List[R] := aList.List[aLast];
aList.List[aLast] := Temp;
end;
Pivot := aList.List[R];



{设置引索并进行划分}
L := aFirst;
R := aLast;
while true do begin
repeat dec(R); until (aCompare(aList.List[R], Pivot) <= 0);
repeat inc(L); until (aCompare(aList.List[L], Pivot) >= 0);
if (L >= R) then Break;
Temp := aList.List[L];
aList.List[L] := aList.List[R];
aList.List[R] := Temp;
end;



{将大一些的子表压入栈，并对小子表处理}
if (R - aFirst) < (aLast - R) then begin
Stack[SP] := succ(R);
Stack[SP+1] := aLast;
inc(SP, 2);
aLast := R;
end
else begin
Stack[SP] := aFirst;
Stack[SP+1] := R;
inc(SP, 2);
aFirst := succ(R);
end;
end;
end;
end;
procedure TDQuickSort(aList : TList;
aFirst : Longint;
aLast : Longint;
aCompare : TtdCompareFunc);
begin
TDValidateListRange(aList, aFirst, aLast, 'TDQuickSort');
QS(aList, aFirst, aLast, aCompare);
QSInsertionSort(aList, aFirst, aLast, aCompare);
QSS(aList, aFirst, aLast, aCompare);
end;





{===比较例程=========================================}
{--------}
{--------}
{--------}
{--------}



procedure TDValidateListRange(aList : TList;
aStart, aEnd : Longint;
aMessage : string);
begin
if (aList = nil) then
begin
//ShowMessage('List为空');
exit;
end;
if (aStart < 0) or (aStart >= aList.Count) or
(aEnd < 0) or (aEnd >= aList.Count) or
(aStart > aEnd) then
begin
// ShowMessage('范围错误');
exit;
end;
end;
{--------}




end.











以上提供多种快速比较方法　我们之用其中的一种TDQuickSort
========================================================================
使用方法

定义一个比较方法
function f_SortNumUp(p_Data1, p_Data2: Pointer): integer; //号码升序 ////
begin ////
Result := StrComp(PAnsiChar(PGrpSendNumInfo(p_Data1)^.r_Num), ////
PAnsiChar(PGrpSendNumInfo(p_Data2)^.r_Num)); ////
end;

然后如下调用
TDQuickSort(m_NumList, 0 , m_NumList.Count - 1, f_SortNumUp)

降序的话反过来就可以

排序完再用２分法查　很快了拉

感谢各位！我先按Avalon的方法试试....

To Avalon:
PGrpSendNumInfo是如何定义的？能否结合我的例子做一个Demo，谢谢！

PGrpSendNumInfo是指针　指向某个数据结构
你可以
PMyRec = ^TMyRec;
然后用PMyRec 代替我的PGrpSendNumInfo啦