首页 > 代码库 > 希尔排序总结

希尔排序总结

数据结构之排序算法——希尔排序

 

代码很多地方借鉴了  http://my.csdn.net/MoreWindows 他的思想,

本人认为该作者已经写的很好了,只是在他的基础上加入了一些自己的理解和说明

如果涉及到版权的问题,请联系我的邮箱,我会尽快删除

 希尔排序想关链接:

维基百科: https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F#C.E8.AA.9E.E8.A8.80

百度百科:http://baike.baidu.com/view/178698.htm

参考博客 :http://blog.csdn.net/morewindows/article/details/6668714

 

希尔排序:其实就是分组的插入排序

 

希尔排序基本思想是:

       在无序的数组中定义一个增量,然后用增量将数组分成几个部分,每个部分进行插入排序,然后减少增量的大小,继续进行插入排序,直到最后增量为1,进行最后的排序操作

 

我看到两种增量的定义方式

  第一种是 先将数组的长度赋值3/1 +1给增量,然后让增量等于自己的3/1 +1,保证每次增量的大小不小于 1,结束条件是增量不小于 1

     注意: 使用这个方式一定要注意增量是永远大于等于1 的,因此一个好的处理方式是使用do {}while();

  第二种是将数组将数组的长度除以2赋值给增量,然后让增量等于自己的1/2 结束条件是增量小于1

其实增量的定义只是在分组的时候,确定每个组数据的规模,没什么需要去深究的!

 

利用第一个增量方式的源码:

void Shell_Sort(int array[], int arrayLen)

{

    // 定义一个增量

    int Incremental = arrayLen;

    do 

    {

        Incremental = Incremental / 3 + 1;

        for (int i = 0; i < Incremental;++ i)

        {

            for (int j = i + Incremental; j < arrayLen; j += Incremental)

            {

                // 从大到小

                if (array[j - Incremental] < array[j])

                {

                    int InsertNum = array[j];

                    int k = j-Incremental;

                    while (k >= 0 && array[k] < InsertNum)

                    {

                        array[k+ Incremental] = array[k];

                        k -= Incremental;

                    }

                    array[k + Incremental] = InsertNum;

                }

            }

        }

    } while (Incremental > 1);

}

 

利用第二个增量方式的源码

void Shell_Sort(int array[], int arrayLen)

{

    // 确认每次增量的大小

    for (int Incremental = arrayLen / 2; Incremental > 0; Incremental /= 2)

    {

        // 分组进行插入排序

        for (int i = 0; i < Incremental; ++ i)

        {

            for (int j = i + Incremental; j < arrayLen; j+= Incremental)

            {

                // 从大到小

                if (array[j - Incremental] < array[j])

                {

                    int InsertNum = array[j];

                    int k = j-Incremental;

                   

                    while (k >= 0 && array[k] < InsertNum)

                    {

                        array[k + Incremental] = array[k];

                        k -= Incremental;

                    }

                    array[k + Incremental] = InsertNum;

                }

            }

           

        }

    }

}

 

针对第二种方案的一些优化:主要是对开始位置的优化,在插入排序中,每次查找与前面的大小关系时都从已经有序的位置开始,在希尔排序的每个分组里面我们也可以这样认为,这样,我们每次从增量开始,寻找增量和它前面的分组的数的关系,然后进行大小的调整

源码如下

void Shell_Sort(int array[], int arrayLen)

{

    for (int Incremental = arrayLen / 2; Incremental > 0; Incremental /= 2)

    {

        // 分组进行插入排序

        for (int i = Incremental; i < arrayLen; ++ i)

        {

            // 由大到小

            if (array[i] > array[i - Incremental])

            {

                int InsertNum = array[i];

                int j = i - Incremental;

               

                // 注意分析 j 和 InsertNum 代表的数据的位置,结合整体的大小顺序

                while (j >= 0 && array[j] < InsertNum) 

                {

                    array[j + Incremental] = array[j];

                    j -= Incremental;

                }

                array[j + Incremental] = InsertNum;

            }

        }

    }

}

 

还可以进一步把第二次优化的的最后的一个for(){}和下面的if()语句合并,然后用数据的移动来代替,查找插入位置

源码:

void Shell_Sort(int array[], int arrayLen)

{

    for (int Incremental = arrayLen / 2; Incremental > 0; Incremental /= 2)

    {

        // 分组进行插入排序

        for (int i = Incremental; i < arrayLen; ++i)

        {

            for (int j = i - Incremental; j >=0 && array[j] < array[j + Incremental]; j -= Incremental)

            {

                Swap_IntVal(array + j, array + j + Incremental);

            }

        }

    }

}

 

希尔排序总结