Shell의 정렬은 매우 "마법의"분류 알고리즘입니다. 아무도 성능이 실제로 달성 할 수있는 것을 명확하게 설명 할 수 없기 때문에 "마법"이라고합니다. DL이기 때문에 언덕 분류. Shell은 1959 년에 제안 된 이름을 따서 명명되었습니다. Car Hoare는 1962 년에 빠른 분류를 제안한 이래로 더 간단하기 때문에 빠른 분류를 사용합니다. 그러나 많은 수학자들은 여전히 언덕 분류의 최고의 복잡성을 찾고 있습니다. 평범한 프로그래머로서 우리는 Hill의 아이디어를 배울 수 있습니다.
그건 그렇고, 힐 분류가 나타나기 전에 컴퓨터 세계에는 "정렬 알고리즘이 O (N2)를 뚫을 수 없다"는 일반적인 견해가있었습니다. 언덕 분류의 출현은이 저주를 깨뜨 렸으며 곧 빠른 분류와 같은 알고리즘이 서로 방출되었습니다. 이런 의미에서, 언덕 분류는 우리를 새로운 시대로 이끌어줍니다.
알고리즘 개요/아이디어
언덕 분류 제안은 주로 다음 두 가지 요점을 기반으로합니다.
1. 삽입 분류 알고리즘은 배열을 기본적으로 주문할 때 대략 O (n) 복잡성을 달성하고 매우 효율적일 수 있습니다.
2. 그러나 삽입 분류는 한 번에 한 번씩 데이터 만 움직일 수 있으며 배열이 크고 기본적으로 무질서하면 성능이 빠르게 악화됩니다.
이를 바탕으로 그룹화 된 삽입 분류 방법을 사용할 수 있습니다.이 방법은 특정 방법입니다.
1. 1보다 큰 증분 델타를 선택하고 직접 삽입 분류를 위해이 증분으로 배열에서 서브 어레이를 선택하십시오. 예를 들어, 증분이 5 인 경우 첨자가 0, 5, 10, 15 인 요소가 정렬됩니다.
2. 증분 델타를 유지하고 라운드가 완료 될 때까지 삽입 및 정렬을 위해 첫 번째 요소를 차례로 움직입니다. 위의 예에서, 배열 [1, 6, 11], [2, 7, 12], [3, 8, 13], [4, 9, 14]는 차례로 정렬된다.
3. 증분을 줄이고 위의 프로세스를 1으로 줄일 때까지 계속해서 위의 프로세스를 반복하십시오. 분명히 마지막 시간은 직접 삽입 정렬입니다.
4. 정렬이 완료되었습니다.
위에서 볼 수 있듯이 증분은 지속적으로 감소하므로 언덕 분류는 다시 "감소 된 증분 분류"라고합니다.
코드 구현
패키지 정렬; 공개 클래스 shellsorttest {public static int count = 0; public static void main (String [] args) {int [] data = new int [] {5, 3, 6, 2, 9, 4, 8, 7}; 인쇄 (데이터); 쉘 소트 (데이터); 인쇄 (데이터); } 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; } 데이터 [j + h] = tmp; 인쇄 (데이터); }} // 다음 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 7 1 3 6 2 5 9 4 8 7 1 2 3 6 5 9 4 7 1 2 3 5 6 9 4 7 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 8 9
알고리즘 성능/복잡성
언덕으로 정렬 된 증분 시퀀스는 언제든지 취할 수 있으며, 유일한 요구 사항은 마지막 요구 사항이 1이어야한다는 것입니다 (1에 의해 주문되도록해야하기 때문에). 그러나 다른 시퀀스 선택은 알고리즘의 성능에 큰 영향을 미칩니다. 위의 코드는 두 가지 단위를 보여줍니다.
기억하십시오 : 증분 순서에서 두 요소마다 1 이외의 공통 요소를 갖지 않는 것이 가장 좋습니다! (분명히, 순서대로 2로 분류하는 것은 그리 의미가 없습니다).
아래는 몇 가지 일반적인 증분 순서입니다.
첫 번째 증분은 도널드 쉘 (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 (NN)는 빠릅니다. 쉘 분류는 많은 양의 데이터에 직면 할 때 좋은 알고리즘이 아닙니다. 그러나 중소형 데이터를 사용할 수 있습니다.