First take an integer d1 smaller than n as the first increment, and divide all records in the file into groups of d1. All records with multiples of distance dl are placed in the same group. First, directly insert the sorting in each group; then, take the second increment d2<d1 and repeat the grouping and sorting above until the increment dt=1(dt<dt-l<;…<d2<d1 ), that is, all records are placed in the same group and sorted directly.
This method is essentially a grouping insertion method.
Schematic:
source code
The code copy is as follows:
package com.zc.manythread;
/**
*
* @author I'm
*
*/
public class ShellSort {
public static int count = 0;
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();
}
public static void main(String[] args) {
int[] data = new int[] { 4, 3, 6, 2, 1, 9, 5, 8, 7 };
print(data);
shellSort(data);
print(data);
}
}
Running results:
Shell sorting is unstable, its space overhead is also O(1), and the time overhead is estimated to be between O(N3/2) and O(N7/6).