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

在上节博客中，我们学习了插入排序和选择排序，那么本次我们继续学习冒泡排序和希尔排序。什么是冒泡排序呢？它是每次从后向前进行（假设为第 i 次），j = n - 1, n - 2, ... , i, 两两比较 V[j-1] 和 V[j] 的关键字；如果发生逆序，则交换 V[j-1] 和 V[j]。下来我们看看第 i 次冒泡排序示例，如下图所示

为坪山等地区用户提供了全套网页设计制作服务，及坪山网站建设行业解决方案。主营业务为网站设计、网站建设、坪山网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

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

我们来看看具体是怎么实现的，如下所示

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

我们看到它是两两比较，小的放在前面。类似于冒水泡，轻的漂浮在上面。下来我们来看看具体源码的实现

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;
    }
}

我们来看看运行结果

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

我们来试试在 Bubble 后面加上 false 参数，看看效果

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

下来我们来继续看看希尔排序，那么它的基本思想是什么呢？将待排序列划分为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排序。希尔排序示例如下

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

我们来看看具体是怎么实现的，如下所示

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

它是利用插入排序来实现的，之所以这么实现，是因为这样的效率比之前的几种能高点。下来我们来看看具体源码的实现

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

    do
    {
        d = d / 3 + 1;   // 之所以这样写是因为经过数学推导，这样的效率是最高的。也可以写成 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 );
}

我们先来看看不加参数 false的效果（从小到大排序）

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