c++实现排序算法之希尔排序方式

目录
  • 排序算法之希尔排序
    • 基本思想
    • 希尔排序算法
    • 复杂度分析
    • 关于希尔排序的问题分析
  • 排序算法之希尔排序及时间复杂度分析
    • 希尔排序
    • 时间复杂度

排序算法之希尔排序

基本思想

将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序的而不是局部有序。

进一步理解：

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

希尔排序算法

#include <iostream>
using namespace std; 
void shellSort(int arr[], int n)
{
    int tmp = 0;
    int step = n / 2;
    while (step)
    {
        for (int i = step; i < n; i++)
        {
            tmp = arr[i];
            int j = i;
            while (j >= step && tmp < arr[j - step])   //采用直接插入排序
            {
                arr[j] = arr[j - step];
                j -= step;
            }
 
            arr[j] = tmp;
        }
 
        step = step / 2;
    }
}
 
int main()
{
    int arr[]{ 3, 14, 25, -22, -3, 87, 126, 34, 64, -70, 15, 17, 78 };
    int n = sizeof(arr) / sizeof(arr[0]);
    shellSort(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
 
    system("pause");
    return 0;
}

复杂度分析

当增量为1（step = 1）时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)；

Hibbard增量的希尔排序的时间复杂度O(n^3/2)；

关于希尔排序的问题分析

排序算法之希尔排序及时间复杂度分析

希尔排序

算法思想：将整个待排序列分割成若干个子序列（由相隔增量个元素组成），分别进行直接插入排序，然后依次缩小增量再进行排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序。

希尔排序的实现应该由三个循环完成

（1）第一次循环，将增量d依次折半，直到增量d=1

（2）第二三层循环，也就是直接插入排序所需要的两次循环。

算法实现：

#include <stdio.h>
#define N 9
int main(void)
{
	int arr[N] = {9,1,5,8,3,7,4,6,2};
	int d = N / 2; //增量先取一半
	int i,j,insertVal;
	//希尔排序三层循环
	while(d>=1) //当增量大于等于1,不断进行插入排序
	{
		//一下两层for循环是直接插入排序代码
		for(i=d; i<N; i++)
		{
			insertVal = arr[i];
			j = i - d;
			while(j>=0 && arr[j]>insertVal)
			{
				arr[j+d] = arr[j];
				j = j - d;
			}
			arr[j+d] = insertVal;
		}
		d = d / 2;
	}
	for(i=0; i<N; i++)
	{
		printf("%d ",arr[i]);
	}
	return 0;
}

由如上代码知，希尔排序的关键并不是随便分组后各自排序，而是将相隔某个增量的记录组成一个子序列，实现跳跃式移动，使得排序的效率高。

时间复杂度

