希尔排序( 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 )
二、插入排序操作
将数组按增量序列 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;
}