当前位置: 首页> 文旅> 美景 > 排序算法之希尔排序

排序算法之希尔排序

时间:2025/7/12 2:03:11来源:https://blog.csdn.net/rd_w_csdn/article/details/141139842 浏览次数:0次

title: 希尔排序
date: 2024-7-25 10:48:15 +0800
categories:

  • 排序算法
    tags:
  • 排序
  • 算法
  • 希尔排序
    description: 1959年Shell发明,是简单插入排序的改进版。是一种高效的排序算法,通过分组和逐步缩减增量,使得数组在接近有序的情况下进行最终排序,从而提高效率。
    math: true

希尔排序

希尔排序(Shell Sort)是一种基于插入排序的排序算法,通过优化插入排序中的比较和移动操作,实现更高效的排序。希尔排序通过将数组分成若干子序列分别进行插入排序,使得数据项的步长逐渐减少,最终进行一次普通的插入排序。本文将详细介绍希尔排序的原理、步骤、示例、复杂度分析及其Java代码实现。

希尔排序的原理

  1. 分组:将待排序数组按某个增量分组,对每组分别进行插入排序。
  2. 缩减增量:逐步缩减增量,重复上述分组和排序过程。
  3. 最终排序:当增量缩减为1时,对整个数组进行一次普通的插入排序。

希尔排序通过多次分组和排序,使得数组在接近有序的情况下进行最终排序,从而提高效率。

希尔排序的步骤

  1. 选择初始增量:选择一个较大的初始增量(一般为数组长度的一半)。
  2. 分组并插入排序:按当前增量将数组分组,对每组分别进行插入排序。
  3. 缩减增量:将增量减半,重复分组和排序过程。
  4. 最终排序:当增量缩减为1时,对整个数组进行一次插入排序。

图示

希尔排序

示例

希尔排序示例

步长

  1. Shell 的原始序列: N 2 \frac{N}{2} 2N, N 4 \frac{N}{4} 4N , …, 1 (重复除以 2);

  2. Hibbard 增量: 1, 3, 7, …, 2 k − 1 2^k-1 2k1 ;

  3. Knuth 增量: 1, 4, 13, …, ( 3 k − 1 ) 2 \frac{(3^k-1)}{2} 2(3k1) ;

  4. Sedgewick 增量: 1, 5, 19, 41, 109, …
    它是通过将两个序列的元素交织得到的:

    1, 19, 109, 505, 2161,……, 9 ( 4 k – 2 k ) + 1 9(4^k–2^k)+1 9(4k2k)+1, k = 0, 1, 2, 3,…
    5, 41, 209, 929, 3905,…… 2 k + 2 ( 2 k + 2 – 3 ) + 1 2^{k+2}(2^{k+2}–3)+1 2k+2(2k+2–3)+1, k = 0, 1, 2, 3, …

复杂度分析

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序,最终算法以步长为1进行排序。当步长为1时,算法变为普通插入排序,这就保证了数据一定会被排序。

Donald Shell最初建议步长选择为 n 2 \frac {n}{2} 2n并且对步长取半直到步长达到1。虽然这样取可以比 O ( n 2 ) O(n^{2}) O(n2)类的算法(插入排序)更好,但这样仍然有减少平均时间和最差时间的余地。

步长序列最坏情况下复杂度
n 2 i \frac {n}{2^{i}} 2in O ( n 2 ) O(n^{2}) O(n2)
2 k − 1 2^{k}-1 2k1 O ( n 3 2 ) O(n^{\frac {3}{2}}) O(n23)
2 i 3 j 2^{i}3^{j} 2i3j O ( n log ⁡ 2 n ) O(n\log ^{2}n) O(nlog2n)

已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,…)。“比较在希尔排序中是最主要的操作,而不是交换。”用这样步长序列的希尔排序比插入排序要快,甚至在小数组中比快速排序和堆排序还快,但是在涉及大量数据时希尔排序还是比快速排序慢。

另一个在大数组中表现优异的步长序列是斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列:(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)

时间复杂度

  • 最佳情况 O ( n log ⁡ 2 n ) O(n \log^2 n) O(nlog2n)
  • 最坏情况 O ( n 2 ) O(n^2) O(n2)
  • 平均情况 O ( n 1.3 ) O(n^{1.3}) O(n1.3)

空间复杂度

  • 空间复杂度 O ( 1 ) O(1) O(1)

希尔排序的代码实现(Java)

public class ShellSort {// 主排序函数public static void shellSort(int[] arr) {int n = arr.length;// 选择初始增量for (int gap = n / 2; gap > 0; gap /= 2) {// 按增量进行插入排序for (int i = gap; i < n; i++) {int temp = arr[i];int j;// 插入排序for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}}// 主函数public static void main(String[] args) {int[] arr = {38, 27, 43, 3, 9, 82, 10};System.out.println("Given Array:");for (int num : arr) {System.out.print(num + " ");}System.out.println();// 调用希尔排序函数shellSort(arr);System.out.println("\nSorted Array:");for (int num : arr) {System.out.print(num + " ");}System.out.println();}
}
关键字:排序算法之希尔排序

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: