在上節(jié)博客中，我們學(xué)習(xí)了插入排序和選擇排序，那么本次我們繼續(xù)學(xué)習(xí)冒泡排序和希爾排序。什么是冒泡排序呢？它是每次從后向前進(jìn)行（假設(shè)為第 i 次），j = n - 1, n - 2, ... , i, 兩兩比較 V[j-1] 和 V[j] 的關(guān)鍵字；如果發(fā)生逆序，則交換 V[j-1] 和 V[j]。下來(lái)我們看看第 i 次冒泡排序示例，如下圖所示

專注于為中小企業(yè)提供網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)潮州免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了上千家企業(yè)的穩(wěn)健成長(zhǎng)，幫助中小企業(yè)通過(guò)網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

        我們來(lái)看看具體是怎么實(shí)現(xiàn)的，如下所示

       我們看到它是兩兩比較，小的放在前面。類似于冒水泡，輕的漂浮在上面。下來(lái)我們來(lái)看看具體源碼的實(shí)現(xiàn)

template < typename T >
static void Bubble(T array[], int len, bool min2max = true)
{
    bool exchange = true;

    for(int i=0; (ii; j--)
        {
            if( min2max ? (array[j] < array[j-1]) : (array[j] > array[j-1]) )
            {
                Swap(array[j], array[j-1]);
                exchange = true;
            }
        }
    }
}

       測(cè)試代碼如下

#include 
#include "Sort.h"

using namespace std;
using namespace DTLib;

int main()
{
    int array[] = {3, 2, 4, 1, 5};

    Sort::Bubble(array, 5);

    for(int i=0; i<5; i++)
    {
        cout << array[i] << endl;
    }
}

       我們來(lái)看看運(yùn)行結(jié)果

       我們來(lái)試試在 Bubble 后面加上 false 參數(shù)，看看效果

       下來(lái)我們來(lái)繼續(xù)看看希爾排序，那么它的基本思想是什么呢？將待排序列劃分為若干組，在每一組內(nèi)進(jìn)行插入排序，以使整個(gè)序列基本有序，然后再對(duì)整個(gè)序列進(jìn)行插入排序。希爾排序示例如下

       我們來(lái)看看具體是怎么實(shí)現(xiàn)的，如下所示

       它是利用插入排序來(lái)實(shí)現(xiàn)的，之所以這么實(shí)現(xiàn)，是因?yàn)檫@樣的效率比之前的幾種能高點(diǎn)。下來(lái)我們來(lái)看看具體源碼的實(shí)現(xiàn)

template < typename T >
static void Shell(T array[], int len, bool min2max = true)
{
    int d = len;

    do
    {
        d = d / 3 + 1;   // 之所以這樣寫(xiě)是因?yàn)榻?jīng)過(guò)數(shù)學(xué)推導(dǎo)，這樣的效率是最高的。也可以寫(xiě)成 d--;

        for(int i=d; i=0) && (min2max ? (array[j]>e) : (array[j] 1 );
}

       我們先來(lái)看看不加參數(shù) false的效果（從小到大排序）

       再來(lái)看看從大到小的排序

       我們看到已經(jīng)正確實(shí)現(xiàn)了。通過(guò)對(duì)冒泡排序和希爾排序的學(xué)習(xí)，總結(jié)如下：1、冒泡排序每次從后向前將較小的元素交互到位；2、冒泡排序是一種穩(wěn)定的排序方法，其復(fù)雜度為O(n²)；3、希爾排序通過(guò)分組的方式進(jìn)行多次插入排序，它是一種不穩(wěn)定排序，其復(fù)雜度為O(n^3/2)。

分享標(biāo)題：冒泡排序和希爾排序（三十一）-創(chuàng)新互聯(lián)
URL分享：http://weahome.cn/article/eoeog.html