美文网首页
lua快速排序

lua快速排序

作者: 王立鹏 | 来源:发表于2016-03-16 00:10 被阅读0次
    包文件:quick_sort.lua
    #!/usr/local/bin/lua
    
    local function printTable(tables) 
        local str   = table.concat(tables, ",");
        return "{"..str.."}";
    end
    
    local function partition(list, low, high)
        local current = list[low]; 
        while low < high do
            while low < high and list[high] >= current do
                high = high - 1;
            end
            list[low], list[high] = list[high], list[low];
    
            while low < high and list[low] <= current do
                low = low + 1;
            end 
            list[low], list[high] = list[high], list[low];
        end
        return low;
    end
    
    local function qsort(list, low, high) 
        if low < high then
            local pivot = partition(list, low, high);
            qsort(list, low, pivot-1);
            qsort(list, pivot + 1, high);
        end
    end
    
    local function quick_sort(list)
        qsort(list, 1, #list);
    end
    
    return {
        sort = quick_sort,
        show = printTable,
    }
    
    run.lua
    
    #!/usr/local/bin/lua
    
    local quick_sort = require "quick_sort";
    
    local list = {10,2,4,12,45,67,89,99};
    quick_sort.sort(list);
    
    local result = quick_sort.show(list);
    print(result);
    
    

    相关文章

      网友评论

          本文标题:lua快速排序

          本文链接:https://www.haomeiwen.com/subject/fmeqlttx.html