冒泡排序和希爾排序（三十一）

        在上節(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]。下來我們看看第 i 次冒泡排序示例，如下圖所示

為坪山等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計制作服務(wù)，及坪山網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為網(wǎng)站設(shè)計、網(wǎng)站建設(shè)、坪山網(wǎng)站設(shè)計，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎ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)進(jìn)行插入排序，以使整個序列基本有序，然后再對整個序列進(jìn)行插入排序。希爾排序示例如下

        我們來看看具體是怎么實現(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ù)學(xué)推導(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)了。通過對冒泡排序和希爾排序的學(xué)習(xí)，總結(jié)如下：1、冒泡排序每次從后向前將較小的元素交互到位；2、冒泡排序是一種穩(wěn)定的排序方法，其復(fù)雜度為O(n²)；3、希爾排序通過分組的方式進(jìn)行多次插入排序，它是一種不穩(wěn)定排序，其復(fù)雜度為O(n^3/2)。

當(dāng)前題目：冒泡排序和希爾排序（三十一）
分享鏈接：http://muchs.cn/article16/ghecgg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供虛擬主機(jī)、網(wǎng)站維護(hù)、定制開發(fā)、網(wǎng)站收錄、網(wǎng)站導(dǎo)航、商城網(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)