devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

希尔排序算法

作者：知新_RL | 2024-07-26 15:29:36

赞

踩

希尔排序

本章介绍排序算法中的希尔排序。内容包括：
1. 希尔排序介绍
2. 希尔排序图文说明
3. 希尔排序的时间复杂度和稳定性
4. 希尔排序实现
4.1 希尔排序C实现
4.2 希尔排序C++实现
4.3 希尔排序Java实现

转载请注明出处：希尔排序 - 如果天空不死 - 博客园

更多内容：数据结构与算法系列 目录

希尔排序介绍

希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

希尔排序实质上是一种分组插入方法。它的基本思想是：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。

希尔排序图文说明

希尔排序代码(一)

  1. /*
  2.  * 希尔排序
  3.  *
  4.  * 参数说明：
  5.  *     a -- 待排序的数组
  6.  *     n -- 数组的长度
  7.  */
  8. void shell_sort1(int a[], int n)
  9. {
  10.     int i,j,gap;
  11.  
  12.     // gap为步长，每次减为原来的一半。
  13.     for (gap = n / 2; gap > 0; gap /= 2)
  14.     {
  15.         // 共gap个组，对每一组都执行直接插入排序
  16.         for (i = 0 ;i < gap; i++)
  17.         {
  18.             for (j = i + gap; j < n; j += gap) 
  19.             {
  20.                 // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
  21.                 if (a[j] < a[j - gap])
  22.                 {
  23.                     int tmp = a[j];
  24.                     int k = j - gap;
  25.                     while (k >= 0 && a[k] > tmp)
  26.                     {
  27.                         a[k + gap] = a[k];
  28.                         k -= gap;
  29.                     }
  30.                     a[k + gap] = tmp;
  31.                 }
  32.             }
  33.         }
  34.  
  35.     }
  36. }

在上面的希尔排序中，首先要选取步长gap的值。选取了gap之后，就将数列分成了gap个组，对于每一个组都执行直接插入排序。在排序完所有的组之后，将gap的值减半；继续对数列进行分组，然后进行排序。重复这样的操作，直到gap<0为止。此时，数列也就是有序的了。

为了便于观察，我们将希尔排序中的直接插入排序独立出来，得到代码(二)。

希尔排序代码(二)

  1. /*
  2.  * 对希尔排序中的单个组进行排序
  3.  *
  4.  * 参数说明：
  5.  *     a -- 待排序的数组
  6.  *     n -- 数组总的长度
  7.  *     i -- 组的起始位置
  8.  *     gap -- 组的步长
  9.  *
  10.  *  组是"从i开始，将相隔gap长度的数都取出"所组成的！
  11.  */
  12. void group_sort(int a[], int n, int i,int gap)
  13. {
  14.     int j;
  15.  
  16.     for (j = i + gap; j < n; j += gap) 
  17.     {
  18.         // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
  19.         if (a[j] < a[j - gap])
  20.         {
  21.             int tmp = a[j];
  22.             int k = j - gap;
  23.             while (k >= 0 && a[k] > tmp)
  24.             {
  25.                 a[k + gap] = a[k];
  26.                 k -= gap;
  27.             }
  28.             a[k + gap] = tmp;
  29.         }
  30.     }
  31. }
  32.  
  33. /*
  34.  * 希尔排序
  35.  *
  36.  * 参数说明：
  37.  *     a -- 待排序的数组
  38.  *     n -- 数组的长度
  39.  */
  40. void shell_sort2(int a[], int n)
  41. {
  42.     int i,gap;
  43.  
  44.     // gap为步长，每次减为原来的一半。
  45.     for (gap = n / 2; gap > 0; gap /= 2)
  46.     {
  47.         // 共gap个组，对每一组都执行直接插入排序
  48.         for (i = 0 ;i < gap; i++)
  49.             group_sort(a, n, i, gap);
  50.     }
  51. }

下面以数列{80,30,60,40,20,10,50,70}为例，演示它的希尔排序过程。

第1趟：(gap=4)

当gap=4时,意味着将数列分为4个组： {80,20},{30,10},{60,50},{40,70}。 对应数列： {80,30,60,40,20,10,50,70}
对这4个组分别进行排序，排序结果： {20,80},{10,30},{50,60},{40,70}。 对应数列： {20,10,50,40,80,30,60,70}


