Hill 정렬의 시간 복잡도는 O(n*log2n)이고 공간 복잡도는 O(1)입니다.
아이디어: 힐 정렬은 삽입 정렬 방법이기도 하며 실제로는 그룹화 삽입 방법입니다. 먼저 n보다 작은 정수 d1을 첫 번째 증분으로 결정하고 테이블의 모든 레코드를 d1 그룹으로 나누고 거리가 d1의 배수인 모든 레코드를 동일한 그룹에 넣은 다음 각 그룹 내에서 직접 삽입 정렬을 수행합니다. , 두 번째 증분 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 = data[j] //센티널
int k = jd;
for(; k >=0&& 임시 < 데이터[k]; k -=d)
{
데이터[k+d] =데이터[k];
}
데이터[k+d] =온도;
}
}
}
d = d/2;
}
}