其實(shí)寫(xiě)排序算法的博客已經(jīng)有很多了砂轻，其中不乏某些細(xì)心的博主去仔細(xì)講解各種排序的過(guò)程，甚至有使用gif圖來(lái)表現(xiàn)排序過(guò)程的博客斤吐，還有對(duì)已有排序算法進(jìn)行改進(jìn)的搔涝，我表示很佩服這些博主，謝謝你們和措。

這里附上一些我參考過(guò)的博客：
7種排序算法（系列博客） - 靜默虛空
常用排序算法總結(jié)(一) - SteveWang
[直觀學(xué)習(xí)排序算法] 視覺(jué)直觀感受若干常用排序算法 - todayx
白話經(jīng)典算法系列 - MoreWindows
常用排序算法穩(wěn)定性庄呈、時(shí)間復(fù)雜度分析 - jiuyueguang
八大排序算法

然后附上我重新寫(xiě)的排序算法

這里的排序算法示例都用函數(shù)模板來(lái)寫(xiě)

• 簡(jiǎn)單排序算法：
  • 選擇排序
  • 冒泡排序
  • 插入排序
• 復(fù)雜排序算法：
  • 快速排序
  • 歸并排序
  • 堆排序
  • shell排序

選擇排序

• 原理：遍歷元素集合，每次遍歷找到剩下的集合中最大\最小的元素放入已排序集合中派阱，直到找完為止诬留。
• 時(shí)間復(fù)雜度：O(n^2)
• 空間復(fù)雜度：O(1)
• 算法穩(wěn)定性：不穩(wěn)定排序。使用序列6 9 6 3 2來(lái)舉例贫母，第一個(gè)6與3交換文兑，導(dǎo)致第一個(gè)6排到了第二個(gè)6后面，所以選擇排序是不穩(wěn)定的排序算法腺劣。
• 算法示例：

template <class T>
void sort_array_select(T* dataArray, int dataSize)
{
    //遍歷數(shù)據(jù)集合
    for (int i = 0; i < dataSize; i++)
    {
        //記錄最小索引
        int minIndex = i;
        //遍歷剩余數(shù)據(jù)集合
        for (int j = i; j < dataSize; j++)
        {
            //查找更小的值
            if (dataArray[minIndex] > dataArray[j])
            {   
                //保存更小值的索引
                minIndex = j;
            }
        }
        //判斷當(dāng)前索引處是否是最小值
        if (minIndex != i)
        {
            //將找到的最小值與當(dāng)前索引處的值交換
            T temp = dataArray[i];
            dataArray[i] = dataArray[minIndex];
            dataArray[minIndex] = temp;
        }
    }
}

冒泡排序

• 原理：遍歷元素集合绿贞，依次比較相鄰元素，將相鄰元素中較大\較小者移向一端橘原，每次遍歷找到剩余數(shù)據(jù)集合中較大\較小者籍铁，直到全部排序完成。
• 時(shí)間復(fù)雜度：
  • 最佳（已經(jīng)順序排好的集合）：O(n)
  • 最差（已經(jīng)逆序拍好的集合）：O(n^2)
• 空間復(fù)雜度：O(1)
• 算法穩(wěn)定性：穩(wěn)定的排序趾断。因?yàn)楸容^與交換均發(fā)生在相鄰的元素之間寨辩，對(duì)于兩個(gè)相等的元素不會(huì)進(jìn)行交換，所以是穩(wěn)定的排序歼冰。
• 算法示例：

template <class T>
void sort_array_bubble(T* dataArray, int dataSize)
{
    //遍歷集合
    for (int i = 0; i < dataSize; i++)
    {
        //遍歷剩余元素集合
        for (int j = 0; j < dataSize - i - 1; j++)
        {
            //比較相鄰元素大小
            if(dataArray[j] > dataArray[j + 1])
            {
                //將較大元素后移
                T temp = dataArray[j];
                dataArray[j] = dataArray[j + 1];
                dataArray[j + 1] = temp;
            }
        }
    }
}

插入排序

