데이터 구조 시리즈 의 힐 정렬 상세 설명

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&&temp

   k 층 순환 의 역할 을 주의 하 십시오. 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

좋은 웹페이지 즐겨찾기