Java를 사용하여 힐 정렬 알고리즘을 구현하는 간단한 예
힐 정렬 (축소 증량법) 은 삽입 클래스 정렬에 속한다. 셸에 의하면 힐 정렬은 직접 삽입 정렬에 대해 간단하게 개선했다. 힐 정렬은 삽입 정렬에서 요소 간의 간격을 확대하고 이 간격이 있는 요소에 삽입 정렬을 해서 항목을 크게 이동시킨다. 이 데이터 항목이 한 번 정렬된 후에 힐 정렬 알고리즘은 데이터 항목의 간격을 줄이고 순서대로 정렬한다.이러한 정렬을 할 때의 데이터 항목 사이의 간격을 증량이라고 하는데, 습관적으로 알파벳 h로 이 증량을 표시한다.
자주 사용하는 h 시퀀스는 Knuth에서 제안합니다. 이 시퀀스는 1부터 시작하여 다음과 같은 공식을 통해 생성됩니다.
h = 3 * h +1
h=(h-1)/3
구현 코드 1:
public static void shellSort(int[] arr){
int temp;
for (int delta = arr.length/2; delta>=1; delta/=2){ //
for (int i=delta; i<arr.length; i++){
for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ // delta
temp = arr[j-delta];
arr[j-delta] = arr[j];
arr[j] = temp;
}
}//loop i
}//loop delta
}
public static void shellSort2(int[] arr){
int delta = 1;
while (delta < arr.length/3){//generate delta
delta=delta*3+1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
}
int temp;
for (; delta>=1; delta/=3){
for (int i=delta; i<arr.length; i++){
for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){
temp = arr[j-delta];
arr[j-delta] = arr[j];
arr[j] = temp;
}
}//loop i
}//loop delta
}
셸 정렬이 불안정하고 공간 비용도 O(1)이며 시간 비용은 O(N3/2)~O(N7/6) 사이로 추정된다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
