插入排序

数据

• 平均时间复杂度：O(n^2)

• 最好时间复杂度：O(n)

• 最坏时间复杂度：O(n^2)

• 空间复杂度：O(1)

• 排序方式：In-Place

• 稳定性：稳定

描述

每次从无序区中选择的元素，插入到有序区里合适的位置（打扑克）

动图

C#实现

public class InsertSort
{
    public static void Sort<T>(IList<T> list, Func<T, T, bool> compare)
    {
        if (list.Count < 2)
        {
            return;
        }

        for (int i = 1; i < list.Count; i++)
        {
            var checkIndex = i;
            for (int j = i - 1; j >= 0; j--)
            {
                if (compare(list[checkIndex], list[j]))
                {
                    SortHelper.Exchange(list, checkIndex, j);
                    checkIndex = j;
                }
                else
                {
                    break;
                }
            }
        }
    }
}

Lua实现

function InsertSort(list, compareFunc)
    local count = #list
    if count < 2 then
        return
    end
    for i = 2, count do
        local checkIndex = i
        for j = i - 1, 1, -1 do
            if compareFunc(list[checkIndex], list[j])  then
                Exchange(list, checkIndex, j)
                checkIndex = j
            else
                break
            end
        end
    end
end