希尔排序 java

1.定义：

希尔排序（Shell Sort）是一种插入排序的改进版，它通过将整个待排序的数组分成若干个子数组来进行排序，从而提高了排序的效率。希尔排序的主要思想是对插入排序进行优化，通过“间隔”来减少元素的移动距离，进而提高排序效率。

2.希尔排序的基本步骤

选择间隔（gap）序列：
希尔排序的核心在于选择一个适当的间隔序列（gap sequence），这个序列决定了排序时子数组的分组方式。常见的间隔序列有：

原始间隔序列：n/2, n/4, ..., 1（其中 n 是待排序数组的长度）
Hibbard 间隔序列：1, 3, 7, 15, 31, ...
Sedgewick 间隔序列：1, 5, 19, 41, 109, ...
按间隔进行插入排序：
对于每一个间隔值，使用该间隔值对数组进行插入排序。具体而言，将数组中的元素分成若干个子数组，每个子数组的元素在原始数组中的索引间隔为当前间隔值。

减少间隔并重复排序：
按照选定的间隔序列减少间隔，并重复插入排序，直到间隔缩小到1为止。

完成排序：
当间隔为1时，执行最后一轮插入排序，此时排序的效率显著提高。

示例代码
以下是 Java 语言中希尔排序的实现示例：java

public class ShellSort {public static void shellSort(int[] array) {int n = array.length;// 初始间隔值int gap = n / 2;// 逐步减少间隔值进行排序while (gap > 0) {// 对当前间隔值进行插入排序for (int i = gap; i < n; i++) {int temp = array[i];int j = i;while (j >= gap && array[j - gap] > temp) {array[j] = array[j - gap];j -= gap;}array[j] = temp;}// 减小间隔值gap /= 2;}}

 

   public static void main(String[] args) {int[] array = { 12, 34, 54, 2, 3 };System.out.println("Original array:");for (int value : array) {System.out.print(value + " ");}System.out.println();shellSort(array);System.out.println("Sorted array:");for (int value : array) {System.out.print(value + " ");}}
}

解释
gap：初始为数组长度的一半，之后逐步减小。
插入排序：对于每一个间隔值，使用插入排序来对这些子数组进行排序。元素之间的间隔为当前的 gap 值。
减少间隔：每完成一轮排序后，将间隔值减半，直到间隔值为1时结束。
性能
希尔排序的时间复杂度依赖于所选择的间隔序列。最坏情况下的时间复杂度为 (O(n^2))，而在实际使用中通常能达到 (O(n \log^2 n)) 或更好的性能。希尔排序的优点是其简洁性和较好的平均性能，使其在许多实际应用中非常有效。