时间复杂度为O(n^1.5)，要好于直接排序的O(n ^ 2)，需要注意的是增量序列的最后一个增量值必须是1.另外由于记录跳跃式的移动，希尔排序并不是一种稳定的排序方法。

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • C++实现希尔排序算法实例

    目录 1.代码模板 2.算法介绍 3.实例 1.代码模板 // 希尔排序(Shell Sort) void ShellSort(SqList *L) { int i, j; int increment = L->length; // 先让增量初始化为序列的长度 do { increment = increment / 3 + 1; // 计算增量的值 for (i = increment + 1; i <= L->length; i ++ ) { if (L->arr[i] <

  • C++深入浅出讲解希尔排序算法的实现

    C++深入浅出讲解希尔排序算法的实现

    目录 希尔排序 1.基本思想 预排序 2.算法实现 3.时间复杂度 插入排序分为两种:直接插入排序&希尔排序 希尔排序 1.基本思想 希尔排序是在直接插入排序基础上的优化,属于非常牛掰的一个排序. 核心思想: 先进行预排序,让数组接近有序: 直接插入排序 预排序 预排序步骤: 分组排,假设gap==3,间隔为gap的为一组,然后分别使用插入排序的思想对这gap组数据进行排序 多组间隔为gap的预排序,gap由大变小,gap越大,大的数可以越快的到后面,小的数可以越快得到前面,gap越大,预排完越

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

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

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

  • c++实现排序算法之希尔排序方式

    c++实现排序算法之希尔排序方式

    目录 排序算法之希尔排序 基本思想 希尔排序算法 复杂度分析 关于希尔排序的问题分析 排序算法之希尔排序及时间复杂度分析 希尔排序 时间复杂度 排序算法之希尔排序 基本思想 将相距某个“增量”的记录组成一个子序列,这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序的而不是局部有序. 进一步理解: 先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直

  • JS排序算法之希尔排序与快速排序实现方法

    本文实例讲述了JS排序算法之希尔排序与快速排序实现方法.分享给大家供大家参考,具体如下: 希尔排序: 定义一个间隔序列,例如是5,3,1.第一次处理,会处理所有间隔为5的,下一次会处理间隔为3的,最后一次处理间隔为1的元素.也就是相邻元素执行标准插入排序. 在开始最后一次处理时,大部分元素都将在正确的位置,算法就不必对很多元素进行交换,这是比插入元素高级的地方. 时间复杂度O(n*logn) function shellSort(){ var N=arr.length; var h=1; whi

  • 图解排序算法之希尔排序Java实现

    图解排序算法之希尔排序Java实现

    一.基本思想 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止. 简单插入排序很循规蹈矩,不管数组分布是怎么样的,依然一步一步的对元素进行比较,移动,插入,比如[5,4,3,2,1,0]这种倒序序列,数组末端的0要回到首位置很是费劲,比较和移动元素均需n-1次.而希尔排序在数组中采用跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分组进行插入排序,随后逐步缩小增量,继续按组

  • 图解Java排序算法之希尔排序

    图解Java排序算法之希尔排序

    目录 基本思想 代码实现 总结 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法.希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一.本文会以图解的方式详细介绍希尔排序的基本思想及其代码实现. 基本思想 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止. 简单插入排序很循规蹈

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

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

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

  • PHP排序算法之希尔排序(Shell Sort)实例分析

    PHP排序算法之希尔排序(Shell Sort)实例分析

    本文实例讲述了PHP排序算法之希尔排序(Shell Sort).分享给大家供大家参考,具体如下: 基本思想: 希尔排序是指记录按下标的一定增量分组,对每一组使用 直接插入排序 ,随着增量逐渐减少,每组包含的关键字越来越多,当增量减少至 1 时,整个序列恰好被分成一组,算法便终止. 操作步骤: 先取一个小于 n(序列记录个数) 的整数 d1 作为第一个增量,把文件的全部记录分组.所有距离为 d1 的倍数的记录放在同一个组中.先在各组内进行 直接插入排序:然后,取第二个增量 d2 < d1 重复上述

  • Java 十大排序算法之希尔排序刨析

    Java 十大排序算法之希尔排序刨析

    目录 希尔排序原理 希尔排序的API设计 希尔排序的代码实现 希尔排序是插入排序的一种,又称"缩小增量排序",是插入排序算法的一种更高效的改进版本. 希尔排序原理 1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组. 2.对分好组的每一组数据完成插入排序. 3.减小增长量,最小减为1,重复第二步操作. 希尔排序的API设计 类名 Shell 构造方法 Shell():创建Shell对象 成员方法 1.public static void sort(Comparable

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

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

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

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

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

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

  • java 排序算法之希尔算法

    java 排序算法之希尔算法

    目录 插入排序存在的问题 简单介绍 基本思想 代码实现 大数据量耗时测试 移动法实现希尔排序 移动法-大数据量耗时测试 算法分析 注:学习本篇的前提是要会插入排序,数据结构与算法--排序算法-插入排序 插入排序存在的问题 简单的插入排序可能存在的问题. 如数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小),过程是: 展示的是要移动 1 这个数,的过程,由于在最后,需要前面的所有数都往后移动一位 {2,3,4,5,6,6} {2,3,4,5,5,6} {2,3,4,4,5,

随机推荐