힐 정렬 알고리즘과 관련된 자바 코드 세밀한 해석 실현

힐 정렬(Shell's sort)은 매우 신기한 정렬 알고리즘이다.그것이'신기하다'고 말하는 것은 그 성능이 도대체 어떤 상황에 도달할 수 있는지 아무도 명확하게 설명할 수 없기 때문이다.힐 정렬은 DL. Shell이 1959년에 제출한 것으로 이름을 얻었다.C.A.R.Hoare가 1962년에 빠른 정렬을 제기한 후, 더욱 간단하기 때문에 일반적으로 빠른 정렬을 채택한다.그러나 많은 수학자들은 힐 서열의 가장 좋은 복잡도를 끊임없이 찾고 있다.일반 프로그래머로서 우리는 힐의 사고방식을 배울 수 있다.
참고로 힐 정렬이 등장하기 전에 컴퓨터계에는'정렬 알고리즘이 O(n2)를 돌파할 수 없다'는 관점이 보편적으로 존재했다.힐 정렬의 출현은 이 저주를 깨뜨렸고, 곧 빠른 정렬 등 알고리즘이 잇따라 나왔다.이런 의미에서 볼 때, 힐 서열은 우리를 새로운 시대로 이끌었다.
알고리즘 개요/사고방식
힐 정렬의 제시는 주로 다음과 같은 두 가지를 바탕으로 한다.
1. 삽입 정렬 알고리즘은 수조가 기본적으로 질서정연한 상황에서 O(n)의 복잡도에 가깝고 효율이 매우 높다.
2. 그러나 삽입 정렬은 매번 데이터를 한 자리만 이동할 수 있으며, 수조가 비교적 크고 기본적으로 무질서한 상황에서 성능이 빠르게 악화될 수 있다.
이를 바탕으로 우리는 그룹을 나누는 삽입 정렬 방법을 사용할 수 있다. 구체적인 방법은 다음과 같다. (16원소 크기의 그룹을 예로 들면)
1. 증량델타를 선택하십시오. 이 증량은 1보다 크고, 수조에서 이 증량에 따라 하위 수조를 선택하여 직접 삽입하여 정렬합니다.예를 들어, 증분 값을 5로 선택하면 아래 0, 5, 10, 15로 표시된 요소를 정렬합니다.
2. 이 증가분delta를 보존하고 첫 번째 요소를 순서대로 이동하여 순서가 끝날 때까지 직접 삽입합니다.위의 예에 대해 순서대로 수조[1,6,11],[2,7,12],[3,8,13],[4,9,14]를 정렬한다.
3. 증량을 줄이고 상술한 과정을 끊임없이 반복한다. 증량이 1로 줄어들 때까지.분명히 마지막으로 정렬을 직접 삽입합니다.
4. 정렬이 완료됩니다.
위에서 볼 수 있듯이 증량은 끊임없이 줄어들기 때문에 힐 정렬은 또'증량 정렬 축소'가 되었다.
코드 구현

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 

알고리즘 성능/복잡도
힐 정렬의 증량 수열은 임의로 취할 수 있으며, 필요한 유일한 조건은 마지막에 반드시 1이어야 하기 때문이다.그러나 서로 다른 수열 선택은 알고리즘의 성능에 큰 영향을 미칠 수 있다.위의 코드는 두 가지 증량을 보여 주었다.
주의: 증량 서열에 있는 두 원소는 1 이외의 공인자가 나타나지 않는 것이 가장 좋다!(분명히 네 개의 질서정연한 수열에 따라 두 개의 정렬을 하는 것은 의미가 크지 않다.)
다음은 흔히 볼 수 있는 증량 서열이다.
첫 번째 증량은 처음에 Donald Shell이 제시한 증량입니다. 즉, 1까지 반으로 줄이는 것입니다.연구에 따르면 힐 증량을 사용하면 그 시간 복잡도는 역시 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(nSn)가 빠르다.대량의 데이터 앞에서 셸 정렬은 좋은 알고리즘이 아니다.그러나 중소형 규모의 데이터는 충분히 사용할 수 있다.