红塔山7毫克专供出口:请教算法高手:还是关于排序!

来源:百度文库 编辑:中科新闻网 时间:2024/05/05 18:33:50
很多人说快速排序很有效;
以下用VB写的快速排序代码有什么问题吗?为什么50万个整数排序要14秒钟?CPU:P4 2.8G
Private Sub Quit_Sort(ByRef X() As Long, ByVal XStart As Long, ByVal XCount As Long, Optional XFrom = -1, Optional XTo = -1)
Dim Xl() As Long
Dim XlCount As Long, XuCount As Long
Dim Xu() As Long
Dim XSelect As Long
If XCount = XStart Then Exit Sub
If XTo = -1 Then XTo = XCount
If XFrom = -1 Then XFrom = XStart
If XTo = XFrom Then Exit Sub
If XTo - XFrom = 1 Then '最小排序
If X(XTo) < X(XFrom) Then Exchange X, XTo, XFrom
ElseIf XTo - XFrom > 1 Then
XSelect = Select_P(XTo, XFrom)
XlCount = 0
ReDim Xl(1 To XTo - XFrom + 1) As Long
XuCount = 0
ReDim Xu(1 To XTo - XFrom + 1) As Long
For i = XFrom To XTo
If X(i) >= X(XSelect) Then
XuCount = XuCount + 1
Xu(XuCount) = X(i)
Else
XlCount = XlCount + 1
Xl(XlCount) = X(i)
End If
Next i
'分组完毕
Quit_Sort Xl, 1, XlCount
Quit_Sort Xu, 1, XuCount
'合并
For i = 1 To XlCount
X(i + XFrom - 1) = Xl(i)
Next i
For i = 1 To XuCount
X(i + XFrom + XlCount - 1) = Xu(i)
Next i
End If
End Sub

Private Function Select_P(ByVal Ia As Long, ByVal Ib As Long) As Long
If Ia > Ib Then
Select_P = Int((Ia - Ib + 1) * Rnd) + Ib
Else
Select_P = Int((Ib - Ia + 1) * Rnd) + Ia
End If
End Function

Private Sub Exchange(ByRef X() As Long, ByVal X1 As Long, ByVal X2 As Long)
Dim Xt As Long
Xt = X(X1)
X(X1) = X(X2)
X(X2) = Xt
End Sub

pascal快排
对C数组排序
procedure sort(l,r:integer);
var
i,j,v:integer;
begin
i:=l;j:=r;
v:=c[(l+r) div 2];
repeat
while c[i]<v do inc(i);
while c[j]>v do dec(j);
if i<=j then begin
n:=c[i]; c[i]:=c[j]; c[j]:=n;
inc(i);dec(j);
end;
until i>j;
if l<j then sort(l,j);
if r>i then sort(i,r);
end;
这可是标准算法啊!!