java 알고리즘의 힐 정렬 상세 및 실현 코드
생각
힐 정렬: 수조의 임의의 간격이 h인 원소를 질서정연하게 합니다.정렬을 진행할 때 만약에 h가 크다면 우리는 원소를 먼 곳으로 이동하여 더욱 작은 h질서를 실현하기 위해 편의를 만들 수 있다.이런 방식으로 임의로 1로 끝나는 h 서열에 대해 우리는 데이터를 정렬할 수 있다.
개념
h질서수조: 임의의 간격이 h인 원소는 모두 질서수조이다.
3. 효율적인 이유
대규모 난서수조에 대한 삽입 정렬은 매우 느리다. 왜냐하면 인접한 원소만 교환하기 때문에 원소는 수조의 한쪽에서 다른 단락으로 조금씩 이동할 수 밖에 없다.
힐 정렬이 더 효율적인 이유: 그것은 하위 그룹의 규모와 질서성을 평가하고 정렬 초기에 각 하위 그룹이 매우 짧았다.정렬 후 하위 그룹은 모두 부분적으로 질서정연한 것이기 때문에 이 두 가지 상황은 정렬을 삽입하기에 매우 적합하다.
4. 코드
/**
*
*
* @author pengcx
*
*/
public class Shell extends Sort {
public static void main(String[] args) {
String[] a = { "d", "a", "w", "b", "q" };
Shell.sort(a);
show(a);
}
/**
* a
*
* @param a
* a
*/
protected static void sort(Comparable[] a) {
int N = a.length;
int h = 1;
while (h < N / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = 0; i < N; i++) {
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
exch(a, j, j - h);
}
}
h = h / 3;
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
38. Java의 Leetcode 솔루션텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
