Shell Sort is a type of insertion sort and a more efficient and improved version of direct insertion sort. Shell Sort makes full use of two characteristics of insertion sort:
1) Very efficient when the data size is small.
2) The time complexity when the given data is already sorted is O(n).
Therefore, Shell sorting divides the data into several blocks each time to use insertion sort, and then combines these small blocks into larger small blocks after they are sorted, and continues to use insertion sort to continuously merge small blocks. chunks until the last little chunk.
Here, each division into several small blocks is controlled by "increment". At the beginning, the increment is large, close to n/2, so that the division is close to n/2 small blocks, and the "increment" is gradually reduced. ”, eventually reduced to 1.
For example:
publicclassMain{publicstaticintcount=0;publicstaticvoidshellSort(int[]data){//Calculate the maximum h value 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);}}//Calculate the next h value 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); print(data);}}The running results are as follows:
461958146958145698145689145689