IT日常-演算法排序(泡沫排序)

前言

在演算法學習中，排序是最基本的一類演算法。但工作以後排序這種東西除非有特殊需求，不然通常都是用 built-in function，例:List裡面的一堆內建用法(Sort(),Reverse()方法用爆) ，然而演算法常常一陣子沒用到很快就會忘記，偏偏面試白版題或是刷題時，就是愛考這些題目，但不得不說這是一門內功，在考量到效能或是時間/空間複雜度時卻是派上用場的地方。 網路上關於排序的文章與教學，但沒有自己寫出來，常常都只是似懂非懂而已，這篇就當作筆記記錄自己的理解，複習一下基礎的演算法。

排序演算法-泡沫排序

邏輯說明:

如泡沫的變化般越往上越大顆，數字越大越往後排序，每一輪的迴圈中透過兩兩交換，會把[未完成排序]中最大的數字往右邊靠

例如:

範例陣列為:524613

第一層迴圈:

每一次迴圈會完成某個數字的排序，因此需要排序的次數應該是陣列的長度-1次。

第二層迴圈:

透過每個數字比較後交換，把較大的數字一直往右移把[未完成排序]中最大的數字往右移的實作過程，可看以下範例了解實際交換的過程(以C#為範例)

        public List<int> Sort(List<int> list)
        {
            for (var x = 0; x < list.Count - 1; x++)
            {
                for (var y = 0; y < list.Count - 1 - x; y++)
                {
                    var transBox = list[y];
                    if (list[y] > list[y + 1])
                    {
                        list[y] = list[y + 1];
                        list[y + 1] = transBox;
                    }
                }
            }
            return list;
        }

結語

開始為每個排序法做紀錄與恢復記憶的過程中也會用[時間複雜度] / [空間複雜度]來比較出每個排序法的效能。

時間複雜度: O(n²)

空間複雜度: θ(1) (不需要額外的陣列去存資料)

參考資料

基礎演算法系列 — 你只會用 built-in function 來排序嗎

Algorithm 演算法排序筆記