LUA 排序算法和性能分析[5]:插入排序算法

插入排序算法

时间开销:较长

稳定性:

复杂度:


math.randomseed(os.time());

local real_print = print;
local nLine = 0;
function print(...)
    real_print(nLine, ...)
    nLine = nLine + 1;
end;

local t = {};

local function dump()
    -- print(table.concat(t, ","));
end;

for i = 1, 256 do
    table.insert(t, math.random(i), i);
end;

function table_sort()
    table.sort(t);
    dump();
end;

-- table_sort() -- 0.3

-- 冒泡排序
function bubble_sort()
    print("冒泡排序")
    local n = #t;
    for j = 1, n - 1 do
        for i = 1, n - j do
            if t[i] > t[i+1] then
                t[i], t[i+1] = t[i+1], t[i];
                dump()
            end;
        end;
    end;
    dump();
end;

-- bubble_sort(); -- 5.7

-- 选择排序
function select_sort()
    print("选择排序")
    local n = #t;
    for i = 0, n - 2 do
        local min = i;
        for j = i + 1, n - 1 do
            if t[min+1] > t[j+1] then
                min = j;
            end;
        end;
        if (min ~= i) then
            t[min+1], t[i+1] = t[i+1], t[min+1];
            dump();
        end;
    end;
    dump();
end;

-- select_sort() -- 3.4

-- 快速排序
function quick_sort()
    print("快速排序")
    local function sort(left, right)
        if left >= right then
            return ;
        end;
        local i     = left;
        local j     = right;
        local key   = t[left];
        while (i < j) do
            while i < j and key <= t[j] do
                j = j - 1;
            end;
            t[i] =  t[j];
            dump()
            while i < j and key >= t[i] do
                i = i + 1;
            end;
            t[j] = t[i];
            dump()
        end;
        t[i] = key;
        dump()
        sort(left, i - 1);
        sort(i + 1, right);
    end;
    sort(1, #t)
end;

-- quick_sort() -- 0.4


function insert_sort()
    print("插入排序")
    local temp;
    for i = 2, #t do
        temp = t[i];
        j = i - 1;
        --与已排序的数逐一比较,大于temp时,该数移后
        while( (j > 0) and (t[j]>temp)) do

            t[j+1] = t[j];
            j = j - 1;
        end;
        if( j ~= i - 1) then
            t[j+1] = temp;
        end
        dump()
    end
end;

-- insert_sort() -- 4.7s
相关文章
相关标签/搜索