第2趟：(gap=2)

当gap=2时,意味着将数列分为2个组：{20,50,80,60}, {10,40,30,70}。 对应数列： {20,10,50,40,80,30,60,70}
注意：{20,50,80,60}实际上有两个有序的数列{20,80}和{50,60}组成。
          {10,40,30,70}实际上有两个有序的数列{10,30}和{40,70}组成。
对这2个组分别进行排序，排序结果：{20,50,60,80}, {10,30,40,70}。 对应数列： {20,10,50,30,60,40,80,70}

第3趟：(gap=1)

当gap=1时,意味着将数列分为1个组：{20,10,50,30,60,40,80,70}
注意：{20,10,50,30,60,40,80,70}实际上有两个有序的数列{20,50,60,80}和{10,30,40,70}组成。
对这1个组分别进行排序，排序结果：{10,20,30,40,50,60,70,80}

希尔排序的时间复杂度和稳定性

希尔排序时间复杂度
希尔排序的时间复杂度与增量(即，步长gap)的选取有关。例如，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)，而Hibbard增量的希尔排序的时间复杂度为O(N3/2)。

希尔排序稳定性
希尔排序是不稳定的算法，它满足稳定算法的定义。对于相同的两个数，可能由于分在不同的组中而导致它们的顺序发生变化。
算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

希尔排序实现

希尔排序C实现
实现代码(shell_sort.c)

  1. /**
  2.  * 希尔排序：C 语言
  3.  *
  4.  * @author skywang
  5.  * @date 2014/03/11
  6.  */
  8. #include <stdio.h>
  9.  
  10. // 数组长度
  11. #define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )
  12.  
  13. /*
  14.  * 希尔排序
  15.  *
  16.  * 参数说明：
  17.  *     a -- 待排序的数组
  18.  *     n -- 数组的长度
  19.  */
  20. void shell_sort1(int a[], int n)
  21. {
  22.     int i,j,gap;
  23.  
  24.     // gap为步长，每次减为原来的一半。
  25.     for (gap = n / 2; gap > 0; gap /= 2)
  26.     {
  27.         // 共gap个组，对每一组都执行直接插入排序
  28.         for (i = 0 ;i < gap; i++)
  29.         {
  30.             for (j = i + gap; j < n; j += gap)
  31.             {
  32.                 // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
  33.                 if (a[j] < a[j - gap])
  34.                 {
  35.                     int tmp = a[j];
  36.                     int k = j - gap;
  37.                     while (k >= 0 && a[k] > tmp)
  38.                     {
  39.                         a[k + gap] = a[k];
  40.                         k -= gap;
  41.                     }
  42.                     a[k + gap] = tmp;
  43.                 }
  44.             }
  45.         }
  46.  
  47.     }
  48. }
  49.  
  50. /*
  51.  * 对希尔排序中的单个组进行排序
  52.  *
  53.  * 参数说明：
  54.  *     a -- 待排序的数组
  55.  *     n -- 数组总的长度
  56.  *     i -- 组的起始位置
  57.  *     gap -- 组的步长
  58.  *
  59.  *  组是"从i开始，将相隔gap长度的数都取出"所组成的！
  60.  */
  61. void group_sort(int a[], int n, int i,int gap)
  62. {
  63.     int j;
  64.  
  65.     for (j = i + gap; j < n; j += gap)
  66.     {
  67.         // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
  68.         if (a[j] < a[j - gap])
  69.         {
  70.             int tmp = a[j];
  71.             int k = j - gap;
  72.             while (k >= 0 && a[k] > tmp)
  73.             {
  74.                 a[k + gap] = a[k];
  75.                 k -= gap;
  76.             }
  77.             a[k + gap] = tmp;
  78.         }
  79.     }
  80. }
  81.  
  82. /*
  83.  * 希尔排序
  84.  *
  85.  * 参数说明：
  86.  *     a -- 待排序的数组
  87.  *     n -- 数组的长度
  88.  */
  89. void shell_sort2(int a[], int n)
  90. {
  91.     int i,gap;
  92.  
  93.     // gap为步长，每次减为原来的一半。
  94.     for (gap = n / 2; gap > 0; gap /= 2)
  95.     {
  96.         // 共gap个组，对每一组都执行直接插入排序
  97.         for (i = 0 ;i < gap; i++)
  98.             group_sort(a, n, i, gap);
  99.     }
  100. }
  101.  
  102. void main()
  103. {
  104.     int i;
  105.     int a[] = {80,30,60,40,20,10,50,70};
  106.     int ilen = LENGTH(a);
  107.  
  108.     printf("before sort:");
  109.     for (i=0; i<ilen; i++)
  110.         printf("%d ", a[i]);
  111.     printf("\n");
  112.  
  113.     shell_sort1(a, ilen);
  114.     //shell_sort2(a, ilen);
  115.  
  116.     printf("after  sort:");
  117.     for (i=0; i<ilen; i++)
  118.         printf("%d ", a[i]);
  119.     printf("\n");
  120. }

