fastsort.bas

使用VB的快速排序算法

Public Sub Ascii_Sort(Numbers As Variant, ByRef SortedPtrs() As Long)
    
    ' a v.quick sort for numbers in the range 0-255
    ' (Written by Steve Smith, Stuff Software Ltd, [e-mail], c.Aug96)
    
    ' RETURNS:
    ' SortedPtrs() = list of pointers to Numbers(), with biggest first.
    
    ' THE PRINCIPLE:
    ' To utilise the Basic/VB INSTR function to subcontract the inner loop of a sort algorithm
    '   out to machine code, rather than have VB plough through it line by line via the interpreter.
    ' It could probably be rewritten for integers or longs, with an MKI/MKL simulator to build SortStr$
    '   & checking that each substring found is on a 2 or 4-byte boundary.
    
    ' NOTES RE. SPEED:
    ' Has the advantage that the speed is proportional to nNumbers,
    '   rather than to nNumbers^2 or nNumber.Ln(nNumbers) - as in most sorting algorithms,
    '   since the INSTR function effectively replaces the inner loop. It also gains in having
    '   no recursive calls.
    ' The lower the biggest number, the faster the sort.
    ' This makes other supposedly 'ultra-fast' sorts look positively snail-like
    '   (eg. with random numbers 0-255, VB4 16-bit on a Pentium 166 -
    '   20,000 numbers - ShellSort 7.3sec, QuickSort 4.7sec, Ascii_Sort 0.32sec !
    '   2,000 numbers - ShellSort 0.45sec, QuickSort 0.34sec, Ascii_Sort 0.05 !)
    
    Dim StartNumber%, EndNumber%, nNumbers%
    Dim SortStr$, Number%, PointerNum%
    Dim Ptr%, i%, Char$
    
    ' misc. preparation
    StartNumber = LBound(Numbers)
    EndNumber = UBound(Numbers)
    nNumbers = EndNumber - StartNumber + 1
    ReDim SortedPtrs(1 To nNumbers)
    
    ' build sortStr$
    '   (this mirrors the Numbers() array, as a string of characters)
    SortStr$ = Space$(nNumbers)
    For i = StartNumber To EndNumber
        Mid$(SortStr$, i - StartNumber + 1, 1) = Chr$(Numbers(i))
    Next
    
    ' sort (starting with the lowest numbers)
    Number = -1
    PointerNum = nNumbers + 1
    Do While PointerNum > 1
        
        ' find next lowest character/number
        Do
            Number = Number + 1
            Ptr = InStr(SortStr$, Chr$(Number))
        Loop Until Ptr
        
        ' return a pointer for each occurences of that character/number
        Char$ = Chr$(Number)
        Do
            PointerNum = PointerNum - 1
            SortedPtrs(PointerNum) = Ptr + StartNumber - 1
            Ptr = InStr(Ptr + 1, SortStr$, Char$)
        Loop Until Ptr = 0
        
    Loop
    
End Sub