lua实现经典排序算法

---

写在前面

• 推荐一个排序可视化网站：VisuAlgo
• 代码里所有输出都是通过下面这个输出函数输出的

function outNum( needOutNum )
    for k,v in ipairs(needOutNum) do
        print(v)
    end
end

• lua里的#到这都成注释了= =||||，所以就不贴代码了，直接贴图

一、选择排序

1. 原理

• 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
• 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾

2. 代码实现

选择排序

二、冒泡排序

1. 原理

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

2. 代码实现

冒泡排序

3. 优化代码

• 记录最后一次交换的位置，下一次交换就从这结束

• 记录是否交换，如果没有交换证明已经有序了

  
  冒泡排序优化

三、插入排序

1. 原理

• 从第一个元素开始，该元素可以认为已经被排序
• 取出下一个元素，在已经排序的元素序列中从后向前扫描
• 如果该元素（已排序）大于新元素，将该元素移到下一位置
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
• 将新元素插入到该位置后
• 重复步骤2~5

2. 代码实现

插入排序

四、希尔排序

1. 原理

• 将整个待排元素序列分割成若干个子序列，分别进行插入排序
• 依次缩减增量再进行排序
• 待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序

2. 代码实现

希尔排序

五、归并排序

1. 原理

• 递归将数组两两划分
• 对划分的数组分别进行排序
• 合并排序好的数组

2. 代码实现

• 递归版

function mergeSortTest(needSortTable)
    local tempTable = {}
    local mergeTable = function (left,right)
        tempTable = {}
        local middle = math.floor((right + left)/2)
        local i = left
        local j = middle + 1
        local t = 1
        while (i<=middle and j<=right) do
            if needSortTable[i] <= needSortTable[j] then
                tempTable[t] = needSortTable[i]
                i = i + 1
                t = t + 1
            else
                tempTable[t] = needSortTable[j]
                j = j + 1 
                t = t + 1
            end
        end
        while(i<=middle) do
            tempTable[t] = needSortTable[i]
            i = i + 1
            t = t + 1
        end
        while(j<=right) do
            tempTable[t] = needSortTable[j]
            j = j + 1
            t = t + 1
        end
        for i=1,t-1 do
            needSortTable[left] = tempTable[i]
            left = left + 1
        end
    end
    local function divideTable (left,right)
        if left < right then
            local middle = math.floor((right + left)/2)
            divideTable(left,middle)
            divideTable(middle+1,right)
            mergeTable(left,right)
        end
    end
    divideTable(1,#needSortTable)
    outNum(needSortTable)
end

• 非递归版

function mergeSortNonRecursiveTest(needSortTable)
    local tempTable = {}
    local mergeTable = function (left,middle,right)
        tempTable = {}
        local i = left
        local j = middle + 1
        local t = 1
        while (i<=middle and j<=right) do
            if needSortTable[i] <= needSortTable[j] then
                tempTable[t] = needSortTable[i]
                i = i + 1
                t = t + 1
            else
                tempTable[t] = needSortTable[j]
                j = j + 1 
                t = t + 1
            end
        end
        while(i<=middle) do
            tempTable[t] = needSortTable[i]
            i = i + 1
            t = t + 1
        end
        while(j<=right) do
            tempTable[t] = needSortTable[j]
            j = j + 1
            t = t + 1
        end
        for i=1,t-1 do
            needSortTable[left] = tempTable[i]
            left = left + 1
        end
    end

    local  i = 1
    while(i<#needSortTable) do
        local left = 1
        local middle = left + i - 1
        local right = middle + i 

        while(right<=#needSortTable) do
            mergeTable(left,middle,right)
            left = right + 1
            middle = left + i - 1
            right = middle + i
        end
        --如果middle大于数组长度，说明没有right部分，不需要合并了
        if (left<=#needSortTable and middle<=#needSortTable) then 
            mergeTable(left,middle,#needSortTable)
        end
        i = i + i
    end
    outNum(needSortTable)
end

六、快速排序

1. 原理

• 挑选基准值：从数列中挑出一个元素
• 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成
• 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序

2. 代码实现

快速排序

七、桶排序

1. 原理

• 设置一个定量的数组当作空桶子
• 寻访序列，并且把项目一个一个放到对应的桶子去
• 对每个不是空的桶子进行排序
• 从不是空的桶子里把项目再放回原来的序列中

2. 代码实现

桶排序

八、堆排序

1. 原理

• 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
• 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
• 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

2. 代码实现

堆排序

九、基数排序

1. 原理

• 求数据的最大位数
• 从个位数开始对每位数进行排序，存放在桶中
• 从不是空的桶子里把值再放回原来的序列中

2. 代码实现

function radixSortTest( needSortTable )
    local function getMaxNumOfDigits(unsortedTable)
        local temp = 0
        local num = 0
        for k,v in ipairs(unsortedTable) do
            temp = math.max(temp,v)
        end
        while temp >10 do
            num = num + 1
            temp = temp/(math.pow(10,num))
        end
        return num
    end

    local maxNum = getMaxNumOfDigits(needSortTable)
    for i=0,maxNum do
        local tempList = {0,0,0,0,0,0,0,0,0,0}
        local outPutList = {}
        local curNum = math.pow(10,i)
        for k,v in ipairs(needSortTable) do
            if (v/curNum)%10+1 <= 10 then
                tempList[math.floor(v/curNum)%10+1] = tempList[math.floor(v/curNum)%10+1] + 1
            end
        end
        local k = 1
        while k + 1 < #tempList do
            tempList[k+1] = tempList[k+1] + tempList[k]
            k = k + 1
        end
        for j = #needSortTable,1,-1 do
            local num = math.floor(needSortTable[j]/curNum)%10 + 1
            if tempList[num] > 0 then
                outPutList[tempList[num]] = needSortTable[j]
                tempList[num] = tempList[num] - 1
            end
        end
        
        for q = 1,#needSortTable do
            needSortTable[q] = outPutList[q]
        end
    end
    outNum(needSortTable)
end