• 原理：將數(shù)據(jù)集合中第一個(gè)數(shù)據(jù)視為已排序集合靡狞，依次獲取未排序集合中的元素，將獲取到的元素插入到已排序集合中的正確位置隔嫡，直到全部排序完成甸怕。
• 時(shí)間復(fù)雜度：
  • 最佳（已排序集合）：O(n)
  • 最差（逆序已排序集合）：O(n^2)
• 空間復(fù)雜度：O(1)
• 算法穩(wěn)定性：穩(wěn)定的排序算法甘穿。因?yàn)楸容^的過(guò)程發(fā)生在相鄰元素之間，對(duì)于相等的元素梢杭，算法中不會(huì)改變他們的相對(duì)位置温兼，所以是穩(wěn)定的排序算法。
• 算法示例：

template <class T>
void sort_array_insert(T* dataArray, int dataSize)
{
    //遍歷數(shù)據(jù)集合（從1開(kāi)始武契，0號(hào)元素已排序）
    for (int i = 1; i < dataSize; i++)
    {
        //獲取未排序集合中第一個(gè)元素
        T temp = dataArray[i];
        int j = i;
        //依次與已排序集合中元素比較募判，找到正確位置
        while(j > 0 && temp < dataArray[j - 1])
        {
            dataArray[j] = dataArray[j - 1];
            j--;
        }
        //取到的元素放入已排序列表中正確位置
        dataArray[j] = temp;
    }
}

快速排序

• 原理：應(yīng)用了分治的思想和以遞歸取代循環(huán)的思想。取一個(gè)元素作為flag咒唆，并將數(shù)據(jù)集合分為大于（等于）flag和小于（等于）flag兩個(gè)子集届垫，然后對(duì)子集進(jìn)行同樣的操作，直到子集元素個(gè)數(shù)為1或0全释，則所有元素完成排序装处。
• 時(shí)間復(fù)雜度：
  • 最差（每次取到的flag都在邊界）：O(n^2)
  • 最佳（每次取到的flag都在中間）：O(nlog2n)
• 空間復(fù)雜度：O(1)
• 算法穩(wěn)定性：不穩(wěn)定的排序。因?yàn)楸容^和替換不是發(fā)生在相鄰元素之間浸船，而是從某個(gè)方向開(kāi)始找到滿足條件的值妄迁，然后進(jìn)行替換，這樣可能導(dǎo)致兩個(gè)相同元素的相對(duì)位置變化李命，所以是不穩(wěn)定的排序方式登淘。
• 算法示例：

template <class T>
void sort_array_quick(T* dataArray, int left, int right)
{
    //遞歸退出條件
    if (left >= right)
    {
        return;
    }
    //取flag，并控制左右范圍
    T flag = dataArray[left];
    int sub_left = left;
    int sub_right = right;
    //根據(jù)flag來(lái)整理數(shù)據(jù)集合
    while(sub_left < sub_right)
    {
        //在右側(cè)找小的值換到左側(cè)
        //此時(shí)dataArray[sub_left]中的值是冗余的
        while (sub_left < sub_right && dataArray[sub_right] >= flag)
        {
            sub_right--;
        }
        if (sub_left < sub_right)
        {
            dataArray[sub_left] = dataArray[sub_right];
        }
        //在左側(cè)找大的值換到右側(cè)
        //此時(shí)dataArray[sub_right]中的值是冗余的
        while (sub_left < sub_right && dataArray[sub_left] <= flag)
        {
            sub_left++;
        }
        if (sub_left < sub_right)
        {
            dataArray[sub_right] = dataArray[sub_left];
        }
    }
    //上面的步驟進(jìn)行完成后封字，dataArray[sub_left]中的值是冗余的黔州，這里將flag放回
    dataArray[sub_left] = flag;
    //以flag為中心，左側(cè)的值小于等于flag周叮，右側(cè)的值大于等于flag
    //分別對(duì)左側(cè)的值的集合和右側(cè)的值的集合進(jìn)行遞歸再次排序劃分
    sort_array_quick(dataArray, left, sub_left - 1);
    sort_array_quick(dataArray, sub_left + 1, right);
}

歸并排序

