자바 데이터 구조 와 알고리즘 힐 정렬 상세 설명

본 고의 실례 는 자바 데이터 구조 와 알고리즘 의 힐 정렬 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다. 구체 적 으로 는 다음 과 같 습 니 다.
여기 서 소개 하고 자 하 는 것 은 힐 정렬 이다.
힐 정렬: 일정한 간격 을 가 진 요 소 를 비교 하여 작업 합 니 다.각 비교 에 사용 되 는 거리 (증분) 는 알고리즘 이 진행 되면 서 인접 요소 의 마지막 정렬 만 비교 할 때 까지 줄어든다.정렬 을 삽입 하 는 일종 으로 정렬 알고리즘 을 직접 삽입 하 는 개선 입 니 다.
알고리즘 사상: 먼저 정렬 할 서열 을 특정한 증 량 d 에 따라 몇 개의 하위 서열 로 나 누고 각 하위 서열 에 있 는 모든 요 소 를 직접 삽입 하여 정렬 한 다음 에 작은 증 량 으로 나 누 어 각 그룹 에서 정렬 합 니 다.증 량 이 1 로 줄 어 들 면 전체 정렬 할 수 는 한 그룹 으로 나 뉘 어 정렬 이 완 료 됩 니 다.주의: 증 량 의 수치 - 일반적인 첫 번 째 추출 서열 의 절반 은 증 량 이 고 그 후에 매번 반 으로 줄 어 들 며 증 량 이 1 이 될 때 까지 합 니 다.
알고리즘 구현 코드 는 다음 과 같 습 니 다.

package exp_sort;
public class ShellSort {
  public static void shell(int array[]) {
    int j;
    int average;
    //      
    for (average = array.length / 2; average > 0; average /= 2) { //  
      for (int i = average; i < array.length; i++) { //           
        int temp = array[i];
        for (j = i; j >= average && temp < array[j - average]; j -= average) {
          array[j] = array[j - average];
        }
        array[j] = temp;
      }
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("
");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    shell(array);
  }
}

알고리즘 분석: 이 알고리즘 은 동기 화 되 지 않 은 길이 에 따라 요 소 를 삽입 하여 정렬 하 는 것 입 니 다. 처음에 요소 가 무질서 할 때 걸음 길이 가 가장 크기 때문에 정렬 된 요소 의 개수 가 적 고 속도 가 빠 릅 니 다.요소 가 기본적으로 질서 가 있 고 걸음 길이 가 작 으 며 정렬 을 삽입 하 는 것 은 질서 있 는 서열 효율 이 높다.따라서 힐 의 정렬 시간 은 O (n ^ 2) 보다 복잡 도가 좋 고 O (n ^ 1.5) 로 정렬 효율 이 삽입 정렬 보다 훨씬 높다.여러 번 정렬 을 삽입 하기 때문에 우 리 는 한 번 의 삽입 정렬 이 안정 적 이 고 같은 요소 의 상대 적 인 순 서 를 바 꾸 지 않 는 다 는 것 을 알 고 있 습 니 다. 그러나 서로 다른 삽입 정렬 과정 에서 같은 요 소 는 각자 의 삽입 정렬 에서 이동 할 수 있 고 마지막 에 안정성 이 흐 트 러 지기 때문에 셸 정렬 은 불안정 합 니 다.힐 정렬 은 빠 른 정렬 알고리즘 인 빠 른 O (N * (logN) 가 없 기 때문에 중간 크기 의 데이터 정렬 에 적용 되 며 규모 가 매우 큰 데이터 정렬 에 최 적 화 된 선택 이 아 닙 니 다.하지만 O (N ^ 2) 보다 복잡 도 알고리즘 이 훨씬 빠르다.또한 힐 의 정렬 은 매우 쉬 워 서 알고리즘 코드 가 짧 고 간단 하 다.또한 힐 알고리즘 은 최 악의 경우 와 평균 상황 에서 집행 효율 의 차이 가 많 지 않 으 며, 동시에 빠 른 정렬 은 최 악의 경우 에 집행 하 는 효율 이 매우 떨어진다.
자바 알고리즘 과 관련 된 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.,,,,,,
본 고 에서 말 한 것 이 여러분 의 자바 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.