常用经典算法—希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。本文会以图解的方式详细介绍希尔排序的基本思想及其代码实现。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止.

在本文中我们选择增量group=length/2，缩小增量继续以group = group/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

#include <iostream>
int shellsort(int iArray[], int iArraySize)
{
    if (iArraySize < 0)
    {
        std::cout << "数组大小为空" << std::endl;
        return -1;
    }
    if (0 == iArraySize || 1 == iArraySize)
    {
        return 0;
    }
    int iGroup = 0;
    for (iGroup = iArraySize / 2; iGroup > 0; iGroup = iGroup / 2)
    {
        for (int i = iGroup; i < iArraySize; i++)
        {
            for (int j = i - iGroup; j >= 0; j = j - iGroup)
            {
                if (iArray[j] > iArray[j + iGroup])
                {
                    int iTmp = iArray[j];
                    iArray[j] = iArray[j + iGroup];
                    iArray[j + iGroup] = iTmp;
                }
            }
        }
    }
}

 

posted on 2018-04-02 12:48 newzol 阅读(…) 评论(…) 编辑 收藏
版权声明：本文为newzol原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/newzol/p/8692475.html