쉘 정렬 은 삽입 정렬의 한 유형이며 직접 삽입 정렬의 보다 효율적이고 향상된 버전입니다. 쉘 정렬은 삽입 정렬의 두 가지 특성을 최대한 활용합니다.
1) 데이터 크기가 작을 때 매우 효율적이다.
2) 주어진 데이터가 이미 정렬되어 있는 경우의 시간 복잡도는 O(n)입니다.
따라서 쉘 정렬은 삽입 정렬을 사용하기 위해 매번 데이터를 여러 블록으로 나눈 다음, 정렬된 후 이 작은 블록을 더 큰 작은 블록으로 결합하고, 마지막 작은 블록이 나올 때까지 계속해서 삽입 정렬을 사용하여 작은 블록을 병합합니다. .
여기서, 여러 개의 작은 블록으로의 각 분할은 "증분"에 의해 제어됩니다. 처음에는 n/2에 가까운 증가량이 크므로 분할은 n/2개의 작은 블록에 가까워지며 "증분"은 점차적으로 증가합니다. 감소했습니다.”, 결국 1로 감소했습니다.
예를 들어:
publicclassMain{publicstaticintcount=0;publicstaticvoidshellSort(int[]data){//최대 h 값 계산 inth=1;while(h<=data.length/3){h=h*3+1;}while(h > 0){for(inti=h;i<data.length;i+=h){if(data[i]<data[ih]){inttmp=data[i];intj=ih;while(j>= 0&&data [j]>tmp){data[j+h]=data[j];j-=h;}data[j+h]=tmp;print(data);}}//다음 h 값 계산 h= (h-1)/3;}}publicstaticvoidprint(int[]data){for(inti=0;i<data.length;i++){System.out.print(data[i]+t) }시스템 .out.println();}publicstaticvoidmain(String[]args){int[]data=newint[]{4,6,1,9,5,8};print(data);shellSort(data); 데이터);}}실행 결과는 다음과 같습니다.
461958146958145698145689145689