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

插入排序——直接插入排序和希尔排序(C语言实现)

文章目录

  • 前言
  • 直接插入排序
    • 基本思想
    • 特性总结
    • 代码实现
  • 希尔排序
    • 算法思想
    • 特性总结
    • 代码实现

前言

本博客插入排序动图和希尔排序视频参考大佬java技术爱好者,如有侵权,请联系删除。

直接插入排序

基本思想

直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。
实际中我们玩扑克牌时,就用了插入排序的思想:
在这里插入图片描述
当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移。
在这里插入图片描述

特性总结

直接插入排序的特性总结:

  1. 元素集合越接近有序,直接插入排序算法的时间效率越高
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1),它是一种稳定的排序算法
  4. 稳定性:稳定

代码实现

#include<stdio.h>

//直接插入排序
//时间复杂度最好为O(N) -- 顺序有序,最坏为O(N^2) -- 逆序,空间复杂度为O(1)
void insertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int end = i - 1, tmp = a[i];//单趟排序,[0,end]有序,插入tmp
		while (end >= 0)//从后向前比较
		{
			if (a[end] > tmp)a[end + 1] = a[end--];
			else break;
		}
		a[end + 1] = tmp;//两种情况,a[end]<=tmp以及tmp最小
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}

int main()
{
	int arr[] = { 1,2,-9,-6,8,9,4,3,0 };
	insertSort(arr, sizeof(arr) / sizeof(int));
	return 0;
}

希尔排序

算法思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数gap,把待排序文件中所有记录分成个组,所有距离为gap的记录分在同一组内,并对每一组内的记录进行排序。然后,取重复上述分组和排序的工作。当gap==1完成最后的直接插入排序时,所有记录在统一组内排好序。
在这里插入图片描述

希尔排序动图

特性总结

希尔排序的特性总结:

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些书中给出的希尔排序的时间复杂度都不固定:
    《数据结构(C语言版)》— 严蔚敏
    在这里插入图片描述
    《数据结构-用面相对象方法与C++描述》— 殷人昆
    在这里插入图片描述
    因为本人的gap是按照Knuth提出的方式取值的,而且Knuth进行了大量的试验统计,我们暂时就按照:O(N1.25)到O(1.6*N1.25)来算。
  4. 稳定性:不稳定

代码实现

#include<stdio.h>

//void shellSort(int* a, int n)
//{
//	//1.预排序 -- 接近有序
//	int gap = 3;
//	for (int i = 0; i < gap; i++)//优化写法,效率相同
//	{
//		for (int j = i; j < n - gap; j += 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;
//		}
//	}
//}

void printArr(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void shellSort(int* a, int n)//希尔排序
{
	//1.预排序 -- 接近有序
	//2.gap == 1 直接插入排序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//+1可以保证最后一次一定是1
		for (int j = 0; j < n - gap; j++)
		{
			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;
		}
	}
}

int main()
{
	int arr[] = { 7,1,9,8,0,3,2,5,4,6,10,-1 };
	printArr(arr, sizeof(arr) / sizeof(int));
	shellSort(arr, sizeof(arr) / sizeof(int));
	printArr(arr, sizeof(arr) / sizeof(int));
	return 0;
}

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

相关文章:

  • AI写作(四)预训练语言模型:开启 AI 写作新时代(4/10)
  • 本地编译ChatNio的问题解决
  • 即插即用篇 | YOLOv8 引入 代理注意力 AgentAttention
  • 机器学习———特征工程
  • MIT 6.S081 Lab1: Xv6 and Unix utilities翻译
  • SpringBoot整合Freemarker(三)
  • 如何进行更好的面试回复之缓存函数在项目中的性能优化?
  • Advanced Renamer
  • 利用R语言heatmap.2函数进行聚类并画热图
  • Shell脚本如何使用 for 循环、while 循环、break 跳出循环和 continue 结束本次循环
  • Vue学习笔记-Vue3中的计算属性与监视属性
  • 【数据结构】拆分详解 - 二叉树的链式存储结构
  • 消费升级:无人零售的崛起与优势
  • 【MATLAB源码-第97期】基于matlab的能量谷优化算法(EVO)机器人栅格路径规划,输出做短路径图和适应度曲线。
  • git操作:使用vscode集成
  • Spring Cloud Gateway中对admin端点进行认证
  • 自动补全的 select antd react
  • php+mysql期末作业小项目
  • kafka学习笔记--安装部署、简单操作
  • luceda ipkiss教程 43:画渐变圆弧型波导
  • ModuleNotFoundError: No module named ‘dlib‘
  • C_15练习题
  • Qt与Sqlite3
  • 车联网软件定义汽车安全攻击示例
  • 第15章:随堂复习与企业真题(File类与IO流)
  • PaddleClas学习3——使用PPLCNet模型对车辆朝向进行识别(c++)