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

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

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

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

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

    for(int i=0; (i<len) && exchange; i++)
    {
        exchange = false;

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

       測試代碼如下

#include <iostream>
#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;
    }
}

       我們來看看運行結(jié)果

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

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

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

       它是利用插入排序來實現(xiàn)的，之所以這么實現(xiàn)，是因為這樣的效率比之前的幾種能高點。下來我們來看看具體源碼的實現(xiàn)

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

    do
    {
        d = d / 3 + 1;   // 之所以這樣寫是因為經(jīng)過數(shù)學推導(dǎo)，這樣的效率是最高的。也可以寫成 d--;

        for(int i=d; i<len; i+=d)
        {
            int k = i;
            T e = array[i];

            for(int j=i-d; (j>=0) && (min2max ? (array[j]>e) : (array[j]<e)); j-=d)
            {
                array[j+d] = array[j];
                k = j;
            }

            if( k != i )
            {
                array[k] = e;
            }
        }
    } while( d > 1 );
}

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

       再來看看從大到小的排序

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

網(wǎng)頁名稱：冒泡排序和希爾排序（三十一）-創(chuàng)新互聯(lián)
網(wǎng)站鏈接：http://chinadenli.net/article6/eoeog.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、商城網(wǎng)站、定制開發(fā)、外貿(mào)網(wǎng)站建設(shè)、服務(wù)器托管、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)