选择排序

数据

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

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

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

• 空间复杂度：O(1)

• 排序方式：In-Place

• 稳定性：不稳定

描述

每次从无序区中选择最小（大）的值至于序列前端

动图

C#实现

public class SelectSort
{
    public static void Sort<T>(IList<T> list, Func<T, T, bool> compare)
    {
        for (int i = 0; i < list.Count; i++)
        {
            var minOrMaxIndex = i;
            for (int j = i + 1; j < list.Count; j++)
            {
                if (compare(list[j], list[minOrMaxIndex]))
                {
                    minOrMaxIndex = j;
                }
            }
            if (minOrMaxIndex != i)
            {
                SortHelper.Exchange(list, i, minOrMaxIndex);
            }
        }
    }
}

Lua实现

function SelectSort(list, compareFunc)
    local count = #list
    for i = 1, count do
        local index = i
        for j = i + 1, count do
            if compareFunc(list[j], list[index])  then
                index = j
            end
        end
        if index ~= i then
            Exchange(list, index, i)
        end
    end
end