수색…
셸 기본 정보 정렬
감소 정렬 (increment increment sort )이라고도 알려진 쉘 정렬 은 발명가 인 Donald의 이름을 따서 명명 된 가장 오래된 정렬 알고리즘 중 하나입니다 . L. Shell (1959). 이해하기 쉽고 구현하기 쉽습니다. 그러나 복잡성 분석은 좀 더 정교합니다.
쉘 정렬의 아이디어는 다음과 같습니다.
- 데이터 시퀀스를 2 차원 배열로 정렬
- 배열 열 정렬
쉘 정렬은 삽입 정렬을 개선합니다. 먼저 멀리 떨어진 요소를 비교 한 다음 멀리 떨어져있는 요소를 비교하고 마지막으로 인접한 요소를 비교하여 시작합니다 (효과적으로 삽입 정렬).
결과적으로 데이터 시퀀스가 부분적으로 정렬됩니다. 위의 프로세스가 반복되지만 매번 더 좁은 배열, 즉 더 적은 수의 열로 반복됩니다. 마지막 단계에서 배열은 단 하나의 열로 구성됩니다.
셸 정렬의 예 :
셸 정렬에 대한 의사 코드 :
input
foreach element in input
{
for(i = gap; i < n; i++)
{
temp = a[i]
for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
{
a[j] = a[j - gap]
}
a[j] = temp
}
}
보조 공간 : O(n) total, O(1) auxiliary
시간 복잡성 : O(nlogn)
C # 구현
public class ShellSort
{
static void SortShell(int[] input, int n)
{
var inc = 3;
while (inc > 0)
{
int i;
for (i = 0; i < n; i++)
{
var j = i;
var temp = input[i];
while ((j >= inc) && (input[j - inc] > temp))
{
input[j] = input[j - inc];
j = j - inc;
}
input[j] = temp;
}
if (inc / 2 != 0)
inc = inc / 2;
else if (inc == 1)
inc = 0;
else
inc = 1;
}
}
public static int[] Main(int[] input)
{
SortShell(input, input.Length);
return input;
}
}
Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow