Hark 의 데이터 구조 와 알고리즘 연습 의 힐 정렬
1552 단어 데이터 구조 와 알고리즘
힐 정렬 은 정렬 을 삽입 하 는 최적화 판 이다.
정렬 을 삽입 하 는 최 악의 시간 복잡 도 는 O (n2) 이지 만 정렬 하려 는 배열 이 거의 질서 있 는 수열 이 라면 시간 복잡 도 를 효과적으로 낮 출 수 있다.
힐 정렬 의 목적 은 하나의 increment (증분) 를 통 해 수열 그룹 을 교환 하여 정렬 하 는 것 이다. 최종 적 으로 수열 을 거의 질서 있 게 하고 마지막 에 삽입 정렬 을 실행 하여 결 과 를 집계 하 는 것 이다.
increment = n / 2, 즉 9 개의 수 를 통 해 증 가 량 은 4, 2, 1 이다. 20 개 라면 10, 5, 2, 1 이다. increment 가 1 일 때 거의 질서 있 는 수열 에 정렬 을 삽입 합 니 다.
시간 복잡 도
O(n2/3)
공간 복잡 도
O(1)
코드
자바
/*
*
*/
public class ShellSort {
public static void main(String[] args) {
int[] arrayData = { 5, 9, 6, 7, 4, 1, 2, 3, 8 };
ShellSortMethod(arrayData);
for (int integer : arrayData) {
System.out.print(integer);
System.out.print(" ");
}
}
public static void ShellSortMethod(int[] arrayData) {
int i, j, temp = 0;
int increment = arrayData.length;
do {
increment = increment / 2; //
for (i = increment; i < arrayData.length; i++) {
if (arrayData[i] > arrayData[i - increment]) { //
temp = arrayData[i]; //
// ， ， 。
//temp > arrayData[j] ，
for (j = i - increment; j >= 0 && temp > arrayData[j]; j -= increment) {
arrayData[j + increment] = arrayData[j];
}
arrayData[j + increment] = temp;
}
}
} while (increment > 0);
}
}
결실
9 8 7 6 5 4 3 2 1
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[JAVA] 배열 회전 출력요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
