黑马程序员技术交流社区

标题: 分享一下希尔排序 [打印本页]
作者: 帅的惊动党中央    时间: 2015-4-22 19:23
标题: 分享一下希尔排序
希尔排序：将无序数组分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行插入排序；然后再选择一个更小的增量，再将数组分割为多个子序列进行排序......最后选择增量为1，即使用直接插入排序，使最终数组成为有序。
  1. /********************************************************
  2. *函数名称：ShellInsert
  3. *参数说明：pDataArray 无序数组；
  4. *          d          增量大小
  5. *                   iDataNum为无序数据个数
  6. *说明：    希尔按增量d的插入排序
  7. *********************************************************/
  8. void ShellInsert(int* pDataArray, int d, int iDataNum)
  9. {
  10.         for (int i = d; i < iDataNum; i += 1)    //从第2个数据开始插入
  11.         {
  12.                 int j = i - d;
  13.                 int temp = pDataArray[i];    //记录要插入的数据
  14.                 while (j >= 0 && pDataArray[j] > temp)    //从后向前，找到比其小的数的位置
  15.                 {
  16.                         pDataArray[j+d] = pDataArray[j];    //向后挪动
  17.                         j -= d;
  18.                 }

  20.                 if (j != i - d)    //存在比其小的数
  21.                         pDataArray[j+d] = temp;
  22.         }
  23. }

  25. /********************************************************
  26. *函数名称：ShellSort
  27. *参数说明：pDataArray 无序数组；
  28. *                   iDataNum为无序数据个数
  29. *说明：    希尔排序
  30. *********************************************************/
  31. void ShellSort(int* pDataArray, int iDataNum)
  32. {
  33.         int d = iDataNum / 2;    //初始增量设为数组长度的一半
  34.         while(d >= 1)
  35.         {
  36.                 ShellInsert(pDataArray, d, iDataNum);
  37.                 d = d / 2;    //每次增量变为上次的二分之一
  38.         }
  39. }
复制代码



作者: lclxjzz    时间: 2015-4-22 20:09
学习了············
作者: JarryHorse    时间: 2015-4-22 20:55
增量设二分之一会不太稳定，我试过呢
作者: 帅的惊动党中央    时间: 2015-4-23 07:56
JarryHorse 发表于 2015-4-22 20:55
增量设二分之一会不太稳定，我试过呢

那设多少比较稳定呢
作者: JarryHorse    时间: 2015-4-23 18:25
帅的惊动党中央 发表于 2015-4-23 07:56
那设多少比较稳定呢

呃···希尔本身就是个不稳定的算法，增量变化越小越稳定，比如···1



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2