一个总体复杂度为O(n)的插入排序算法

悠悠 2021-10-23 11:22 188阅读 0赞

下面的代码可以方便地根据所排序对象的ID查找对象的排名，且总体复杂度为O(n)，使用的是插入排序思想，下面是lua代码：

local playerList = {} -- {dbid=1,name="fdf",score=999,rank=8}
    local playerRanks = {} -- 已经排序列表
    
    function printt(obj)
    	for key, val in pairs(obj) do 
    		print("key:", key, val.dbid, "score:", val.score, "rank:", val.rank)
    	end
    	print("--------------------")
    end
    
    -- 插入排序算法
    function UpdateScore(player, score)
        if playerList[player.dbid] == nil then 
            local unit = {}
            unit.dbid = player.dbid 
            unit.score = 0 
            unit.rank = 0
    		playerList[unit.dbid] = unit
        end
        local single = playerList[player.dbid]
        single.score = single.score + score 
        if single.rank == 0 then 
            -- 新玩家
            -- 找自己的位置
            for key, val in pairs(playerRanks) do 
                if single.score > val.score then 
                    single.rank = key
                    break
                end
            end
            if single.rank > 0 then 
                table.insert(playerRanks, single.rank, single)
                -- 后面的重排
                for i = single.rank + 1, #playerRanks, 1 do 
                    playerRanks[i].rank = i
                    playerList[playerRanks[i].dbid].rank = i
                end
            else
                -- 插入到最后
                single.rank = #playerRanks + 1
                table.insert(playerRanks, single)
            end
        else
            -- 旧玩家 
            -- 排名在第二名之后的才需要处理
            if single.rank > 1 and single.score > playerRanks[single.rank - 1].score then 
                table.remove(playerRanks, single.rank)
                for j = single.rank - 1, 1, -1 do 
                    if single.score > playerRanks[j].score then 
                        playerRanks[j].rank =  playerRanks[j].rank + 1  -- 依次后退一位
                        playerList[playerRanks[j].dbid].rank = playerRanks[j].rank -- 被移动玩家的新排名
    					 if j == 1 then 
                            single.rank = 1
                            table.insert(playerRanks, 1, single)
                        end
                    else
                        -- 找到了合适的位置
                        single.rank = j + 1
                        table.insert(playerRanks, j + 1, single)
                    end
                end
            end
        end
    end
    
    local player1 = {dbid = 5}
    UpdateScore(player1, 5)
    
    local player2 = {dbid = 6}
    UpdateScore(player2, 6)
    
    local player3 = {dbid = 3}
    UpdateScore(player3, 3)
    
    local player10 = {dbid = 10}
    UpdateScore(player10, 10)
    
    UpdateScore(player1, 10)
    UpdateScore(player2, 10)
    
    local player8 = {dbid = 8}
    UpdateScore(player8, 8)
    
    UpdateScore(player2, 8)
    
    printt(playerList)
    printt(playerRanks)