Salah satu algoritme pengurutan larik yang paling tidak biasa adalah HeapSort, yang didasarkan pada algoritme pengurutan pilihan, menggunakan struktur data heap untuk menemukan elemen maksimum dengan cepat, dan juga cara untuk menyimpan pohon biner dalam larik linier. Mari kita tangani semuanya secara berurutan.
Sortir menurut pilihan
.
, . - .
, , 1.
, N . , :
(2*N + 1) + (2*(N - 1) + 1) + … + (2*K + 1) + … + 2*1 + 1 = 2(N*N - N)/2 + N = N*N
, - O(N^2).
.
. - ? , , «» «». , . , - 1 .
, :
, . , , , . .
P = (x - 1) / 2
L = 2x + 1
R = 2x + 2
: .
void heapify(int root, int size)
, , . - .
?
, , «» . -- .
- , , .
, . heapify , , - , , .
heapify()
. .
HeapSort
? - . N/2 . , , log 2 N.
, - (N log N) / 2
. . , . 1, , .
«» -- , , . log 2 K , K - .
N , , !
O(N log 2 N).
- - «» , .
" ". 20 - , () . . . - .