Сортировка Шеллом — это разновидность сортировки вставками, более эффективная и улучшенная версия сортировки прямой вставкой, в которой в полной мере используются две характеристики сортировки вставками:
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 );}System.out.println();}publicstaticvoidmain(String[]args){int[]data=newint[]{4,6,1,9,5,8};print(data);shellSort(data );печатать(данные);}}Результаты бега следующие:
461958146958145698145689145689