C++实现希尔排序（ShellSort）

本文实例为大家分享了C++实现希尔排序的具体代码，供大家参考，具体内容如下

一、思路：

希尔排序:又称缩小增量排序，是一种改进的插入排序算法，是不稳定的。

设排序元素序列有n个元素，首先取一个整数gap<n作为间隔，将全部元素分为gap个子序列，所有距离为gap的元素放在同一个子序列中，在每一个子序列中分别施行直接插入排序。然后缩小间隔gap，重复上述的子序列和排序工作。

二、实现程序：

#include <iostream>
using namespace std;

const int maxSize = 20;

// 希尔排序：每次减小1/3，直到d=1;
//   因为前面增量比较大，间隔比较，减少比较的次数，已经将部分排好序，
//   后面虽然d越来越小，但是因为前面已经排好序，所以，后面插入需要比
//   较的次数减少。
template <class T>
void ShellSort(T arr[], const int left, const int right) {
 int i, j, gap, temp; // gap为增量

 gap = right - left + 1; // 增量的初始值
 do{ // 直到增量值为1
  gap = gap / 3 + 1; // 求下一增量值
  for(i = left + gap; i <= right; i++) {
   if(arr[i] < arr[i-gap]) {
    temp = arr[i];
    j = i - gap;
    do {
     arr[j+gap] = arr[j]; // 后移元素
     j = j - gap; // 再比较前一元素
    }while(j >= left && temp < arr[j]);
    arr[j+gap] = temp; // 回填
   }
  } // for
 }while(gap > 1);
} // ShellSort

int main(int argc, const char * argv[]) {
 int i, n, arr[maxSize];

 cout << "请输入要排序的数的个数：";
 cin >> n;
 cout << "请输入要排序的数：";
 for(i = 0; i < n; i++)
  cin >> arr[i];
 cout << "排序前：" << endl;
 for(i = 0; i < n; i++)
  cout << arr[i] << " ";
 cout << endl;
 ShellSort(arr, 0, n-1);
 cout << "排序后：" << endl;
 for(i = 0; i < n; i++)
  cout << arr[i] << " ";
 cout << endl;
 return 0;
}

测试结果：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

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

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

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

  • 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语言常见排序算法之插入排序(直接插入排序,希尔排序)

    目录 前言 一.直接插入排序 1.1 基本思想 1.2 算法思想 1.3 程序实现 1.4 直接插入排序的总结 二.希尔排序 2.1 算法思想 2.2 程序实现 2.3 希尔排序的特征总结 前言 本期为大家带来的是常见排序算法中的插入排序,主要有直接插入排序以及它的升级版——希尔排序,包您一看就会,快来试试吧~ 一.直接插入排序 1.1 基本思想 在生活当中,这种排序方式处处可见: 在玩扑克牌的时候我们就会采用插入排序的思想,当我们拿起第二张牌时,就会下意识的与第一张牌进行比较,如果比第一张牌小

  • C++实现希尔排序（ShellSort）

    本文实例为大家分享了C++实现希尔排序的具体代码,供大家参考,具体内容如下 一.思路: 希尔排序:又称缩小增量排序,是一种改进的插入排序算法,是不稳定的. 设排序元素序列有n个元素,首先取一个整数gap<n作为间隔,将全部元素分为gap个子序列,所有距离为gap的元素放在同一个子序列中,在每一个子序列中分别施行直接插入排序.然后缩小间隔gap,重复上述的子序列和排序工作. 二.实现程序: #include <iostream> using namespace std; const int

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

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

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

  • java 数据结构基本算法希尔排序

    C语言数据结构基本算法希尔排序 前言: 基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序, 然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序.当增量减到1时,进行直接插入排序后,排序完成. 实现代码: public class ShellSort { /** * 原理:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的 * 下标相差d.对每组

  • 用Java实现希尔排序的示例

    一.理论准备 希尔排序(Shell Sort)是插入排序的一种,是针对直接插入排序算法的改进,是将整个无序列分割成若干小的子序列分别进行插入排序,希尔排序并不稳定.该方法又称缩小增量排序,因DL．Shell于1959年提出而得名.基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为d1的倍数的记录放在同一个组中.先在各组内进行直接插入排序:然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<-<d2<

  • java高级排序之希尔排序

    希尔排序对于多达几千个数据项的,中等大小规模的数组排序表现良好,希尔排序不像快速排序和其它时间复杂度为O(n*logn)的排序算法那么快,因此,对非常大的文件排序,它不是最优选择,但是希尔排序比选择排序和插入排序这种时间复杂度为O(n²)的排序要快的多,并且它非常容易实现,代码简短 希尔排序也是插入排序的一种,在插入排序中,如果最小的数在最后面,则复制的次数太多,而希尔解决了这个问题,它也是n-增量排序,它的思想是通过加大插入排序中元素的间隔,并在这些有间隔的元素中进行插入排序,当这些数据项排过

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

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

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是EightAlgorithms.java文件,代码如下: import java.util.Arrays; /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ public class EightAlgorithms { //插入排序:时间复杂度o(n^2) p

  • python实现的希尔排序算法实例

    本文实例讲述了python实现希尔排序算法的方法.分享给大家供大家参考.具体如下: def shellSort(items): inc = len(items) / 2 while inc: for i in xrange(len(items)): j = i temp = items[i] while j >= inc and items[j-inc] > temp: items[j] = items[j - inc] j -= inc items[j] = temp inc = inc/2

  • Swift编程中实现希尔排序算法的代码实例

    Swift编程中实现希尔排序算法的代码实例

    思想 希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL．Shell于1959年提出而得名. 该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个"增量"的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序.因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高. 以n=10的一个数组49, 38, 65,

  • JavaScript希尔排序、快速排序、归并排序算法

    以var a = [4,2,6,3,1,9,5,7,8,0];为例子. 1.希尔排序. 希尔排序是在插入排序上面做的升级.是先跟距离较远的进行比较的一些方法. function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; while(gap>0){ for (var k = 0; k < gap; k++) { var tagArr = []; tagArr.push(arr[k]) for (i

随机推荐