冒泡排序

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

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

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

• 空间复杂度：O(1)

• 排序方式：In-Place

• 稳定性：稳定

从无序区通过交换将最大（小）元素排列到最前端

CSharp

public class BubbleSort
{
    public static void Sort<T>(IList<T> list, Func<T, T, bool> compare)
    {
        for (int i = 0; i < list.Count; i++)
        {
            var isSwaped = false;
            for (int j = list.Count - 1; j > i; j--)
            {
                if (compare(list[j], list[j - 1]))
                {
                    SortHelper.Exchange(list, j, j - 1);
                    isSwaped = true;
                }
            }
            // 没有交换，说明有序了
            if (!isSwaped)
            {
                return;
            }
        }
    }
}

Lua

function BubbleSort(list, compareFunc)
    local count = #list
    for i = 1, count do
        local isExchagned = false
        for j = count, 2, -1 do
            if compareFunc(list[j], list[j - 1])  then
                Exchange(list, j, j - 1)
                isExchagned = true
            end
        end
        if isExchange then
            return
        end
    end
end