정렬 알고리즘 (6) - 힐 정렬 (셸 정렬)
2155 단어 정렬 알고리즘
의 원리
- 정렬 을 직접 삽입 하 는 최적화 알고리즘 – 배열 을 아래 표 시 된 일정한 증분 에 따라 그룹 을 나 누고 각 그룹 에 직접 정렬 을 삽입 합 니 다.증 량 이 점점 줄 어 들 면서 그룹의 요소 가 점점 많아 지고 증 량 이 1 일 때 까지 그룹 에 모든 요 소 를 포함 하고 정렬 이 완료 되면 알고리즘 이 결 제 됩 니 다.
주의 점
4. 567917. 최소 증 가 는 1 이 어야 합 니 다
4. 567917. 힐 의 정렬 이 각 조 에서 실 행 된 후에 정렬 이 완성 에 한 걸음 가 까 워 졌 기 때문이다.또 직접 삽입 정렬 이 정렬 에 가 까 울 수록 효율 이 높 기 때문이다.그래서 힐 의 정렬 은 직접 삽입 하 는 것 보다 우수 하 다 (비교 와 교환 횟수 가 적다)
예시
@Override
int[] sort(int[] data) {
int len = data.length;
// Hibbard
int hibbard = 1;
while(hibbard < len/2) {
hibbard = hibbard*2+1;
}
// ,
for (int i = hibbard; i > 0; i=(i-1)/2) {
// , j , i
for (int j = i; j < len; j+=i) {
int temp = data[j];//
int k = j - i;
while(k >= 0 && data[k] > temp) {
data[k+i] = data[k];
k-=i;
}
data[k+i] = temp;
}
}
return data;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
WEEK. 01 2022.04.03 TIL정렬(sorting)이란 이름, 학번, 학점 등의 키(key)를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 의미함. 정렬 알고리즘은 안정적인 알고리즘과 그렇지 않은 알고리즘으로 나...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.