Shell's sort is a very "magical" sorting algorithm. It is said to be "magical" because no one can clearly explain what its performance can actually achieve. Hill sorting because DL. Shell was named after it was proposed in 1959. Since CAR Hoare proposed quick sorting in 1962, it is generally used quick sorting because it is simpler. However, many mathematicians are still tirelessly looking for the best complexity of Hill sorting. As ordinary programmers, we can learn Hill's ideas.
By the way, before Hill sorting appeared, there was a general view in the computer world that "sorting algorithms cannot break through O(n2)". The emergence of Hill sorting broke this curse, and soon, algorithms such as quick sorting were released one after another. In this sense, Hill sorting leads us to a new era.
Algorithm overview/ideas
The proposal of Hill sorting is mainly based on the following two points:
1. The insertion sorting algorithm can approximately achieve O(n) complexity and extremely efficient when the array is basically ordered.
2. However, insertion sorting can only move data by one bit at a time, and the performance will deteriorate rapidly when the array is large and basically disordered.
Based on this, we can use a grouped insert sorting method, which is the specific method: (Take an array of 16 elements as an example)
1. Select an increment delta, which is greater than 1, and select the subarray from the array by this increment for direct insertion sorting. For example, if the increment is 5 is selected, the elements with subscripts 0, 5, 10, 15 are sorted.
2. Keep the increment delta and move the first element in turn for insertion and sorting until the round is completed. For the example above, the arrays [1, 6, 11], [2, 7, 12], [3, 8, 13], [4, 9, 14] are sorted in turn.
3. Reduce the increment and repeat the above process continuously until the increment decreases to 1. Obviously, the last time is the direct insert sort.
4. Sorting is completed.
As can be seen from the above, the increment is constantly decreasing, so Hill sorting is again called "reduced increment sorting".
Code implementation
package sort; public class ShellSortTest { public static int count = 0; public static void main(String[] args) { int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; print(data); shellSort(data); print(data); } public static void shellSort(int[] data) { // Calculate the maximum h value int h = 1; while (h <= data.length / 3) { h = h * 3 + 1; } while (h > 0) { for (int i = h; i < data.length; i += h) { if (data[i] < data[i - h]) { int tmp = data[i]; int j = i - h; 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; } } public static void print(int[] data) { for (int i = 0; i < data.length; i++) { System.out.print(data[i] + "/t"); } System.out.println(); } } Running results:
5 3 6 2 1 9 4 8 7 1 3 6 2 5 9 4 8 7 1 2 3 6 5 9 4 8 7 1 2 3 5 6 9 4 8 7 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Algorithm performance/complexity
The incremental sequences sorted by Hill can be taken at any time, and the only requirement is that the last one must be 1 (because it is necessary to ensure that it is ordered by 1). However, different sequence selection will have a huge impact on the performance of the algorithm. The above code demonstrates two increments.
Remember: It is best not to have common factors other than 1 for every two elements in the incremental sequence! (Obviously, sorting by 2 in sequence is not very meaningful).
Below are some common incremental sequences.
The first increment is the initially proposed by Donald Shell, i.e., the fold is reduced to 1. According to research, using Hill increments, the time complexity is still O(n2).
The second increment Hibbard: {1, 3, ..., 2^k-1}. The time complexity of this incremental sequence is approximately O(n^1.5).
The third increment Sedgewick increment: (1, 5, 19, 41, 109,...), which generates a sequence either 9*4^i - 9*2^i + 1 or 4^i - 3*2^i + 1.
Algorithm stability
We all know that insertion sorting is a stable algorithm. However, shell sorting is a process of multiple insertions. In one insertion we can ensure that the order of the same elements is not moved, but in multiple insertions, it is entirely possible that the same elements are moved in different insertion rounds, and the stability is finally destroyed. Therefore, shell sorting is not a stable algorithm.
Algorithm applicable scenarios
Although shell sorting is fast, it is insert sorting after all, and its order of magnitude is not as good as the rising star - quick sorting O(nn) is fast. Shell sorting is not a good algorithm in the face of a large amount of data. However, it is completely possible to use small and medium-sized data.