java 版本的希尔排序
时间: 2023-02-15 16:42:36 浏览: 58
希尔排序是一种插入排序,它的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组被称为 h 有序数组。希尔排序是将每个 h 有序数组看成一个小的有序数组,然后对所有的 h 有序数组进行插入排序。
具体的,首先选择一个增量 h,然后将数组分成若干个 h 有序的子数组。接着对每个 h 有序的子数组进行插入排序。最后逐渐减小 h 的值,并重复以上步骤,直到 h=1 为止。
下面是 java 代码实现:
```
public class ShellSort {
public static void sort(int[] array) {
int h = 1;
while (h < array.length / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < array.length; i++) {
for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
int temp = array[j];
array[j] = array[j - h];
array[j - h] = temp;
}
}
h /= 3;
}
}
}
```
希尔排序的时间复杂度为 O(n^(3/2))。