Hill ソートの時間計算量は O(n*log2n)、空間計算量は O(1) です。これは不安定なソート アルゴリズムです。
アイデア: ヒル ソートも挿入ソート手法であり、実際にはグループ化挿入手法です。まず、最初の増分として n より小さい整数 d1 を決定し、テーブル内のすべてのレコードを d1 グループに分割し、距離が d1 の倍数であるすべてのレコードを同じグループに入れ、各グループ内で直接挿入ソートを実行します。 、2 番目の増分 d2 (<d1) を取得し、取得した増分 dt=1 (dt<dt-1<...<d2<d1) になるまで、つまりすべてのレコードが直接挿入ソートが実行されるまでは同じグループです。
次のようにコードをコピーします。
void ShellSort(int* データ,int 長)
{
if( データ == NULL || 長さ <= 0 )
戻る;
int d = 長さ/2;
一方(d)
{
for(int i = 0; i < d; ++i) //ステップサイズに応じてグループに分け、グループごとにインサートソート
{
//挿入ソート
for(int j = i+d; j <長さ ; j +=d )
{
if(データ[j] < データ[j -d])
{
int temp = データ[j]; //センチネル
int k = jd;
for(; k >=0&& temp < data[k]; k -=d)
{
データ[k+d] = データ[k];
}
データ[k+d] = 温度;
}
}
}
d = d/2;
}
}