데이터 구조 시리즈 의 힐 정렬 상세 설명
2093 단어 데이터 구조
1. 우선 정렬 삽입 의 원 리 를 파악 해 야 한다.
public void InsertSort(int data[]){ // （ ）
int temp;
int i,j;
for(i=1;i0&&temp 한 마디 만 기억 하 세 요: i 층 순환 은 요 소 를 선택 하 는 것 입 니 다. j 층 순환 은 선택 한 요 소 를 합 리 적 인 위치 에 놓 습 니 다.
2. 힐 정렬 의 원리
쉽게 말 하면 한 배열 을 몇 개의 작은 배열 로 나 눈 다음 에 모든 작은 배열 의 대응 요 소 를 정렬 에 삽입 한 다음 에 배열 을 다시 나 누 는 것 이다. 다만 이번에 분 단 된 작은 배열 의 개 수 는 처음 보다 많 고 모든 작은 배열 의 대응 요 소 를 정렬 에 삽입 하 는 것 이다.그리고 이 과정 을 반복 합 니 다. 모든 작은 배열 의 요소 개 수 는 1 입 니 다.
예 를 들 어 6, 3, 5, 9 에 대해 먼저 간격 을 2 로 나 누 면 이 배열 을 두 개의 작은 배열 6, 3 과 5, 9 로 나 눈 다음 에 각각 6, 5 와 3, 9 에 대해 삽입 순 서 를 사용 할 수 있다.이때 의 배열 은 5, 3, 6, 9 로 바 뀌 었 다가 배열 을 나 누 었 다. 이때 구분 간격 은 1 밖 에 되 지 않 기 때문에 5, 3, 6, 9 로 나 누 었 다. 이 배열 에 대해 삽입 정렬 을 사용 하면 힐 정렬 이 완성 된다.
3. 힐 정렬 사용 조건
이 원리 에서 볼 때 힐 정렬 을 사용 하려 면 마지막 으로 1 로 나 누 어야 하 며, 그렇지 않 으 면 힐 정렬 이 적용 되 지 않 는 다.
public boolean canUseShell(int a[],int groupNumber)
{
boolean b=false;
int m=a.length,n=groupNumber;
while(m!=0){
if(m/n==1){
b=true;
break;
}
m=m/n;
}
return b;
}이상 은 한 배열 이 힐 정렬 을 사용 할 수 있 는 지 를 판단 하 는 방법 을 제시 했다. 그 중에서 groupNumbe 는
배열 을 작은 배열 의 개수 로 나누다.
4. 힐 정렬 자바 구현
public void ShellSort(int a[]){
if(!this.canUseShell(a, 4)){
System.out.print(" ， ");
return;
}
int j;
int len = a.length;
for(int val=len/4; val>0; val/=4) {
//
for(int k=0;k<4;k++)
{
for(int i=val+k; i<=len-val; i+=val) {
int temp = a[i];
for(j=i; j>=val&&tempk 층 순환 의 역할 을 주의 하 십시오. k 층 이 없 으 면 모든 작은 배열 의 첫 번 째 요소 에 만 정렬 을 삽입 하 는 것 과 같 지만 작은 배열 의 다른 요 소 는 없습니다.
5. 테스트
public class Sort {
public static void main(String[] args) {
int a[]={2,3,6,-1,0,-4,6,-11,12,-5,21,10,12,45,23,67};
Sort s=new Sort();
s.ShellSort(a);
s.P(a); //
}결 과 는:
배열: - 11 -5 -4 -1 0 2 3 6 6 10 12 12 21 23 45 67
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
