先挑最值,再把剩下的挑最值,再把剩下的挑最值。。。
1selectionSort.lua
-- 排序函数
function selectionSort(arr)
-- 外层循环,从数组的第一个元素开始,对每个元素进行排序
for i = 1, #arr do
-- 假设当前位置的元素是最小的
local minIndex = i
-- 内层循环,从当前位置开始,查找剩余元素中的最小值
for j = i, #arr do
-- 如果找到一个更小的元素,更新最小元素的索引
if arr[j] < arr[minIndex] then
minIndex = j
end
end
-- 交换当前位置和最小元素的位置
swap(arr, i, minIndex)
end
end
-- 交换函数
function swap(arr, i, j)
-- 使用一个临时变量来交换两个元素的值
local temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
end
-- 主程序
-- 定义一个待排序的数组
local arr = {1, 5, 2, 8, 9, 3}
-- 调用排序函数进行排序
selectionSort(arr)
-- 打印排序后的数组
for _, v in ipairs(arr) do
print(v .. " ")
end
Lua中的数组和字典都使用相同的数据结构(即表),但在这个例子中,我们只使用了数组部分。
2selectionSort.lua
function selectionSort(arr)
local length = #arr
for i = 1, length do
local minIndex = i
for j = i, length do
if arr[j] < arr[minIndex] then
minIndex = j
end
end
arr[i], arr[minIndex] = arr[minIndex], arr[i] -- Swap elements
end
end
function main()
local arr = {1, 5, 2, 8, 9, 3}
selectionSort(arr)
for _, v in ipairs(arr) do
print(v, " ")
end
end
main()
复杂度
O(n^2)
SortingHelper.lua
-- SortingHelper.lua
-- isSorted function to check if an array is sorted in ascending order
function isSorted(arr)
for i = 2, #arr do
if arr[i-1] > arr[i] then
return false
end
end
return true
end
-- sortTest function to test a sorting algorithm and measure its execution time
function sortTest(sortName, arr)
-- Lua doesn't have a direct equivalent of System.nanoTime(),
-- so we use os.clock() which provides the CPU time used by the Lua state in seconds
local startTime = os.clock()
if sortName == "SelectionSort" then
selectionSort(arr)
end
local endTime = os.clock()
local time = endTime - startTime -- This will give the time in seconds
if not isSorted(arr) then
error(sortName .. " failed")
end
print(string.format("%s, n = %d: %f s", sortName, #arr, time))
end
-- This is a placeholder for the actual selectionSort function,
-- which should be implemented separately as shown in the previous answer.
function selectionSort(arr)
-- Implementation of the selection sort algorithm goes here
end
-- Example usage:
local arr = {1, 5, 2, 8, 9, 3}
sortTest("SelectionSort", arr)
Lua的os.clock()函数测量的是CPU时间,而不是实际经过的时间。这在某些情况下可能不同于Java的System.nanoTime(),后者测量的是实际经过的时间。此外,由于Lua的性能测量可能不如Java精确,因此结果可能会有所不同。
还需要注意的是,Lua中没有异常处理机制与Java的throw new RuntimeException()完全对应。在Lua中,我们通常使用error()函数来抛出一个错误,这会终止程序的执行。如果你需要更复杂的错误处理,你可能需要实现自己的错误处理逻辑。
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » 003 选择排序(lua)
发表评论 取消回复