Shell Sort
Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort. But Hill sort is an unstable sort algorithm.
Hill sort is an improved method based on the following two properties of insertion sort:
- Insertion sort has high efficiency when it operates on almost ordered data, that is, it can achieve the efficiency of linear sort.
- But insert sort is generally inefficient because it can only move data one bit at a time;
The basic idea of Hill sorting is that the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion sorting respectively. When the records in the whole sequence are “basically ordered”, the whole records are directly inserted in sequence.
Algorithm description
- Select a delta sequence T1, T2… , where Ti >tj, tk=1;
- Sort the sequence k times according to the number of incremental sequences k;
- In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.
example
Array:8 9 1 7 2 3 5 4 6 0Narrow the increment: gap = length/2 = 5Grouping:8.3] [9.5] [1.4] [7.6] [2.0[First time:3 5 1 6 0 8 9 4 7 2Narrow the increment: gap = gap/2 = 5/2 = 2Grouping:3.1.0.9.7] [5.6.8.4.2[Second time:0 2 1 4 3 5 7 6 9 8Narrow the increment: gap = gap/2 = 2/2 = 1The third time:0 1 2 3 4 5 6 7 8 9The end of theCopy the code
It’s basically insertion sort plus incremental grouping to sort.
Algorithm complexity
Space complexity: O(1)
Time complexity:
Sorting is unstable, and two previously equal parameters may be ranked first.
Code implementation
public static void shellSort(int[] arr) {
int len = arr.length;
for (int gap =len / 2; gap > 0; gap = gap / 2) {
for (int i = gap; i < len; i++) {
int j = i;
int current = arr[i];
while (j - gap >= 0&& current < arr[j - gap]) { arr[j] = arr[j - gap]; j = j - gap; } arr[j] = current; } System.out.println(Arrays.toString(arr)); }}Copy the code
The results
Input array:int[] arr = {8.9.1.7.2.3.5.4.6.0};
[3.5.1.6.0.8.9.4.7.2]
[0.2.1.4.3.5.7.6.9.8]
[0.1.2.3.4.5.6.7.8.9]
Copy the code
But following the steps above, at this point we can see that the results are consistent.