希尔排序C++实现
实现代码(ShellSort.cpp)

  1. /**
  2.  * 希尔排序：C++
  3.  *
  4.  * @author skywang
  5.  * @date 2014/03/11
  6.  */
  8. #include <iostream>
  9. using namespace std;
  10.  
  11. /*
  12.  * 希尔排序
  13.  *
  14.  * 参数说明：
  15.  *     a -- 待排序的数组
  16.  *     n -- 数组的长度
  17.  */
  18. void shellSort1(int* a, int n)
  19. {
  20.     int i,j,gap;
  21.  
  22.     // gap为步长，每次减为原来的一半。
  23.     for (gap = n / 2; gap > 0; gap /= 2)
  24.     {
  25.         // 共gap个组，对每一组都执行直接插入排序
  26.         for (i = 0 ;i < gap; i++)
  27.         {
  28.             for (j = i + gap; j < n; j += gap)
  29.             {
  30.                 // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
  31.                 if (a[j] < a[j - gap])
  32.                 {
  33.                     int tmp = a[j];
  34.                     int k = j - gap;
  35.                     while (k >= 0 && a[k] > tmp)
  36.                     {
  37.                         a[k + gap] = a[k];
  38.                         k -= gap;
  39.                     }
  40.                     a[k + gap] = tmp;
  41.                 }
  42.             }
  43.         }
  44.  
  45.     }
  46. }
  47.  
  48. /*
  49.  * 对希尔排序中的单个组进行排序
  50.  *
  51.  * 参数说明：
  52.  *     a -- 待排序的数组
  53.  *     n -- 数组总的长度
  54.  *     i -- 组的起始位置
  55.  *     gap -- 组的步长
  56.  *
  57.  *  组是"从i开始，将相隔gap长度的数都取出"所组成的！
  58.  */
  59. void groupSort(int* a, int n, int i,int gap)
  60. {
  61.     int j;
  62.  
  63.     for (j = i + gap; j < n; j += gap)
  64.     {
  65.         // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
  66.         if (a[j] < a[j - gap])
  67.         {
  68.             int tmp = a[j];
  69.             int k = j - gap;
  70.             while (k >= 0 && a[k] > tmp)
  71.             {
  72.                 a[k + gap] = a[k];
  73.                 k -= gap;
  74.             }
  75.             a[k + gap] = tmp;
  76.         }
  77.     }
  78. }
  79.  
  80. /*
  81.  * 希尔排序
  82.  *
  83.  * 参数说明：
  84.  *     a -- 待排序的数组
  85.  *     n -- 数组的长度
  86.  */
  87. void shellSort2(int* a, int n)
  88. {
  89.     int i,gap;
  90.  
  91.     // gap为步长，每次减为原来的一半。
  92.     for (gap = n / 2; gap > 0; gap /= 2)
  93.     {
  94.         // 共gap个组，对每一组都执行直接插入排序
  95.         for (i = 0 ;i < gap; i++)
  96.             groupSort(a, n, i, gap);
  97.     }
  98. }
  99.  
  100. int main()
  101. {
  102.     int i;
  103.     int a[] = {80,30,60,40,20,10,50,70};
  104.     int ilen = (sizeof(a)) / (sizeof(a[0]));
  105.  
  106.     cout << "before sort:";
  107.     for (i=0; i<ilen; i++)
  108.         cout << a[i] << " ";
  109.     cout << endl;
  110.  
  111.     shellSort1(a, ilen);
  112.     //shellSort2(a, ilen);
  113.  
  114.     cout << "after  sort:";
  115.     for (i=0; i<ilen; i++)
  116.         cout << a[i] << " ";
  117.     cout << endl;
  118.  
  119.     return 0;
  120. }

