前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >排序算法之插入排序(直接插入排序、折半插入排序、希尔排序)

排序算法之插入排序(直接插入排序、折半插入排序、希尔排序)

作者头像
跋扈洋
发布2021-09-03 14:10:51
4720
发布2021-09-03 14:10:51
举报
文章被收录于专栏:物联网知识物联网知识

插入排序

在排序过程中,根据数据元素是否完全在内存中,可以将排序分成两类:

  1. 内部排序:是指在排序期间元素全部存放在内存中的排序。内部排序在执行过程中都要进行两种操作:比较和移动。
  2. 外部排序:是指在排序期间元素无法全部同时存放在内存中,必须在排序的过程中根据要求不断地在内、外存之间移动的排序。外部排序还要关注如何使读/写磁盘次数更少。

插入排序的思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列,直到全部记录插入完成。 插入排序思想可以引申为三种重要的排序算法:直接插入排序、折半插入排序、希尔排序

直接插入排序

理论

直接插入是一个稳定的排序方法,适用于顺序存储和链式存储的线性表。 算法的思想是:依次将每个元素插入到前面已经排序好的子表的相应位置中。

算法实现

代码语言:javascript
复制
void InserSort(ElemType A[], int n)
{
	int i, j;
	for(i=2;i<=n;i++)
		if (A[i] < A[i - 1])
		{
			A[0] = A[i];
			for (j = i - 1; A[0] < A[i]; --j)
				A[j + 1] = A[j];
			A[j + 1] = A[0];
		}
}

折半插入排序

折半插入排序将比较和移动操作分离,即先折半查找出元素的待插入位置,然后统一地移动待插入位置之后的所有元素。

算法实现

代码语言:javascript
复制
void half_Insert(ElemType A[], int n)
{
	int i, j, low, high, mid;
	for (i = 2; i <= n; i++)
	{
		A[0] = A[i];
		low = 1;
		high = i - 1;
		while (low <= high)
		{
			mid = (low + high) / 2;
			if (A[mid] > A[0])
				high = mid - 1;
			else
				low = mid + 1;
		}
		for (j = i - 1; j >= high + 1; --j)
			A[j + 1] = A[j];

		A[high + 1] = A[0];
		
	}
}

希尔排序

概念

希尔排序的基本思想是:先将排序表分割成若干形如L[i,i+d,i+2d…i+kd]的“特殊”子表,即把相隔某个“增量”的记录组车一个子表,对各个子表分别进行直接插入排序,当整个表中的元素已经基本有序时,再对整个表进行一次直接插入排序。 一般情况下,第一个增量一般选用n=总元素数/2;

算法实现

代码语言:javascript
复制
void shell_Sort(ElemType A[],int n)
{
	int i, j, dk;
	for (int dk = n / 2; dk >= 1; dk--)
		for(int i=dk+1;i<=n;i++)
			if (A[i] < A[i - dk])
			{
				A[0] = A[i];
			}
	for (int j = i - dk; j > 0 && A[0] < A[j]; j -= dk)
		A[j + dk] = A[j];
	A[j + dk] = A[0];


}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-08-10,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 物联网知识 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 插入排序
    • 直接插入排序
      • 算法实现
    • 折半插入排序
      • 算法实现
    • 希尔排序
      • 概念
      • 算法实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档