Hill 정렬 알고리즘 및 관련 Java 코드 구현에 대한 자세한 해석

쉘 정렬은 매우 "마법같은" 정렬 알고리즘입니다. 그 성능이 무엇인지 명확하게 설명할 수 있는 사람이 없기 때문에 이를 "마법적"이라고 부릅니다. DL로 인한 언덕 분류. Shell은 1959년에 제안된 이름을 따서 명명되었습니다. C. A. R. Hoare가 1962년에 퀵 정렬을 제안한 이후 퀵 정렬이 일반적으로 사용되는 이유는 퀵 정렬이 더 간단하기 때문입니다. 그러나 많은 수학자들은 여전히 ​​Hill 정렬의 최적 복잡성을 찾기 위해 끊임없이 노력하고 있습니다. 일반 프로그래머로서 우리는 Hill의 아이디어로부터 배울 수 있습니다.
그런데 힐 정렬이 등장하기 전에는 "정렬 알고리즘은 O(n2)를 돌파할 수 없다"는 것이 컴퓨터 업계의 공통된 견해였습니다. 힐 정렬(Hill Sorting)의 등장으로 이 저주가 깨졌고, 곧이어 퀵 정렬(Quick Sort)과 같은 알고리즘이 속속 등장했다. 이런 의미에서 힐 정렬은 우리를 새로운 시대로 인도합니다.

알고리즘 개요/아이디어
Hill 정렬 제안은 주로 다음 두 가지 사항을 기반으로 합니다.
1. 삽입 정렬 알고리즘은 기본적으로 배열을 정렬할 때 대략 O(n) 복잡도에 도달할 수 있습니다. . 학위, 매우 효율적입니다.
2. 그러나 삽입 정렬은 한 번에 한 비트씩만 이동할 수 있으며, 배열이 크고 기본적으로 무질서할 경우 성능이 빠르게 저하됩니다.

이를 바탕으로 그룹화된 삽입 정렬 방법을 사용할 수 있습니다. 구체적인 방법은 다음과 같습니다. (16개 요소 배열을 예로 사용)
1보다 큰 증분 델타를 선택합니다. . 직접 삽입 정렬의 경우 이 증분에 따라 배열에서 하위 배열을 선택합니다. 예를 들어 선택한 증분이 5인 경우 인덱스가 0, 5, 10, 15인 요소가 정렬됩니다.
2. 증분 델타를 유지하고 한 라운드가 완료될 때까지 직접 삽입 정렬을 위해 첫 번째 요소를 순서대로 이동합니다. 위의 예에서는 배열 [1, 6, 11], [2, 7, 12], [3, 8, 13], [4, 9, 14]가 순서대로 정렬됩니다.
3. 증분을 줄여서 증분이 1이 될 때까지 위의 과정을 반복합니다. 당연히 마지막은 직접 삽입 정렬입니다.
4. 정렬이 완료되었습니다.
위에서 알 수 있듯이 증분이 지속적으로 감소하므로 Hill 정렬을 "축소 증분 정렬"이라고도 합니다.

코드 구현

package sort; 
  
public class ShellSortTest { 
  public static int count = 0; 
  
  public static void main(String[] args) { 
  
    int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; 
    print(data); 
    shellSort(data); 
    print(data); 
  
  } 
  
  public static void shellSort(int[] data) { 
    // 计算出最大的h值 
    int h = 1; 
    while (h <= data.length / 3) { 
      h = h * 3 + 1; 
    } 
    while (h > 0) { 
      for (int i = h; i < data.length; i += h) { 
        if (data[i] < data[i - h]) { 
          int tmp = data[i]; 
          int j = i - h; 
          while (j >= 0 && data[j] > tmp) { 
            data[j + h] = data[j]; 
            j -= h; 
          } 
          data[j + h] = tmp; 
          print(data); 
        } 
      } 
      // 计算出下一个h值 
      h = (h - 1) / 3; 
    } 
  } 
  
  public static void print(int[] data) { 
    for (int i = 0; i < data.length; i++) { 
      System.out.print(data[i] + "\t"); 
    } 
    System.out.println(); 
  } 
  
}

실행 결과:

5  3  6  2  1  9  4  8  7   
1  3  6  2  5  9  4  8  7   
1  2  3  6  5  9  4  8  7   
1  2  3  5  6  9  4  8  7   
1  2  3  4  5  6  9  8  7   
1  2  3  4  5  6  8  9  7   
1  2  3  4  5  6  7  8  9   
1  2  3  4  5  6  7  8  9

알고리즘 성능/복잡성
Hill 정렬의 증분 순서는 임의로 선택할 수 있으며 필요한 유일한 조건은 마지막 하나는 1이어야 합니다(1로 정렬되어야 하기 때문). 그러나 다른 시퀀스 선택은 알고리즘 성능에 큰 영향을 미칩니다. 위의 코드는 두 가지 증분을 보여줍니다.
기억하세요: 증분 시퀀스의 두 요소마다 1 이외의 공통 인수를 갖지 않는 것이 가장 좋습니다! (분명히 4순으로 정렬한 다음 2순으로 정렬하는 것은 의미가 없습니다.)
다음은 몇 가지 일반적인 델타 시퀀스입니다.
첫 번째 증분은 원래 Donald Shell이 ​​제안한 증분으로, 1이 될 때까지 절반으로 줄어듭니다. 연구에 따르면 Hill 증분을 사용하면 시간 복잡도는 여전히 O(n2)입니다.
두 번째 증분 Hibbard: {1, 3, ..., 2^k-1}. 이 증분 시퀀스의 시간 복잡도는 대략 O(n^1.5)입니다.
세 번째 증분 Sedgewick 증분: (1, 5, 19, 41, 109,...), 생성된 시퀀스는 9*4^i - 9*2^i + 1 또는 4^ i - 3*입니다. 2^i + 1.

알고리즘 안정성
삽입 정렬이 안정적인 알고리즘이라는 것은 모두가 알고 있는 사실입니다. 그러나 쉘 정렬은 다중 삽입 프로세스입니다. 한 번의 삽입에서는 동일한 요소의 순서가 이동되지 않도록 할 수 있지만 여러 삽입에서는 동일한 요소가 다른 삽입 라운드에서 이동될 수 있으며 결국 안정성이 손상됩니다. 따라서 쉘 정렬 알고리즘은 안정적이지 않습니다. .

알고리즘 적용 시나리오
쉘 정렬은 빠르지만 결국 삽입 정렬이고 크기 순서는 라이징 스타-퀵 정렬 O(n㏒n)만큼 빠르지 않습니다. 쉘 정렬은 많은 양의 데이터에 직면하여 좋은 알고리즘이 아닙니다. 그러나 중소 규모의 데이터에는 완벽하게 적합합니다.

Hill 정렬 알고리즘에 대한 자세한 설명과 관련 Java 코드 구현 관련 기사는 PHP 중국어 사이트를 주목해주세요!