冒泡算法

-步驟

-> 比較相鄰的元素，如果第一個比第二個大，就交換。
-> 對每一對元素都進(jìn)行比較，從開始的第一對，到結(jié)尾的最后一對。完成后，最后的元素應(yīng)該是最大的。
-> 針對所有的元素重復(fù)上面的步驟，除了最后一個。
-> 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有一對數(shù)字需要比較。

void BubbleSort(int* h, size_t len)
{
    if(h == NULL) return;
    if(len <= 1) return;
    // i是次數(shù)，j是具體下標(biāo)
    for(int i = 0; i < len - 1; i++)
    {
        for(int j = 0; j < len - 1 - i; j++)
        {
            if(h[j] > h[j+1])
            {
                Swap(h[j], h[j + 1])
            }
        }
    }
}

選擇排序

-步驟

-> 在未排序的序列中找到最小（大）的元素，存放到排序序列的最前面。
-> 從剩余未排序的序列中繼續(xù)尋找最?。ù螅┑脑兀缓蠓诺揭雅判虻男蛄心┪?。
-> 重復(fù)第二步，直到所有元素均排序完畢。

-理解

選擇排序是在未排序的序列里每次去找最大(小)的元素。永遠(yuǎn)在矮子里面拔高個，被選出來的那一刻，就確定好了自己的位置排名。

void SelectionSort(int* h, size_t len)
{
    if(h == NULL) return;
    if(len <= 1) return;
    int minindex, i, j;
    // i是次數(shù)，也即排好的個數(shù)，j是繼續(xù)排
    
    for (i = 0; i < len; i++) // 遍歷選到最小的值
    {
        minindex = i;
        // 每輪需要比較的次數(shù)是len - i
        for(int j = i + 1; j < len; j++)
        {
            if(h[j] < h[minindex]) minindex = j; // 一輪下來，minindex都是最小的值
        }
        // 將每次找到的最小值都依次放在i位置
        Swap(h(i), h[minindex]); //這樣依次排好了前i個數(shù)
    }
}

插入排序

-步驟

-> 將待排序的序列的第一個元素看作是一個有序的序列，把第二個元素到最后一個元素的序列看作是一個未排序的序列。
-> 從頭到尾依次掃描未排序的序列，將掃描到的每個元素插入到前面有序序列的正確位置。（如果待插入的序列中有與選擇的元素相同的元素，那么將這個元素插入到相等元素后面。）

-理解

插入排序是，每一個值都去已經(jīng)排好隊的序列里找自己的位置。
每一個值都不需要等，輪到自己的時候一定會給自己安排上位置，只不過后面還有可能被擠掉就是了。

void InsertSort(int* h, size_t len)
{
    if(h == null) return;
    if( len <= 1) return;
    // 從下標(biāo)1開始，i代表已經(jīng)排好序的元素個數(shù)
    for (int i = 1; i < len; i++)
    {
        // 用拿到的每一個元素去前面比較，直到找到合適的位置break
        for (int j = i; j > 0; j-- )
        {
            if (h[j] < h[j - 1])
            {
                Swap(h[j], h[j - 1])
            } else
            {
                break;
            }
        }
    }
    return;
}

希爾排序

[理解了過程，但是用代碼實現(xiàn)還是有點不熟悉，不理解]

-步驟

-> 選擇一個增量序列，t1,t2,...,tk ,其中ti > tj, tk = 1;
-> 按增量序列的個數(shù)，對序列進(jìn)行k趟排序。
-> 每趟排序，根據(jù)對應(yīng)的增量值ti,將待排序序列分割成若干個長度為m的子序列，分別對各子序列進(jìn)行插入排序，僅增量因子的值為1時，整個序列作為一個表來處理，表的長度即為序列的長度。

-理解

-> 希爾排序采用的是跳躍式的分組策略，通過某個增量，將數(shù)組劃分為若干組子序列。然后分組進(jìn)行插入排序，隨后逐步縮小增量，繼續(xù)這個操作，直至增量為1。
-> 這種策略，在初始階段就可以達(dá)到基本有序的程度，然后隨著縮小增量，多數(shù)情況下后面只要數(shù)據(jù)微調(diào)即可，不會涉及過多數(shù)據(jù)移動。
-> 我們實現(xiàn)這個算法的時候，使用的增量gap = length/2,縮小增量也以gap/2的方式，這種增量的選擇我們可以使用一個序列表示 ,{n/2, (n/2)/2,...,1},這個就是增量序列。增量序列的選擇和證明都是個數(shù)學(xué)難題，我們用的這個增量序列是比較常用的，也是希爾建議的增量，亦稱為希爾增量，但其實這個增量不是最優(yōu)的。

void ShellSort(int* h, size_t len)
{
    if(h == null) return;
    if(len <= 1) return;
    // 增量序列的個數(shù)就是對整個序列排序的次數(shù)
    // 增量gap，并逐步縮小gap
    for(int div = len/2; div >= 1; div/=2 )
    {
        for(k = 0; k <div; k++)
        {
            for(int i = div + k; i < len; i+=div)
            {
                for(int j = i; j > k; j -= div)
                {
                    if(h[j] < h[j - div]) swap(h[j], h[j - div]);
                    else break;
                }
            }
        }
    }
}

歸并排序

-步驟

當(dāng)我們拿到一個序列的時候：

我們先把它一份為二，像下面這樣：

繼續(xù)這樣的步驟，直到把這個細(xì)度分到每個部分只有一個元素為止：

image.png

現(xiàn)在我們已經(jīng)直到了這個算法的實現(xiàn)過程 ，但是分序列容易，歸并這件事情該如何完成呢？當(dāng)我們現(xiàn)在有了兩個已經(jīng)排好序的序列時，我們要把它們合并成一個有序的序列，要怎么辦效率比較高呢？
這里我們可以申請一塊內(nèi)存，用來存放將要合并好的序列，因為在現(xiàn)代計算機中，時間復(fù)雜度是要比空間復(fù)雜度要更優(yōu)先考慮的事情，畢竟內(nèi)存也好，硬盤也罷，現(xiàn)在是變得越來越能存儲了。（這里用了O(n)的額外空間來完成這件事件）
至于在歸并過程中使用插入算法還是快速排序那都是很隨意的。

這時我們連同額外申請的輔助內(nèi)存序列外，一共有了三個序列，所以這變成了一個具有三個索引的實現(xiàn)方法。

-理解

歸并排序是使用了分治的方法策略，將問題分成一個個小的部分然后遞歸求解，而治則是說將分的階段獲得的答案拼在一起。分而治之。
歸并排序可以使用遞歸的方法實現(xiàn)，也可以用迭代。遞歸和迭代這兩種算法思想也是非?；A(chǔ)和重要的，我會在專門的章節(jié)去學(xué)習(xí)理解。

分的階段可以采用遞歸的方法去拆分子序列，遞歸深度為log2n.
治的階段則是把兩個已經(jīng)有序的序列進(jìn)行合并。