<> Shell Sort

Also called “ Reduce incremental sort ”, A more efficient and improved version of insert sorting

<> Basic principles

1, Select an increase h, According to the growth h As the basis for data grouping , Group data
2, Insert and sort each group of data divided into groups
3, Reduce growth , Until reduced to 1, Repeat step 2

<> growth

The rules for determining the growth are as follows

Find the maximum value of growth , Let's start first h=1, There are the following rules ：
int h = 1; while(h< Length of array /2){ h = 2h+1; }
Then reduce the growth according to the rules h
h = h/2;
Growth is used to control grouping

<> graphic

Suppose there is an array ：{9,1,2,5,7,4,8,6,3,5}
Count Reg 10, Therefore, the initial growth can be obtained from the above method as h=7, Further reduce the growth step by step , To group

When h = 7 Time

When h = 3 Time
When h=1 Time

<> Specific code
// Main ideas ： Group first , Then sort public class ShellSort { public static void main(String[] args
) { // Define an array int arr[] = {9,1,2,5,7,4,8,6,3,5}; // definition h To represent growth int h = 1; while(h<
arr.length){ h = 2*h+1; } while(h>=1){ // according to h Group , Find the element to be exchanged for(int i = h; i<arr.
length; i++){ for(int j = i; j>=h; j-=h){ // Compare and swap locations if(arr[j-h]>arr[j]){ int
temp; temp = arr[j-h]; arr[j-h] = arr[j]; arr[j] = temp; }else{
// Exit the cycle until the minimum number in this round is moved to the front break; } } } // narrow h Value of , Change growth h = h/2;
//System.out.println(h + "\n"); // This string of code can see the change of growth } for(int array : arr){ System.
out.print(array + " "); } } }
Maybe it's a little confusing , But that's the general meaning , Personal understanding , Please refer to the code for details , Step by step debugging , Well understood , If there is a mistake, please point out , Make progress together

Technology
Daily Recommendation