希尔排序Java实现
实现代码(ShellSort.java)

  1. /**
  2.  * 希尔排序：Java
  3.  *
  4.  * @author skywang
  5.  * @date 2014/03/11
  6.  */
  8. public class ShellSort {
  9.  
  10.     /**
  11.      * 希尔排序
  12.      *
  13.      * 参数说明：
  14.      *     a -- 待排序的数组
  15.      *     n -- 数组的长度
  16.      */
  17.     public static void shellSort1(int[] a, int n) {
  18.  
  19.         // gap为步长，每次减为原来的一半。
  20.         for (int gap = n / 2; gap > 0; gap /= 2) {
  21.  
  22.             // 共gap个组，对每一组都执行直接插入排序
  23.             for (int i = 0 ;i < gap; i++) {
  24.  
  25.                 for (int j = i + gap; j < n; j += gap) {
  26.  
  27.                     // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
  28.                     if (a[j] < a[j - gap]) {
  29.  
  30.                         int tmp = a[j];
  31.                         int k = j - gap;
  32.                         while (k >= 0 && a[k] > tmp) {
  33.                             a[k + gap] = a[k];
  34.                             k -= gap;
  35.                         }
  36.                         a[k + gap] = tmp;
  37.                     }
  38.                 }
  39.             }
  40.         }
  41.     }
  42.  
  43.     /**
  44.      * 对希尔排序中的单个组进行排序
  45.      *
  46.      * 参数说明：
  47.      *     a -- 待排序的数组
  48.      *     n -- 数组总的长度
  49.      *     i -- 组的起始位置
  50.      *     gap -- 组的步长
  51.      *
  52.      *  组是"从i开始，将相隔gap长度的数都取出"所组成的！
  53.      */
  54.     public static void groupSort(int[] a, int n, int i,int gap) {
  55.  
  56.         for (int j = i + gap; j < n; j += gap) {
  57.  
  58.             // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
  59.             if (a[j] < a[j - gap]) {
  60.  
  61.                 int tmp = a[j];
  62.                 int k = j - gap;
  63.                 while (k >= 0 && a[k] > tmp) {
  64.                     a[k + gap] = a[k];
  65.                     k -= gap;
  66.                 }
  67.                 a[k + gap] = tmp;
  68.             }
  69.         }
  70.     }
  71.  
  72.     /**
  73.      * 希尔排序
  74.      *
  75.      * 参数说明：
  76.      *     a -- 待排序的数组
  77.      *     n -- 数组的长度
  78.      */
  79.     public static void shellSort2(int[] a, int n) {
  80.         // gap为步长，每次减为原来的一半。
  81.         for (int gap = n / 2; gap > 0; gap /= 2) {
  82.             // 共gap个组，对每一组都执行直接插入排序
  83.             for (int i = 0 ;i < gap; i++)
  84.                 groupSort(a, n, i, gap);
  85.         }
  86.     }
  87.  
  88.     public static void main(String[] args) {
  89.         int i;
  90.         int a[] = {80,30,60,40,20,10,50,70};
  91.  
  92.         System.out.printf("before sort:");
  93.         for (i=0; i<a.length; i++)
  94.             System.out.printf("%d ", a[i]);
  95.         System.out.printf("\n");
  96.  
  97.         shellSort1(a, a.length);
  98.         //shellSort2(a, a.length);
  99.  
  100.         System.out.printf("after  sort:");
  101.         for (i=0; i<a.length; i++)
  102.             System.out.printf("%d ", a[i]);
  103.         System.out.printf("\n");
  104.     }
  105. }

上面3种实现的原理和输出结果都是一样的。下面是它们的输出结果：

before sort:80 30 60 40 20 10 50 70 
after  sort:10 20 30 40 50 60 70 80
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/886006
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号