最近項(xiàng)目忙了起來(lái)冕杠，很難集中一整塊時(shí)間去學(xué)習(xí)微姊，文章更新的速度也慢了下來(lái)。零碎時(shí)間打算把算法過(guò)一遍分预，所以開了一個(gè)文集記錄下學(xué)習(xí)過(guò)程兢交，

談到算法，很重要笼痹。為什么這樣講配喳，面試基本上要問(wèn)啊５矢伞Ｇ绻！但是實(shí)際上救赐，對(duì)于游戲開發(fā)客戶端來(lái)講涧团，我們遇到的數(shù)據(jù)量不會(huì)很大，常見的也就是排序或者字符匹配這樣的（除非是高級(jí)AI系統(tǒng)经磅，可以涉及到復(fù)雜的算法）泌绣，而且現(xiàn)在很多算法都有相應(yīng)的接口封裝好了，我們只管調(diào)用使用即可预厌，還有一點(diǎn)就是阿迈，懂得算法，完全開闊了我們處理問(wèn)題的思路轧叽，比如使用什么數(shù)據(jù)結(jié)構(gòu)處理數(shù)據(jù)更為便捷苗沧，以及如果更有效率的處理問(wèn)題等。

作為開篇炭晒，我們從數(shù)組處理開始待逞。其中，最老生常談的就是排序网严。本篇主要介紹插入排序：簡(jiǎn)單插入排序以及希爾排序飒焦，這兩個(gè)排序都屬于插入排序，實(shí)際上簡(jiǎn)單插入排序就是希爾排序間隔為1分組的情況屿笼，兩者代碼也非常相似牺荠。

前文：

我們首先介紹幾個(gè)概念：
空間復(fù)雜度：指程序處理算法需要的額外內(nèi)存空間。

時(shí)間復(fù)雜度：指程序處理算法需要的時(shí)間驴一。但是這個(gè)時(shí)間會(huì)根據(jù)CPU能力休雌，環(huán)境溫度，計(jì)算機(jī)配置等影響肝断，所以不太客觀杈曲。而事實(shí)上驰凛，我們會(huì)用記錄算法的關(guān)鍵操作來(lái)表示時(shí)間復(fù)雜度。

算法的復(fù)雜度担扑，我們通常會(huì)使用大O表示法來(lái)表示恰响。

排序算法的穩(wěn)定性：假設(shè)A，B兩個(gè)數(shù)據(jù)相等涌献，在原數(shù)據(jù)列中胚宦，A在B之前，經(jīng)過(guò)排序算法燕垃，AB數(shù)據(jù)序列永遠(yuǎn)不變枢劝，即A永遠(yuǎn)在B之前，這種排序算法為穩(wěn)定排序卜壕；而在排序之后您旁，A有可能排在了B之后，這種算法為非穩(wěn)定排序轴捎。為什么我們要關(guān)注穩(wěn)定性鹤盒？舉個(gè)例子，如果你只關(guān)心數(shù)據(jù)本身侦副，那么排序穩(wěn)定就無(wú)關(guān)緊要昨悼；但是你要用數(shù)據(jù)去處理其他操作，就要考慮是否需要考慮穩(wěn)定性跃洛，假設(shè)游戲里需要顯示排行，為了保證每個(gè)玩家看到的排行的順序一致终议，以及每次玩家打開排行榜汇竭，看到的順序是一致的，這時(shí)候就需要排序算法要具有穩(wěn)定性穴张。

簡(jiǎn)單插入排序：

思想：將一個(gè)數(shù)插入到一個(gè)有序的數(shù)組细燎，那么只用依次比較有序數(shù)組的數(shù)，直到找到這個(gè)數(shù)在數(shù)組中的位置即可皂甘〔Ｗぃ可以看一下動(dòng)畫演示（動(dòng)畫是用unity制作的）：

InsertionSort.gif

接下來(lái)著手寫代碼：

        public static void InsertionSort(int[] arr)
        {
            int length = arr.Length;
            if (length<2)
            {
                return;
            }
            for (int i = 1; i < length; i++)
            {
                int j = i-1;
                int temp = arr[i];              //當(dāng)前待排序的數(shù)字
                while (j>=0&&arr[j]>temp)       //依次向前比較，找到自身位置
                {                    
                    arr[j+1] = arr[j];
                    j--;
                }
                arr[j + 1] = temp;              
            }
        }

時(shí)間復(fù)雜度：我們主要看兩層循環(huán)偿枕，第一層執(zhí)行次數(shù)為（length-1)璧瞬，第二層最小為0，最大為（length-1)渐夸，那么復(fù)雜度就是從（length-1)+（length-2)+...+1嗤锉。用大O法，通常我們只關(guān)心數(shù)量級(jí)墓塌，而不關(guān)心系數(shù)瘟忱，所以其負(fù)責(zé)度就是：O（n²）
空間復(fù)雜度：很明顯只申請(qǐng)了一個(gè)temp的變量奥额，因此為O(1)。
穩(wěn)定性：如果當(dāng)前數(shù)據(jù)跟前一位數(shù)據(jù)相等访诱，并不會(huì)交換兩數(shù)位置垫挨，因此是穩(wěn)定排序。

希爾排序：

思路：將數(shù)組按照一定間隔進(jìn)行分組触菜，每組組內(nèi)成員進(jìn)行簡(jiǎn)單插入排序九榔。然后間隔變小，再次分組進(jìn)行簡(jiǎn)單插入排序玫氢。直到間隔為1帚屉，并插入排序結(jié)束，那么排序結(jié)束漾峡。演示動(dòng)畫如下：

ShellSort.gif

代碼如下：

        public static void ShellSort(int[] arr)
        {
            int length = arr.Length;
            if (length<2)
            {
                return;
            }
            int gap = length / 2;           //分組間隔
            while (gap>0)                   //分組間隔每次縮小2倍
            {
                for (int i = gap; i < length; i++)  
                {
                    //類似插入排序攻旦，不過(guò)數(shù)據(jù)已經(jīng)分組吭狡，待排序數(shù)組谦铃，依次與組內(nèi)數(shù)據(jù)比較
                    //以便找到合適位置
                    int j = i - gap;
                    int temp = arr[i];
                    while (j>=0&&arr[j]>temp)
                    {
                        arr[j + gap] = arr[j];
                        j  -= gap;
                    }
                    arr[j + gap] = temp;
                }

                gap /= 2;
            }
        }

可以看出，希爾排序的代碼與簡(jiǎn)單插入排序基本類似耙册，其實(shí)簡(jiǎn)單插入排序就是gap為1的希爾排序槽袄。
時(shí)間復(fù)雜度：希爾排序的時(shí)間復(fù)雜度分析較為復(fù)雜烙无，我自己即便是查閱各種資料，也推不出公式遍尺。
空間復(fù)雜度：O(1)截酷。

Shell1.png

shell2.png