当前位置: 首页 > article >正文

算法之插入排序及希尔排序(C语言版)

我们来实现上述排序

一.插入排序.

当插入第i(i>=1)个元素时,前面的array[0],array[1],.,array[i-1]已经排好序,此时用array[i的排序码与array[i-1]array[i-2].的排序码顺序进行比较,找到插入位置即将arrayU插入,原来位置上的元素顺序后移.

CSDN这个链接有我之前写的直接插入排序

今天我们来实现广义上的插入排序:

我直接写出来,会在里面写注释

void Insertsort(int* arr, int n)//arr数组,n元素个数
{
	//我们用升序排列
	for (int i = 0; i < n-1; i++)//循环n次
	{
		int end = i;//将i的值赋给end,方便将其数值改变而不影响循环
		int tmp = arr[end + 1];//由于升序,我们要提前保存要排序的数
		//这里默认前i个数是已排好的,即end
		while (end >= 0)
		{
			if (arr[end] > tmp)//arr[end]与arr[end+1]比较
			{
				arr[end + 1] = arr[end];//满足条件赋值
				end--;//继续向前排列
			}
			else
			{
				break;//不满足条件退出循环
			}
		}
		arr[end + 1] = tmp;//将保存的数值赋给留出的位置
	}
}

我们排一个数组试试:
 

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Insertsort(int* arr, int n)//arr数组,n元素个数
{
	//我们用升序排列
	for (int i = 0; i < n-1; i++)//循环n次
	{
		int end = i;//将i的值赋给end,方便将其数值改变而不影响循环
		int tmp = arr[end + 1];//由于升序,我们要提前保存要排序的数
		//这里默认前i个数是已排好的,即end
		while (end >= 0)
		{
			if (arr[end] > tmp)//arr[end]与arr[end+1]比较
			{
				arr[end + 1] = arr[end];//满足条件赋值
				end--;//继续向前排列
			}
			else
			{
				break;//不满足条件退出循环
			}
		}
		arr[end + 1] = tmp;//将保存的数值赋给留出的位置
	}
}
void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[] = { 2,4,6,8,0,1,3,5,7,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Insertsort(arr, sz);
	Print(arr, sz);

}

结果:

当然我们也可以用降序来排:

void Insertsort(int* arr, int n)//arr数组,n元素个数
{
	//我们用升序排列
	for (int i = 0; i < n-1; i++)//循环n次
	{
		int end = i;//将i的值赋给end,方便将其数值改变而不影响循环
		int tmp = arr[end + 1];//由于升序,我们要提前保存要排序的数
		//这里默认前i个数是已排好的,即end
		while (end >= 0)
		{
			if (arr[end] < tmp)//arr[end]与arr[end+1]比较,改变<,>符号即可
			{
				arr[end + 1] = arr[end];//满足条件赋值
				end--;//继续向前排列
			}
			else
			{
				break;//不满足条件退出循环
			}
		}
		arr[end + 1] = tmp;//将保存的数值赋给留出的位置
	}
}

上题数组的结果(用降序排列):

我们接下来看看其时间复杂度:

我们只考虑最坏的情况:

假设 n=1:外层1次,内层1次

        n=2:外层2次,内层最坏2次

        n=3:外层3次,内层最坏3次

        n=n:外层n次,内层最坏n次

因此时间复杂度为:O(N*N)=O(N^2);

二.插入排序进阶----希尔排序.

又叫递减增量排序算法。

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

希尔排序主要分两步:1.预排序  2.插入排序

预排序:分组排间隔为gap是一组。

假设gap == 5

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

我们直接实现,在插入排序上改:

void Shellsort(int* arr, int n)
{
	int gap = n;//将n的值赋值一份给gap,便于后续对gap给值划分
	while (gap > 1)
	{
		//法一:gap/2为单位
		gap = gap / 2;//gap的值以二分之一不断划分,最后得到gap=1进行插入排序
		//gap/3为单位
		//gap = gap / 3 + 1;//gap的值以三分之一不断划分,最后加+1得到gap=1进行插入排序
		//gap>1时进行预排序
		//gap=1时进行插入排序
		for (int i = 0; i < n - gap; i++)//i<n-gap:把间隔为gap的多组数据同时排
		{
			//下面操作和插入排序大体相同,但注意不再时加减1;而是以gap为单位!!!
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

继续实现上面那个数组的排序:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Shellsort(int* arr, int n)
{
	int gap = n;//将n的值赋值一份给gap,便于后续对gap给值划分
	while (gap > 1)
	{
		//法一:gap/2为单位
		gap = gap / 2;//gap的值以二分之一不断划分,最后得到gap=1进行插入排序
		//gap/3为单位
		//gap = gap / 3 + 1;//gap的值以三分之一不断划分,最后加+1得到gap=1进行插入排序
		//gap>1时进行预排序
		//gap=1时进行插入排序
		for (int i = 0; i < n - gap; i++)//i<n-gap:把间隔为gap的多组数据同时排
		{
			//下面操作和插入排序大体相同,但注意不再时加减1;而是以gap为单位!!!
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}
void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[] = { 2,4,6,8,0,1,3,5,7,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Shellsort(arr, sz);
	Print(arr, sz);

}

结果:

上面这是升序的,相信降序的大家都会了。没错,和插入排序改变之处相同。

接下来我们讨论其时间复杂度:

gap = gap / 2;// logN
//gap = gap / 3 + 1;// 1og3N 以3为底数的对数
for (int i = 0; i < n - gap; i++)
{
	// gap > 1时都是预排序 接近有序
	// gap == 1时就是直接插入排序 有序
	// gap很大时,下面预排序时间复杂度0(N)
	// // gap很小时,数组已经很接近有序了,这时差不多也是(N)
	int end = i;
	int tmp = arr[end + gap];
	while (end >= 0)
	{
		if (arr[end] > tmp)
		{
			arr[end + gap] = arr[end];
			end -= gap;
		}
		else
		{
			break;
		}
	}
	arr[end + gap] = tmp;
}

因此,其时间复杂度为:O(N*logN),平均的时间复杂度是0(N*1.3)

读者可能会想这个希尔排序是三层循环,而插入排序才两层循环,不可能出现其算法更优越啊!

但实际上,确实是希尔排序快,而且快了不止一点。

假设用10万个数据,我们对比发现希尔排序要少排非常多次。

InsertSort:1616ms
ShellSort:12ms

这是一个相同数据检测出来两者的时间差距,可见两者的差距有多大,希尔牛逼!

希尔排序缺点:

希尔排序并不只是相邻元素的比较,有许多跳跃式的比较,难免会出现相同元素之间的相对位置发生变化,所以希尔排序是不稳定的算法。

最后,我会不间断的更新其他排序,希望大家多多支持!


http://www.kler.cn/a/149407.html

相关文章:

  • 提取神经网络数学表达式
  • 【121. 买卖股票的最佳时机】——贪心算法/动态规划
  • 【vue2.0入门】vue基本语法
  • [前端]NodeJS常见面试题目
  • MacOS 本地生成SSH key并关联Github
  • [代码随想录Day10打卡] 理论基础 232.用栈实现队列 225. 用队列实现栈 20. 有效的括号 1047. 删除字符串中的所有相邻重复项
  • C++ day42背包理论基础01 + 滚动数组
  • source: command not found错误的解决方法
  • 学习知识随笔(Django)
  • 机器学习笔记 - 基于百度飞桨PaddleSeg的人体分割
  • Douuble 4 VR智能互动系统为酒店管理专业提供虚拟场景实训
  • 代洋集团,引领绿色能源新潮流
  • Python搭建运筹模型的代码框架
  • Android 13.0 系统settings系统属性控制一级菜单显示隐藏
  • layui下拉框jQuery动态修改选中并展示
  • Vue实现可拖拽边界布局
  • UE5、CesiumForUnreal实现加载GeoJson绘制多面(MultiPolygon)功能(支持点选高亮)
  • python循环调用http示例(一定时间duration内,每隔时间interval去调用一次)call_http()
  • osgFX扩展库-异性光照、贴图、卡通特效(1)
  • Docker+Anaconda+CUDA+cuDNN
  • C++ 17实现无锁队列
  • Servlet-Vue-JSON交互
  • JSP迭代标签之 forEach循环标签 基本使用讲解
  • 使用Wireshark提取流量中图片方法
  • JSP forEach 标签遍历map集合
  • 【nlp】4.5 迁移学习实践项目(相关概念、中文分类、填空、句子关系、模型微调)