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

目录
  • 希尔排序
    • 1.基本思想
      • 预排序
    • 2.算法实现
    • 3.时间复杂度

插入排序分为两种：直接插入排序&希尔排序

希尔排序

1.基本思想

希尔排序是在直接插入排序基础上的优化，属于非常牛掰的一个排序。

核心思想：

  • 先进行预排序，让数组接近有序；
  • 直接插入排序

预排序

预排序步骤：

分组排，假设gap==3，间隔为gap的为一组，然后分别使用插入排序的思想对这gap组数据进行排序

多组间隔为gap的预排序，gap由大变小，gap越大，大的数可以越快的到后面，小的数可以越快得到前面，gap越大，预排完越不接近有序，gap越小，预排完越接近有序，gap为1时就是直接插入排序

动图演示：

预排序代码：

		for (int i = 0; i < gap; i++)//有gap组需要排
		{
			for (int j = i; j < n - gap; j += gap)//内层循环，先排红，再排绿，最后排蓝
			//注意内层循环的写法
			{
			//跟直接插入排序很像，不同的是需要使用gap
				int end = j;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}

这是最初的写法，其实这个代码是可以优化的：

//预排序优化
		for (int i = 0; i < n - gap; i++)
		//把间隔为gap的多组数据同时排
		//当到n-gap-1的位置就终止了
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}

2.算法实现

//希尔排序
void ShellSort(int* a, int n)
{
	//一开始初始化gap为n
	int gap = n;
	while (gap > 1)//gap大于1都是预排序，gap==1时为直接插入排序
	{
		//为保证gap最终结果为1，可以gap/=2，也可以是gap=gap/3+1;
		gap /= 2;
		//预排序优化
		for (int i = 0; i < n - gap; i++)
		//把间隔为gap的多组数据同时排
		//当到n-gap-1的位置就终止了
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

完整代码：

3.时间复杂度

希尔排序的时间复杂度是：O(N*logN)

到此这篇关于C++深入浅出讲解希尔排序算法的实现的文章就介绍到这了,更多相关C++希尔排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

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

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

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

  • 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++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

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

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

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

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

  • C语言深入浅出讲解直接插入排序算法的实现

    C语言深入浅出讲解直接插入排序算法的实现

    目录 直接插入排序 1.基本思想 2.算法实现 3.时间复杂度 插入排序分为两种:直接插入排序&希尔排序 直接插入排序 1.基本思想 直接插入排序是一种简单的插入排序算法,其基本思想是: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 . 说得通俗一点就是: 假设区间[0, end]有序,将end+1位置的值插入到[0, end]中,保持区间[0, end+1]依旧有序. 生活中我们玩扑克牌时,就用了插入排序的思想. 在这里,

  • Java十大经典排序算法的实现图解

    Java十大经典排序算法的实现图解

    目录 前言 一.排序算法 1.排序算法概述(百度百科) 2.<数据结构与算法>中的排序算法 3.算法分析 二.十大经典排序算法(Java开发版) 1.冒泡排序 2.快速排序 3.基数排序 4.插入排序 5.选择排序 6.希尔排序 7.归并排序 8.计数排序 9.堆排序 10.桶排序 前言 本文章主要是讲解我个人在学习Java开发环境的排序算法时做的一些准备,以及个人的心得体会,汇集成本篇文章,作为自己对排序算法理解的总结与笔记. 内容主要是关于十大经典排序算法的简介.原理.动静态图解和源码实现

  • java几种排序算法的实现及简单分析

    本文实例讲述了java几种排序算法的实现及简单分析.分享给大家供大家参考.具体如下: package test; public class first { /*普通的插入排序*/ public void insertSort(int[] list) { int i, j; list[0] = -999; //相当于设置一个监视哨兵,不用判断是否越界, //但要求数组从第二个数开始即i=1开始存储 for (i = 1; i < list.length; i++) { j = i; while (

  • python常用排序算法的实现代码

    这篇文章主要介绍了python常用排序算法的实现代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 排序是计算机语言需要实现的基本算法之一,有序的数据结构会带来效率上的极大提升. 1.插入排序 插入排序默认当前被插入的序列是有序的,新元素插入到应该插入的位置,使得新序列仍然有序. def insertion_sort(old_list): n=len(old_list) k=0 for i in range(1,n): temp=old_lis

  • php计数排序算法的实现代码(附四个实例代码)

    计数排序只适合使用在键的变化不大于元素总数的情况下.它通常用作另一种排序算法(基数排序)的子程序,这样可以有效地处理更大的键. 总之,计数排序是一种稳定的线性时间排序算法.计数排序使用一个额外的数组C ,其中第i个元素是待排序数组 A中值等于 i的元素的个数.然后根据数组C 来将A中的元素排到正确的位置. 通常计数排序算法的实现步骤思路是: 1.找出待排序的数组中最大和最小的元素: 2.统计数组中每个值为i的元素出现的次数,存入数组C的第i项: 3.对所有的计数累加(从C中的第一个元素开始,每一

  • 详解Python排序算法的实现(冒泡,选择,插入,快速)

    详解Python排序算法的实现(冒泡,选择,插入,快速)

    目录 1. 前言 2. 冒泡排序算法 2.1 摆擂台法 2.2 相邻两个数字相比较 3. 选择排序算法 4. 插入排序 5. 快速排序 6. 总结 1. 前言 所谓排序,就是把一个数据群体按个体数据的特征按从大到小或从小到大的顺序存放. 排序在应用开发中很常见,如对商品按价格.人气.购买数量……显示. 初学编程者,刚开始接触的第一个稍微有点难理解的算法应该是排序算法中的冒泡算法. 我初学时,“脑思维”差点绕在 2 个循环结构的世界里出不来了.当时,老师要求我们死记冒泡的口诀,虽然有点搞笑,但是当

  • C/C++浅析邻接表拓扑排序算法的实现

    C/C++浅析邻接表拓扑排序算法的实现

    目录 前言 一.拓扑排序算法的思路 二.实现步骤 1.求个顶点的入度 2.拓扑排序的实现 三.测试结果 总结 前言 在软件开发.施工过程.教学安排等等的一系列活动中,往往需要一个有向无环图来表示其是否成成功进行下去. 在一个有向图为顶点表示活动的网中,我们称为AOV网(Activity On Vertex Network).设G={V,E}是一个具有n个顶点的有向图,V中的顶点序列v1,v2,…,vn,满足若从顶点vi到vj有一条路径,则在顶点序列中顶点vi必在vj之前.则我们称这样的顶点为一个

  • 7种排序算法的实现示例

    复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <time.h> void BubbleSort1 (int n, int *array) /*little > big*/{ int i, j; for (i=0; i<n-1; i++) {  for (j=n-1; j>i; j--)  {   if (array[j] < array[j-1])   {    int temp

  • python选择排序算法的实现代码

    1.算法:对于一组关键字{K1,K2,-,Kn}, 首先从K1,K2,-,Kn中选择最小值,假如它是 Kz,则将Kz与 K1对换:然后从K2,K3,- ,Kn中选择最小值 Kz,再将Kz与K2对换.如此进行选择和调换n-2趟,第(n-1)趟,从Kn-1.Kn中选择最小值 Kz将Kz与Kn-1对换,最后剩下的就是该序列中的最大值,一个由小到大的有序序列就这样形成. 2.python 选择排序代码: 复制代码 代码如下: def selection_sort(list2):    for i in

随机推荐