Java Hill 정렬의 예에 대한 자세한 설명

이 글은 주로 Hill 정렬의 Java 데이터 구조와 알고리즘을 소개하고, Hill 정렬의 개념, 원리, 구현 방법 및 관련 주의사항을 예제 형식으로 분석하여 도움이 필요한 친구들이 참고할 수 있습니다

이 기사의 예에서는 Java 데이터 구조 및 알고리즘의 Hill 정렬을 설명합니다. 참고하실 수 있도록 공유해 드리며, 자세한 내용은 다음과 같습니다.

제가 여기서 소개하고 싶은 것은 Hill 정렬(축소 증분 정렬 방법)입니다.

힐 정렬: 은 특정 거리만큼 떨어져 있는 요소를 비교하는 방식으로 작동합니다. 마지막 정렬까지 인접한 요소만 비교할 때까지 알고리즘이 진행됨에 따라 각 비교에 사용되는 거리(증분)가 감소합니다. 요소의. 삽입 정렬의 일종으로 직접 삽입 정렬 알고리즘을 개선한 것입니다.

알고리즘 아이디어: 먼저 정렬할 시퀀스를 특정 증분 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("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    shell(array);
  }
}

알고리즘 분석: 이 알고리즘은 다양한 단계 크기에 따라 요소를 삽입하고 정렬합니다. .처음에 요소가 매우 무질서한 경우 단계 크기가 가장 크므로 삽입 정렬의 요소 수가 매우 적고 요소가 기본적으로 정렬되면 속도가 매우 빠릅니다. , 삽입 정렬은 순서가 지정된 시퀀스에 매우 효율적입니다. 따라서 Hill 정렬의 시간 복잡도는 O(n^1.5)인 O(n^2)보다 낫고 정렬 효율은 훨씬 높습니다. 삽입 정렬 . 다중 삽입 정렬로 인해 우리는 하나의 삽입 정렬이 안정적이며 동일한 요소의 상대적 순서를 변경하지 않는다는 것을 알고 있습니다. 그러나 다른 삽입 정렬 프로세스에서는 동일한 요소가 각각의 삽입 정렬에서 이동할 수 있으며 최종적으로 안정성이 향상됩니다. 변경이 중단되어 쉘 정렬이 불안정합니다. 힐 정렬은 퀵 정렬 알고리즘 O(N*(logN))만큼 빠르지 않기 때문에 중간 크기의 데이터를 정렬하는 데 더 적합하지만 매우 큰 데이터를 정렬하는 데는 최적의 선택이 아닙니다. . 그러나 O(N^2) 복잡도 알고리즘보다 훨씬 빠릅니다. 그리고 Hill 정렬은 구현하기가 매우 쉽고, 알고리즘 코드도 짧고 간단합니다. 또한 최악의 경우 Hill 알고리즘의 성능 효율성은 평균의 경우와 차이가 크지 않은 반면, 퀵 정렬의 경우 최악의 경우 효율성이 매우 떨어지게 됩니다.

【관련 추천사항】

1. 특별 추천: "php Programmer Toolbox" V0.1 버전 다운로드

2. Java 무료 동영상 튜토리얼

3. YMP 온라인 매뉴얼

위 내용은 Java Hill 정렬의 예에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!