Lua - 选择排序

选择排序（Selection Sort）从列表的未排序部分中反复选择最小元素，然后将其与未排序列表的第一个元素交换。

main.lua

-- 使用选择排序对列表进行排序的函数
function selection_sort(list)
   -- 列表的长度
   local n = #list 
   -- 从第1个元素开始迭代到倒数第二个元素
   for i = 1, n-1 do 
      -- 初始化最小元素的索引
      local minIndex = i 
      -- 在列表的未排序部分找到最小元素的索引
      for j = i + 1, n do
         if list[j] < list[minIndex] then
            minIndex = j -- minIndex 应指向最小元素
         end
      end

      -- 将 minIndex 与第一个元素交换
      if minIndex ~= i then
         list[i], list[minIndex] = list[minIndex], list[i]
      end
   end
   -- 列表已排序，返回它
   return list 
end

-- 示例用法：
local numbers = {5, 1, 4, 2, 8}
local sorted = selection_sort(numbers)
print("Sorted list:", table.concat(sorted, ", "))

输出

运行上述程序时，我们将得到以下输出−

Sorted list:	1, 2, 4, 5, 8

选择排序的工作原理

• 遍历每个元素 − 我们从第1个元素开始循环到倒数第二个元素。每次迭代的目标是将正确元素放置在第 i 个位置。

• 找到最小值 − 使用 minIndex 获取最小元素的索引。使用内层循环遍历列表的未排序部分并获取最小元素的索引。

• 交换 − 内层循环完成后，如果 minIndex 与 i 不同，则交换值，将未排序列表的最小元素放置在其正确位置。

• 重复过程 − 外层循环继续，每次迭代后，将每个迭代的最小元素放置在其正确位置。

• 构建排序列表 − 重复上述步骤直到列表排序完成。

时间复杂度

• O(n²) − n 为元素数量，因为我们总是循环内层循环。外层循环运行 n-1 次，内层循环平均运行 n/2 次。因此，最坏情况、最佳情况和平均时间复杂度均为 O(n²)。

空间复杂度

• O(1) − 选择排序的空间复杂度是常数，因为它不需要从列表中额外分配内存用于临时存储。

何时使用选择排序

选择排序简单易学，适用于以下场景 −

• 教育目的 − 由于简单易学/教授，选择排序常用于教育目的。

• 小数据集 − 对于小数据集，选择排序的性能与其他算法相当。

• 较少交换 − 如果交换操作成本高，选择排序很有用，因为它执行的交换次数最少，为 O(n)。