-
Notifications
You must be signed in to change notification settings - Fork 0
/
sort_algorithms.lua
99 lines (94 loc) · 2.42 KB
/
sort_algorithms.lua
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
function sum(data)
if #data == 1 then
return data[1]
else
return table.remove(data) + sum(data)
end
end
print(sum({ 1, 2, 3 }))
function length(data)
if data == nil then
return 0
elseif #data == 1 then
return 1;
else
table.remove(data)
return 1 + length(data)
end
end
print(length({ 2, 3, 4, 5 }))
function max_number(data)
if #data == 1 then
return data[1]
else
local max = table.remove(data)
local sub_max = max_number(data)
if max < sub_max then
return sub_max
end
return max
end
end
print(max_number({ 2, 8, 1, 9 }))
local function swap(array, left, right)
local tmp = array[left]
array[left] = array[right]
array[right] = tmp
end
local function sort(array)
local pivotValue = array[1]
local left = 2
local right = #array
while left <= right do
while left <= right and array[left] < pivotValue do
left = left + 1
end
--保持稳定
while left <= right and array[right] >= pivotValue do
right = right - 1
end
if left <= right then
swap(array, left, right)
end
end
swap(array, 1, right)
return right
end
--[[
快速排序
--]]
local ARRAY_START = 1
function quick_sort(array)
local start = 1
local length = #array
if length > start then
local pivot = sort(array);
if start < pivot then
local left = table.move(array, start, pivot - 1, ARRAY_START, {})
table.move(quick_sort(left), start, pivot - 1, ARRAY_START, array)
end
if pivot < length then
local right = table.move(array, pivot + 1, length, ARRAY_START, {})
table.move(quick_sort(right), ARRAY_START, #right, pivot + 1, array)
end
end
return array
end
print(require("json").encode(quick_sort({ 4, 3, 9, 6, 1, 7, 5 })))
function selection_sort(array)
for index = 1, #array - 1 do
local leftSmallest = index
for leftIndex = leftSmallest + 1, #array do
if array[leftIndex] < array[leftSmallest] then
leftSmallest = leftIndex
end
swap(array, leftSmallest, index)
end
end
return array
end
print(require("json").encode(selection_sort({ 4, 3, 9, 6, 1, 7, 5 })))
return {
quick_sort = quick_sort,
selection_sort = selection_sort,
}