回 帖 发 新 帖 刷新版面

主题:[讨论]一种排序的算法(以空间换时间)

[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) .?

回复列表 (共1个回复)

沙发

如果是n位数,则需要定义10^n大小的数组.
空间需求也挺大的.甚至可能完全不能实现

我来回复

您尚未登录,请登录后再回复。点此登录或注册