• 原理：應(yīng)用了分治的思想和以遞歸取代循環(huán)的思想辩撑。將待排序數(shù)據(jù)集合劃分為兩個(gè)子集，對(duì)子集分別進(jìn)行排序仿耽，排序完成后將兩個(gè)有序子集中的元素合冀。
• 時(shí)間復(fù)雜度：O(nlog2n)
• 空間復(fù)雜度：O(n)
• 算法穩(wěn)定性：穩(wěn)定的排序算法。在元素集合被拆分為n個(gè)子集合之后项贺，合并集合時(shí)君躺，是通過(guò)對(duì)已排序集合中值最相近的兩個(gè)元素進(jìn)行比較并存儲(chǔ)的，所以不會(huì)造成值相同的元素相對(duì)位置變化开缎。
• 算法示例：

//按順序合并集合
template <class T>
void array_merge(T* dataArray, int left, int mid, int right, T* sortedArray)
{
    int i = left;
    int j = mid + 1;
    int count = 0;
    
    //將dataArray中l(wèi)eft->mid和mid+1->right部分的元素按順序放入sortedArray中
    while (i <= mid && j <= right)
    {
        if (dataArray[i] < dataArray[j])
        {
            sortedArray[count++] = dataArray[i++];
        }
        else
        {
            sortedArray[count++] = dataArray[j++];
        }
    }
    
    //剩余元素直接放入sortedArray
    while (i <= mid)
    {
        sortedArray[count++] = dataArray[i++];
    }
    while (j <= right)
    {
        sortedArray[count++] = dataArray[j++];
    }
    
    //排序好的元素放回dataArray
    for (int i = 0; i < count; i++)
    {
        dataArray[left + i] = sortedArray[i];
    }
}

//拆分集合
template <class T>
void sort_array_merge(T* dataArray, int left, int right, T* sortedArray)
{
    //遞歸停止條件
    if (left >= right)
    {
        return;
    }
    
    //集合分為兩個(gè)子集
    int mid = (left + right) / 2;
    //繼續(xù)拆分
    sort_array_merge(dataArray, left, mid, sortedArray);
    sort_array_merge(dataArray, mid + 1, right, sortedArray);
    
    //按順序合并集合
    array_merge(dataArray, left, mid, right, sortedArray);
}

堆排序

• 原理：應(yīng)用了二叉堆的特點(diǎn)棕叫，即父節(jié)點(diǎn)的值總是大于（小于）子節(jié)點(diǎn)的值。這樣每一次將待排序集合調(diào)整為堆時(shí)奕删，便能得到待排序集合中的一個(gè)最值俺泣。堆排序分為兩步：第一步是建立堆，將無(wú)序的集合調(diào)整為滿足堆的條件的集合；第二步是依次取得最值伏钠，此時(shí)只破壞了堆頂横漏，以堆頂為根進(jìn)行一次調(diào)整，形成一個(gè)新的堆熟掂，然后循環(huán)第二步缎浇。
• 時(shí)間復(fù)雜度：O(nlog2n)
• 空間復(fù)雜度：O(1)
• 算法穩(wěn)定性：不穩(wěn)定的排序算法。因?yàn)楸容^與交換不是發(fā)生在相鄰元素之間赴肚，兩個(gè)相同的元素相鄰時(shí)會(huì)被分配到不同的子樹(shù)中素跺，在調(diào)整子樹(shù)時(shí)可能導(dǎo)致值相同的元素的相對(duì)位置發(fā)生變化。
• 算法示例：

