基于Lua的选择排序算法实现

 选择排序思想的核心：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

说直白点，以从小到大排序来说，就是：

第一轮找到最小的哪个元素所在的位置，记录下来，然后把数组（或table）中第一个元素和最小值位置的元素进行交换；

第二轮，从第二个位置起，找到剩余未排序的元素中值最小的哪个元素，记录下位置，然后把数组中第二个位置的元素和最小值的元素进行交换

套娃中....

直到所有元素都排序完毕，收工.

--------------------------------------------------------------------------------------------------------------
-- 实现一个自定义的 maxn_ex 函数，计算table中元素的个数
function maxn_ex(tab)
  local length = 0
  for i in pairs(tab) do
    length = length +1
  end
  return length
end


 -- 通过递归实现数组的打印
function printArray(array)
  for i = 1,table.maxn(array) do
    if type(array[i]) ~="table" then  -- 子项不为数组
      print("array["..i.."]:",array[i])
    else  -- 子项仍为数组
      if array[i] == nil then
        break
      end
      -- 递归
      printArray(array[i])
    end
  end
end
--------------------------------------------------------------------------------------------------------------

--[[
选择排序：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
--]]

function select_sort(tab)
  len = maxn_ex(tab)
  for i=1,len -1 do
    local min = i
    
    for j = i+1,len do
      if(tab[min] > tab[j]) then
        min = j  -- 记录最小值的下标索引
      end
    end
    
    -- 将本轮找到的最小值放到第i个位置
    tab[i],tab[min] = tab[min],tab[i]  
  end
  return tab
end



--- 测试1
function test_01()
  local tab = {2,1,6,3,17,8}
  printArray(  select_sort(tab))
  print("------------")
end


--测试2 
function test_02()
  local tab = {36,58,14,24,69,13,45,87,99}
  printArray(select_sort(tab))
  print("------------")
end

test_01()
test_02()

结果：

array[1]:	1
array[2]:	2
array[3]:	3
array[4]:	6
array[5]:	8
array[6]:	17
------------
array[1]:	13
array[2]:	14
array[3]:	24
array[4]:	36
array[5]:	45
array[6]:	58
array[7]:	69
array[8]:	87
array[9]:	99