主题:[讨论]一种排序的算法(以空间换时间)
[code=c]Private Function CreateData(ByVal strOutFile As String, ByVal dataCount As Long) As Long
'* 产生dataCount个不重复的7位数,保存到文件
Dim i As Long
Dim isNumExist() As Boolean
ReDim isNumExist(9000000) As Boolean '共有10000000-1000000个7位数
Dim num As Long
Dim fNo As Integer
fNo = FreeFile
Open strOutFile For Output As fNo
For i = 0 To dataCount - 1
Do
num = Rnd * 9000000 + 1000000
Loop While isNumExist(num - 1000000)
isNumExist(num - 1000000) = True
Write #fNo, num
Next
Close fNo
Erase isNumExist()
End Function
Private Function SortData(ByVal strInFile As String, ByVal strOutFile As String) As Long
'* 排序strInFile里的数据,将排序后的结果保存到strOutFile里
Dim i As Long
Dim bit() As Boolean
Dim fNo As Integer
Dim num As Long
fNo = FreeFile
ReDim bit(9000000) As Boolean
Open strInFile For Input As fNo
While (Not EOF(fNo))
Input #fNo, num
bit(num - 1000000) = True
Wend
Close fNo
fNo = FreeFile
Open strOutFile For Output As fNo
For i = 0 To 9000000
If bit(i) Then
Write #fNo, i + 1000000
End If
Next
Close fNo
Erase bit()
End Function
'* 测试
Private Sub Command1_Click()
Call CreateData("e:\a.txt", 50000)
MsgBox "created"
End Sub
Private Sub Command2_Click()
Call SortData("e:\a.txt", "e:\ok.txt")
MsgBox "sorted"
End Sub
[/code]
局限性:只能针对相同位数的数字进行排序.
时间复杂度为O(N) .?
'* 产生dataCount个不重复的7位数,保存到文件
Dim i As Long
Dim isNumExist() As Boolean
ReDim isNumExist(9000000) As Boolean '共有10000000-1000000个7位数
Dim num As Long
Dim fNo As Integer
fNo = FreeFile
Open strOutFile For Output As fNo
For i = 0 To dataCount - 1
Do
num = Rnd * 9000000 + 1000000
Loop While isNumExist(num - 1000000)
isNumExist(num - 1000000) = True
Write #fNo, num
Next
Close fNo
Erase isNumExist()
End Function
Private Function SortData(ByVal strInFile As String, ByVal strOutFile As String) As Long
'* 排序strInFile里的数据,将排序后的结果保存到strOutFile里
Dim i As Long
Dim bit() As Boolean
Dim fNo As Integer
Dim num As Long
fNo = FreeFile
ReDim bit(9000000) As Boolean
Open strInFile For Input As fNo
While (Not EOF(fNo))
Input #fNo, num
bit(num - 1000000) = True
Wend
Close fNo
fNo = FreeFile
Open strOutFile For Output As fNo
For i = 0 To 9000000
If bit(i) Then
Write #fNo, i + 1000000
End If
Next
Close fNo
Erase bit()
End Function
'* 测试
Private Sub Command1_Click()
Call CreateData("e:\a.txt", 50000)
MsgBox "created"
End Sub
Private Sub Command2_Click()
Call SortData("e:\a.txt", "e:\ok.txt")
MsgBox "sorted"
End Sub
[/code]
局限性:只能针对相同位数的数字进行排序.
时间复杂度为O(N) .?