48_冒泡排序和希尔排序

关键词：冒泡排序、希尔排序

0. 冒泡排序

思想：每次从后向前进行（假设为第i次），j=n-1, n-2, ..., i,两两比较v[j-1]和v[j]的关键字；如果发生逆序，则交换v[j-1]和v[j]。

template < typename T >
    static void Bubble(T array[], int len, bool min2max = true) // O(n^2)
    {
        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;
                }
            }
        }
    }

1. 希尔排序

思想：将待排序列划分为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排序。

希尔排序示例

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

        do
        {
            d = d / 3 + 1;  // 改变增量

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

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

                if( pos != i )
                {
                    array[pos] = value;
                }
            }

        }while(d > 1);
    }len;

2. 小结

• 冒泡排序每次从后向前将较小的元素交换位置
• 冒泡排序是一种稳定的排序法，时间复杂度为O(n^2)
• 希尔排序通过分组的方式进行多次插入排序
• 希尔排序是一种不稳定的排序法，时间复杂度为O(n^3/2)

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4