lua実装スタックソート
1141 ワード
ヒープのソート:
local function swap(t, i, j)
local temp = t[i]
t[i] = t[j]
t[j] = temp
end
local function heapInsert(t, i)
-- i i / 2
while i > 1 and t[i] > t[i // 2] do
swap(t, i, i // 2)
i = i // 2
end
end
local function heapify(t, i, size)
local left = i * 2
while left < size do
local largest = (left + 1 < size and t[left + 1] > t[left]) and left + 1 or left
largest = t[i] > t[largest] and i or largest
if largest == i then return end
swap(t, i, largest)
i = largest
left = i * 2
end
end
function heapSort(t)
if(t and #t < 2) then
return
end
for i = 1, #t do
heapInsert(t, i)
end
local size = #t
swap(t, 1, size)
while size > 1 do
heapify(t, 1, size)
size = size - 1
swap(t, 1, size)
end
end
t = {1, 34, 435, 2, 6, -234, 324, -4, 0}
print(table.concat(t, ","))
heapSort(t)
print(table.concat(t, ","))
----- 1,34,435,2,6,-234,324,-4,0
----- -234,-4,0,1,2,6,34,324,435