C++ 算法之希尔排序详解及实例

C++ 算法之希尔排序算法详解及实例

希尔排序算法

定义：

希尔排序是插入排序的一种，也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。

算法思想：

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰好被分为一组，算法终止。

时间复杂度：

O(N)

空间复杂度：

O(1)

性能：

希尔排序为不稳定算法（一次插入排序是稳定的，不会改变相同元素的相对顺序，但是在不同的插入排序中，相同的元素可能在各自的插入排序中移动，会打乱其稳定性）

优势：

希尔排序不需要大量的辅助空间，比直接插入排序时间要快，并且代码很好实现。

缺点：

虽然希尔排序相对于直接插入排序要优化很多，但是O（N）的算法依旧效率不是很高，并且希尔排序不稳定。

代码实现：

#include <iostream>
#include <Windows.h>
#include <assert.h> 

using namespace std; 

//希尔排序,从小到大排
void ShellSort(int* arr, int len)
{
  assert(arr);
  int gap = 3;   //先给一个初始组间距，gap为1时即为直接插入排序
  for (gap = 3; gap > 0; --gap)  //不断缩小组间距，直到gap=1
  {
    for (int i = 0; i < len; ++i)
    {
      for (int j = i + gap; j < len; j = j + gap)
      {
        if (arr[j-gap] > arr[j])
        {
          int temp = arr[j];  //将arr[j]处的值先保存起来
          arr[j] = arr[j-gap];
          arr[j-gap] = temp;
        }
      }
    }
  }
}

#include "ShellSort.h" 

void TestShellSort()
{
  int arr[] = { 100, 2,888, 6, 10, 5, 3, 666, 78, 9, 10000, 45, 67, 33 };
  int len = sizeof(arr) / sizeof(arr[0]);
  cout << "未排序序列：" << "";
  for (int i = 0; i < len; ++i)
  {
    cout << arr[i] << "->";
  }
  cout << endl;
  ShellSort(arr, len);
  cout << "已排序序列：" << "";
  for (int j = 0; j < len; ++j)
  {
    cout << arr[j] << "->";
  }
  cout << endl;
} 

