欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

希尔排序( shell sort )

程序员文章站 2024-03-16 12:08:22
...

一、简介

增量序列:希尔排序使用一个序列h1,h2,…,ht,叫做增量序列。只要h1=1,任何增量序列都是可行的,不同增量序列有好坏之分

  • 在使用增量hk的一趟排序之后,对每个i都有a[ i ] <= a[ i + hk ]( 插入排序 ),所以相隔hk的元素都被排序。
  • 一个hk排序的文件( 此后将是hk-1 排序的)保持它的hk排序性

希尔排序思路:先按照增量序列进行分组再插入排序。

希尔序列:ht = N / 2 和 hk = hk+1 / 2

最坏时间复杂度:O( Nlog2N )

最好时间复杂度:O(Nlog2N )

平均时间复杂度:O( NlogN )

二、插入排序操作

希尔排序( shell sort )

将数组按增量序列 hk 分组,然后对每组进行插入排序,保留当前趟的排序,下一趟在上一趟的基础上进行排序,最终到 h1 = 1 对数组的所以元素进行一次插入排序,结束。

三、代码

/**
 * @description: 希尔排序 
 * @param {type} a 排序数组  
 * @return: null
 */
template < typename Comparable >
void shellsort( std::vector<Comparable> & a )
{
    for( int gap = a.size( ) / 2; gap > 0; gap /= 2 )       // 分组
        for( int i = gap; i < a.size( ); ++i )              // 对每组进行插入排序
        {
            Comparable tmp = std::move( a[ i ] );
            int j = i;
            for( ; j >= gap && tmp < a[ j - gap ]; j -= gap )
                a[ j ] = std::move( a[ j - gap ] );
            a[ j ] = std::move( tmp );
        }
}

int main( )
{
    int a[] = {1,8,7,5,90,8,4,2,7,6};
    std::vector<int> iv(a,a+sizeof(a)/sizeof(int));
    shellsort( iv );
    return 0;
}