这是一道经典的算法题目，给定一个无序的数组，求第i小的数字，一种简单的方法是，先对数组排序，然后返回数组中第i个数值。
但是排序的时间复杂度，一般是在n*logn这个量级的，为了达到线性时间复杂度，可以借用快排的思想做这道题，也就是利用快排的分解过程，每次划分后，就会知道第k小的元素，其中下标<k的元素都是小于A[k]的，而>k的元素都是大于A[k]的，这是快排的性质。
我们可以利用此性质，若一次划分之后，恰好k就是我们要求的第i小的数字，那么就得出了结果，否则就在<k或>k的空间中再次利用快排的性质进行划分求解，这样的时间复杂度平均就是O(n)了。
下面给出汇编的代码实现：

.386
.model flat, stdcall

include windows.inc
include user32.inc
include kernel32.inc

includelib kernel32.lib
includelib user32.lib
includelib msvcrt.lib

printf PROTO C :VARARG
getchar proto C
time proto C :DWORD
Random_partition proto :SDWORD, :SDWORD, :SDWORD

.data
array                        dd  4,1,3,2,16,9,10,14,8,7
szMessage                db "%d "

.code

start:

        mov eax, lengthof array
        dec eax
       
        push 5
        push eax
        push 0
        call Random_partition
       
        push array[eax*4]
        push offset szMessage
        call printf
        add esp, 8
               
        call getchar
       
        invoke ExitProcess,0
       
Random_partition proc p:SDWORD, q:SDWORD, r:SDWORD
        LOCAL i:SDWORD
        LOCAL j:SDWORD
       
        mov eax, p
        dec eax
        mov i,eax
       
        mov ebx, p
        mov j, ebx
       
        mov ecx, p       
        mov edx, q
       
       
        .if ecx == edx
                mov eax, ecx

                ret
        .endif
       
       
        ;获取随机数
       
        xor edx,edx
       
        push 0
        call time
        add esp,4
       

        mov ebx, q
        sub ebx, p
        inc ebx
       
        div ebx
       
        mov eax, edx
       
        add eax, p

       
        mov ecx, array[eax*4]
        mov esi, q
        mov edx, array[esi*4]
       
        mov array[esi*4], ecx
        mov array[eax*4], edx
       

        mov esi, j
        mov edi, q
       

        .while esi < edi
       
               
                        mov ecx, array[esi*4]       
                       
                .if ( ecx <= array[edi*4] )
                        ;交换i+1和j元素
                        mov ebx, i
                        inc ebx

                        mov eax, array[ebx*4]               
                        mov ecx, array[esi*4]       
                       

                        mov array[ebx*4], ecx
                        mov array[esi*4], eax
                       
                        inc i
                        inc esi  ;增加j的值
                       
                        .continue
                .endif
               
                .if ( ecx > array[edi*4] )
                       
                        inc esi  ;增加j的值
                        .continue
                .endif
               
               
        .endw
       
       
        ;将主元放置到正确的位置
       
        mov ebx, i
        inc ebx
        mov esi, q
       
        mov eax, array[ebx*4]
                       
        mov ecx, array[esi*4]
                       
        mov array[ebx*4], ecx
        mov array[esi*4], eax
       
       
        mov ebx, i
        inc ebx
        inc ebx
       
        sub ebx, p
       
        .if        (ebx == r)
       
                mov ebx, i
                inc ebx
                mov eax, ebx
                ret
       
        .elseif (r < ebx)
       
                push r
               
                push i
                push p
                call Random_partition
       
        .elseif (r > ebx)

                mov eax, i
                add eax, 2
                sub r, ebx
               
                push r
                push q
                push eax

                call Random_partition
        .endif
       
       
        ret
       

Random_partition endp

end start

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)