int main()
{
  TestShellSort();
  system("pause");
  return 0;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • C++实现简单的希尔排序Shell Sort实例

    本文以实例形式讲述了基于C++实现简单的希尔排序Shell Sort的方法,是一个很经典的算法,具体实现代码如下: #include <iostream> using namespace std; void ShellSort(int* iArray,int length) { //初始化jump等于length int jump = length; //标记本趟检测是否进行了交换, // 若进行了 则还有下次从头开始的检测, // 否则停止,继续改变jump的值 做另一趟排序 bool is

  • C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是算法实现文件Sort.h,代码如下: /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ #include <iostream> template<class T> void swap_value(T &a, T &b) { T t

  • C++ 算法之希尔排序详解及实例

    C++ 算法之希尔排序详解及实例

    C++ 算法之希尔排序算法详解及实例 希尔排序算法 定义: 希尔排序是插入排序的一种,也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本. 算法思想: 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰好被分为一组,算法终止. 时间复杂度: O(N) 空间复杂度: O(1) 性能: 希尔排序为不稳定算法(一次插入排序是稳定的,不会改变相同元素的相对顺序,但是在不同的插入排序中,相同的元素可能在各自的

  • java数据结构与算法之希尔排序详解

    本文实例讲述了java数据结构与算法之希尔排序.分享给大家供大家参考,具体如下: 这里要介绍的是希尔排序(缩小增量排序法). 希尔排序:通过比较相距一定间隔的元素来工作:各趟比较所用的距离(增量)随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止.是插入排序的一种,是针对直接插入排序算法的改进. 算法思想:先将要排序的序列按某个增量d分成若干个子序列,对每个子序列中全部元素分别进行直接插入排序,然后再用一个较小的增量对它进行分组,在每组中再进行排序.当增量减到1时,整个要排序的数被分成一

  • java 算法之希尔排序详解及实现代码

    java 算法之希尔排序 一.思想 希尔排序:使数组中任意间隔为h的元素都是有序的.在进行排序的时候,如果h很大,我们就能将元素移动到很远的地方,为实现更小的h有序创造方便.用这种方式,对任意以1结尾的h序列,我们都能够将数据排序: 二.概念 h有序数组:任意间隔为h的元素都是有序的数组: 三.高效原因 对于大规模乱序数组插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一段:   希尔排序更高效的原因:它权衡了子数组的规模和有序性,在排序之初,各个子数组都很短:

  • Java经典排序算法之希尔排序详解

    Java经典排序算法之希尔排序详解

    一.希尔排序(Shell Sort) 希尔排序(Shell Sort)是一种插入排序算法,因D.L.Shell于1959年提出而得名. Shell排序又称作缩小增量排序. 二.希尔排序的基本思想 希尔排序的中心思想就是:将数据进行分组,然后对每一组数据进行排序,在每一组数据都有序之后,就可以对所有的分组利用插入排序进行最后一次排序.这样可以显著减少交换的次数,以达到加快排序速度的目的. 希尔排序的中心思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数

  • JAVA十大排序算法之希尔排序详解

    JAVA十大排序算法之希尔排序详解

    目录 希尔排序 代码实现 时间复杂度 算法稳定性 总结 希尔排序 一种基于插入排序的快速的排序算法.简单插入排序对于大规模乱序数组很慢,因为元素只能一点一点地从数组的一端移动到另一端.例如,如果主键最小的元素正好在数组的尽头,要将它挪到正确的位置就需要n-1次移动. 希尔排序为了加快速度简单地改进了插入排序,也称为缩小增量排序. 希尔排序是把待排序数组按一定的数量分组,对每组使用直接插入排序算法排序:然后缩小数量继续分组排序,随着数量逐渐减少,每组包含的元素越来越多,当数量减至 1 时,整个数组

  • JavaScript排序算法之希尔排序的2个实例

    JavaScript排序算法之希尔排序的2个实例

    插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率.但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位.希尔排序按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布.一些老版本教科书和参考手册把该算法命名为Shell-Metzner,即包含Marlene Metzner Norton的名字,但是根据Metzner本人的说法,"我没有为这种算法做任何事,我的名字不应该出现在算法的名字中." 希尔排序基本思想:先取一个小于n的

  • MySQL对中文进行排序详解及实例

    MySQL对中文进行排序详解 MySQL默认只支持对日期.时间和英文字符串进行排序,如果对中文进行order by很可能得不到想要的结果,如下面的查询并不会按我们所想的根据汉字的拼音进行排序: SELECT * from user order by user_name; 如果相对中文进行排序的话,可以使用CONVERT(coloum_name USING GBK)将中文转为GBK编码形式,然后再排序,就可以实现根据汉子的拼音进行排序: SELECT * from user order by CO

  • java排序算法之选择排序详解

    java排序算法之选择排序详解

    本文实例为大家分享了java排序算法之选择排序的具体代码,供大家参考,具体内容如下 选择排序 选择排序的思路是这样的:首先,找到数组中最小的元素,拎出来,将它和数组的第一个元素交换位置,第二步,在剩下的元素中继续寻找最小的元素,拎出来,和数组的第二个元素交换位置,如此循环,直到整个数组排序完成. 至于选大还是选小,这个都无所谓,你也可以每次选择最大的拎出来排,也可以每次选择最小的拎出来的排,只要你的排序的手段是这种方式,都叫选择排序. (有序区,无序区).在无序区里找一个最小的元素跟在有序区的后

  • JAVA十大排序算法之桶排序详解

    JAVA十大排序算法之桶排序详解

    目录 桶排序 代码实现 时间复杂度 算法稳定性 总结 桶排序 桶排序是计数排序的升级,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过函数的某种映射关系,将待排序数组中的元素映射到各个对应的桶中,对每个桶中的元素进行排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序),最后将非空桶中的元素逐个放入原序列中. 桶排序需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效. 代码实现 1.找出数组中的最大值max和最小值min,可以确定出数组所在范

  • JAVA十大排序算法之选择排序详解

    JAVA十大排序算法之选择排序详解

    目录 选择排序 代码实现 动图演示 代码实现 时间复杂度 算法稳定性 总结 选择排序 1.找到数组中最大(或最小)的元素 2.将它和数组的第一个元素交换位置(如果第一个元素就是最大(小)元素那么它就和自己交换) 3.在剩下的元素中找到最大(小)的元素,将它与数组的第二个元素交换位置.如此往复,直到将整个数组排序. 代码实现 对下面数组实现排序:{87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9} 动图演示 代码实现 public class Selecti

随机推荐