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