//調(diào)整為最大堆,保證父節(jié)點(diǎn)值大于子節(jié)點(diǎn)
template <class T>
void heap_update(T* dataArray, int rootIndex, int arraySize)
{
    //遞歸終止條件誉券，rootIndex處應(yīng)為非葉子節(jié)點(diǎn)
    if (rootIndex >= arraySize / 2)
    {
        return;
    }
    
    //計(jì)算左右子節(jié)點(diǎn)的index
    int left_child = rootIndex * 2 + 1;
    int right_child = rootIndex * 2 + 2;
    
    //查找父指厌、左子、右子節(jié)點(diǎn)中最大值
    int largest = rootIndex;
    
    if (left_child < arraySize && dataArray[left_child] > dataArray[largest])
    {
        largest = left_child;
    }
    if (right_child < arraySize && dataArray[right_child] > dataArray[largest])
    {
        largest = right_child;
    }
    //將最大值替換到父節(jié)點(diǎn)位置
    if (largest != rootIndex)
    {
        T temp = dataArray[rootIndex];
        dataArray[rootIndex] = dataArray[largest];
        dataArray[largest] = temp;
        
        //largest所處位置元素相對(duì)其子節(jié)點(diǎn)來(lái)說(shuō)横朋，又是一個(gè)被破壞的堆頂仑乌，所以繼續(xù)調(diào)整
        heap_update(dataArray, largest, arraySize);
    }
    
    //對(duì)左右子節(jié)點(diǎn)分別進(jìn)行調(diào)整
    //heap_update(dataArray, left_child, arraySize);
    //heap_update(dataArray, right_child, arraySize);
}

//建立堆百拓。即逆序?qū)λ蟹侨~子節(jié)點(diǎn)進(jìn)行一次堆調(diào)整琴锭。
template <class T>
void heap_build(T* dataArray, int arraySize)
{
    for (int i = arraySize / 2 - 1; i >= 0; i--)
    {
        heap_update(dataArray, i, arraySize);
    }
}

//堆排序
template <class T>
void sort_array_heap(T* dataArray, int arraySize)
{
    //建立堆
    heap_build(dataArray, arraySize);
    
    //循環(huán)獲得堆頂元素并調(diào)整堆
    int count = arraySize;
    while (count > 1)
    {
        //將堆頂元素與待排序數(shù)組末尾元素交換
        T temp = dataArray[0];
        dataArray[0] = dataArray[count - 1];
        dataArray[count - 1] = temp;
        
        //調(diào)整堆,只破壞了堆頂，這里以堆頂為root衙传，對(duì)待排序的部分進(jìn)行堆調(diào)整
        count--;
        heap_update(dataArray, 0, count);
    }
}

shell排序

• 原理：對(duì)直接插入法排序的改良决帖。因?yàn)橹苯硬迦敕ㄅ判蛟谠鼗居行虻那闆r下效率最高，所以將待排序元素依次劃分為n組（n為size/2蓖捶，size/4地回，... 首先保持元素?cái)?shù)量最少，組內(nèi)排序完成后再重新劃分為元素更多的組俊鱼，保持直接插入法的高效）刻像，然后對(duì)組內(nèi)進(jìn)行直接插入法排序。
• 時(shí)間復(fù)雜度：
  • 最差：O(n^2)
  • 最佳(有序排列的集合)：O(nlog2n)
• 空間復(fù)雜度：O(1)
• 算法示例：

template <class T>
void sort_array_shell(T* dataArray, int arraySize)
{
    //使用step劃分組
    for (int step = arraySize / 2; step > 0; step /= 2)
    {
        //逐個(gè)元素進(jìn)行組內(nèi)插入排序
        for (int i = step; i < arraySize; i++)
        {
            //組內(nèi)直接插入排序
            T temp = dataArray[i];
            int k = i - step;
            //在組內(nèi)依次向前查找正確位置
            while (k >= 0 && dataArray[k] > temp)
            {
                dataArray[k + step] = dataArray[k];
                k -= step;
            }
            //元素插入到正確位置
            dataArray[k + step] = temp;
        }
    }
}

上面所有的算法示例在排序一個(gè)int類型的數(shù)組時(shí)并闲，是正诚杆可用的。但是很多都有優(yōu)化的空間（比如看到一篇博客中對(duì)插入法排序?qū)懥硕喾N實(shí)現(xiàn)方法）帝火，而且使用臨時(shí)變量來(lái)交換兩個(gè)值的過(guò)程也值得思考溜徙。

總結(jié)：以上排序算法只是提供一種思想，在我們面臨遍歷大量數(shù)據(jù)犀填、從大量數(shù)據(jù)中查找某個(gè)值等問(wèn)題的時(shí)候蠢壹，其中的某些點(diǎn)是可以借鑒的。其中的分段九巡、構(gòu)建二叉樹(shù)的思想是很值得學(xué)習(xí)的图贸，以此告誡自己思維不要太刻板。