This is the seventh day of my August challenge
Follow me for more updates
Data structure and algorithm (I): time complexity and space complexity
Data structure and algorithm (2): stack
Data structure and algorithm (3): queue
Data structure and algorithm (4): single linked list
Data structure and algorithm (5): two-way linked list
Data structure and algorithm (6): hash table
Data Structures and algorithms (7): trees
Data Structure and algorithm (8): sorting algorithm
Data Structures and algorithms (9): classical algorithm interview questions
As mentioned above, when the smaller number is at the back of the sequence, the number of backward moves increases significantly, which affects the efficiency. For this, Hill sort is optimized. Hill sort makes the sequence basically ordered by setting an incremental gap. Improved efficiency. This class is going to focus on the Hill order.
The basic idea
The entire sequence to be sorted is divided into several subsequences, and the subsequence is directly inserted into each subsequence. When the whole sequence is basically ordered, all elements are directly inserted into the sequence (that is, when the last loop gap=1). For (int gap = (int)arr.count/2; for (int gap = (int)arr.count/2; gap>0; Gap /=2) {gap = 1; When inserting the element ARR [I], it searches for the position to be inserted by jumping forward (jump amplitude is gap) from arR [i-gap]. In the process of searching, the element moves backward by jumping gap; In the entire sequence, the first gap element is the first element in the gap subsequence, so the insertion starts at gap+1.
Hill sort and byte insertion sort, there are exchange method and shift method, the exchange method is too inefficient, the code with shift method.
Code implementation
-(void)shellSort:(NSMutableArray*)arr{ int gap = (int)arr.count/2; while (gap>0) { for (int i = gap; i<arr.count; Int TMP = [arr[I] intValue]; int TMP = [arr[I] intValue]; int j = i; J /** while loop: jgap >=0; j /** while loop: jgap >=0; j /** while loop: jgap >=0; j /** while loop: jgap >=0; TMP < arr[j-gap]: if the value to be inserted is less than the next element to be compared; If both conditions are met, the element is moved back by gap positions; */ while (j-gap>=0 && TMP < [arr[j-gap] intValue]) {arr[j] = arr[j-gap]; // Move the preceding element back one bit j = j-gap; } arr[j] = @(TMP);} arr[j] = @(TMP); // Insert the element to be compared at the correct position} gap = gap/2; }}Copy the code// for (int gap = (int)arr.count/2; // for (int gap = (int)arr.count/2; gap>0; Gap /=2) {//① for (int I = gap; i<arr.count; Int TMP = [arr[I] intValue]; int TMP = [arr[I] intValue]; // int j = I; // int j = I; // int j = I; /** while loop condition: j-gap>=0: if next element >=0; TMP < arr[j-gap]: if the value to be inserted is less than the next element to be compared; If both conditions are met, the element is moved back by gap positions; While (j-gap>=0 && TMP < [arr[j-gap] intValue]) {/③ arr[j] = arr[j-gap]; // Move the front element back by gap positions j = j-gap; } arr[j] = @(TMP);} arr[j] = @(TMP); // Insert the element to be compared at the correct position}}}Copy the codeCode reading
(1) Gap starts at n, and each loop is divided by 2. This outer loop goes several times, and performs a sequence of direct insertion sorts on several wheels
TMP stores the value of arr[I], that is, the value to be inserted, so that it does not lose the contents of the element because the element is moved back
③ Conditions of the while loop:
J -gap>=0; j-gap>=0;
TMP < arr[j-gap]: if the value to be inserted is less than the next element to be compared; Move back
If both conditions are met, the element is shifted back gap positions;
When we exit the while loop, we find the right place to insert it directly into j
Hill sort versus direct insertion sort
Focus on
If you think MY writing is good, please click a like and follow me for continuous updates