排序算法之插入排序

要考数据结构了,赶紧来复习一波排序算法

文章目录

  • 一、直接插入排序
  • 二、希尔排序


一、直接插入排序

直接上主题 插排,揪出一个数,插入到原本已经有序的数组里面,如数组有n个数据,从0~n下标依次排列,先从左往右依次排序,每一个待排序它的左边都已经是有序的然后这个数揪出来插入它左边已经有序的数组中,其实它需要先与它左边的相比较,比左边的数小才插入进去,如果这个数都比它左边的数要大了,就不用再插入了就呆在原本位置不变,再往右排,重复这样操作,直到将所有排好序。 其实就像体育课或者军训按高矮次序排列一样。

第一个可以先不动,然后第二个与前面比较如果前面一个比他高。那么第一个就往后面走一位,原先的第二位再与前面比较,但是这会发现他前面已经没人了,都比完了,都没有发现比他矮的,那么他就在第一个位置站着。这会轮到第三个,他发现他比第二个要小,那么原来第二个位置上的人跑到第三个位置上,然后原本第三个位置上的那个人再与第一个比较,发现比第一个高,这会他就站在第一个的后面,他这一轮就结束了,轮到第四个、第五个一直到一列排完。

可以发现每个人排序停止条件是要么比较完了都没有发现比他小的,那么他就是最小的,呆在第一位,要么就是比较时发现有比他矮的,那么他就站在比他矮的那个后面。当然体育课上排列自然不是这样排的,都是看一眼哪些高哪些矮就先站好,然后最后再排,但是其实思想也是插入排序。

在这里插入图片描述

可以发现6个数字但是只比较了五趟,因为第一个就是有序的所有不用比较

好了上代码了

#include<stdio.h>

void Insertsort(int* arr, int sz)
{
	for (int i = 0; i < sz - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		//[0,end]有序,end+1位置的值插入[0,end]让[0,end+1]有序
		while (end >= 0)
		{
			if (arr[end] > tmp)//tmp比他前面的小,那么end就往左边走
			{
				arr[end + 1] = arr[end];
				end--;
			}
            //直到遇见比其小的,tmp就在end后面了
            //这里结束条件有两个
            //第一:它前面的所有都比它大,那么它插在第一个
            //第二:tmp在中间时遇见比其小的,那么就插在比它小的后面,也就是end后面
			else
			{
				break;
			}
		}

		arr[end + 1] = tmp;//在end后一位插入
	}
}

int main()
{
	int a[] = { 9,6,4,7,1,2 };
	int sz = sizeof(a) / sizeof(a[0]);
	Insertsort(a, sz);

	for (int i = 0; i < sz; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

在这里插入图片描述

最好的情况就是原本就有序的,其时间复杂度为O(n),因为要遍历一遍。它的时间复杂度为O(n^2),考虑最坏的那一种情况,逆序,要求我们正序输出,在这里插入图片描述


二、希尔排序

而希尔排序其实思想是基于直接插入排序上升华的,原理和直接插入排序差不多
思想:先将数组进行预排序,让数组接近有序,最后再直接插入排序,
预排序是如何排的?分组排。
分多组,间隔为gap的为一组,假设gap最开始为数组长度 gap = n,因为gap越大,数组中大的值能更快的到后面,小的值能更快的到前面
但是在分组排的过程中gap不会一成不变的,当gap==1 时就是直接插入排序了,因此我们将gap每次除以2或者除以3,但是除3要使其+1,假设gap =n=6,gap = gap/3 =2,2/3!=1,所有要加1保证最后一次一定为一,因为最后进行直接插入排序

gap = 4
在这里插入图片描述
gap = 2
在这里插入图片描述

经过预排,大的数更快的跳到后面,小的数更快的跳到前面

注意gap越大越不接近有序,gap越小越接近有序,gap == 1时就是直接插入排序
上代码

//希尔排序
#include<stdio.h>

void Sheelsort(int* a, int sz)
{
	int gap = sz;
	while (gap > 1)
	{
		gap /= 2;
		//注意越界的情况
		//把间隔为gap的数据排序
		for (int i = 0; i < sz - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];//将后一个数保存到tmp,其实和直接插入排序类似,只不过这里是end+gap,
			//因为要与间隔为gap比较
			//直接插入排序是与它后面一个比较,这里是gap罢了
			
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;//往前跳跃gap,
				}

				else
				{
					break;
				}
			}

			a[end + gap] = tmp;//在end的gap位置放tmp,其实就是将直接插入排序的1换成了gap
		}
	}
}

int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Sheelsort(arr, sz);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

在这里插入图片描述
希尔时间复杂度
在这里插入图片描述
这个循环为lon^n次
这个循环近乎n次
在这里插入图片描述

在这里插入图片描述
所有总的近乎是nlon^n
时间复杂度也就是O(nlog^n),
gap/3时,为nlon3^n

`

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/931.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

iOS中SDK开发 -- cocoapods库创建

在iOS项目中&#xff0c;经常使用cocoadpods来进行依赖管理以及三方库引入等。引入的三方库一般会有几种形式&#xff1a;一、在Pods目录下可以直接看到源代码的开源库&#xff0c;如AFNetworking&#xff0c;Masonry等常见开源库。二、在Pods目录下拉取的项目文件只能看到对应…

讲解Linux中samba理论讲解及Linux共享访问

♥️作者&#xff1a;小刘在C站 ♥️个人主页&#xff1a;小刘主页 ♥️每天分享云计算网络运维课堂笔记&#xff0c;努力不一定有收获&#xff0c;但一定会有收获加油&#xff01;一起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的绽放&#xff0…

监管数据治理治什么?1104、EAST、客户风险系统数据简介

近年来&#xff0c;随着经济社会数字化发展&#xff0c;商业银行逐步向数字化、智能化转型&#xff0c;监管部门对商业银行数据报送质量也越来越重视。自2020年5月9日工行、农行、中行、建行、交行、邮储、中信、光大8家商业银行因监管标准化数据&#xff08;EAST&#xff09;系…

漫画:什么是归并排序算法?

归并排序是建立在归并操作的一种高效的排序方法&#xff0c;该方法采用了分治的思想&#xff0c;比较适用于处理较大规模的数据&#xff0c;但比较耗内存&#xff0c;今天我们聊聊归并排序 一、排序思想 一天&#xff0c;小一尘和慧能坐在石头上&#xff0c;眺望着远方 分而治…

Qt5.12实战之QByteArray与字符指针及字符串转换

示例源码:#include <QCoreApplication> #include <QDebug> #include <QTextStream> static QTextStream cout (stdout,QIODevice::WriteOnly); #include <iostream> #include <QtGlobal> #include <QByteArray>void test() {qDebug() <…

进程调度的基本过程

这里写目录标题什么是进程进程管理结构体或类的主要属性pid内存指针文件描述符表辅助进程调度的属性并发并行并发什么是进程 进程是操作系统对一个正在运行的程序的一种抽象&#xff0c;也就是说&#xff0c;一个运行起来的程序就是一个进程。 进程又是操作系统进行资源分配的…

百度终于要出手了?文心一言

文心一言 百度全新一代知识增强大语言模型&#xff0c;文心大模型家族的新成员&#xff0c;能够与人对话互动&#xff0c;回答问题&#xff0c;协助创作&#xff0c;高效便捷地帮助人们获取信息、知识和灵感。 前几天炒的风风火火的ChatGPT&#xff0c;虽然 ChatGPT 很强大&a…

【Error: ImagePullBackOff】Kubernetes中Nginx服务启动失败排查流程

❌pod节点启动失败&#xff0c;nginx服务无法正常访问&#xff0c;服务状态显示为ImagePullBackOff。 [rootm1 ~]# kubectl get pods NAME READY STATUS RESTARTS AGE nginx-f89759699-cgjgp 0/1 ImagePullBackOff 0 103…

【数据结构与算法】顺序表和链表

[数据结构与算法]顺序表和链表线性表线性表定义&#xff1a;顺序表静态顺序表动态顺序表动态顺序表的接口实现链表链表的概念链表的分类单向链表的接口实现双向链表循环的接口实现顺序表和链表的区别缓存利用率参考存储体系结构以及局部原理性存储体系结构Cache采用的程序访问的…

面试官问 : ArrayList 不是线程安全的,为什么 ?(看完这篇,以后反问面试官)

前言 金三银四 &#xff1f; 也许&#xff0c;但是。 近日&#xff0c;又收到金三银四一线作战小队成员反馈的战况 &#xff1a; 我不管你从哪里看的面经&#xff0c;但是我不允许你看到我这篇文章之后&#xff0c;还不清楚这个面试问题。 本篇内容预告&#xff1a; Array…

【基础算法】单链表的OJ练习(5) # 环形链表 # 环形链表II # 对环形链表II的解法给出证明(面试常问到)

文章目录前言环形链表环形链表 II写在最后前言 本章的OJ练习相对于OJ练习(4)较为简单。不过&#xff0c;本章的OJ最重要的是要我们证明为何可以这么做。这也是面试中常出现的。 对于OJ练习(4)&#xff1a;-> 传送门 <-&#xff0c;分割链表以一种类似于归并的思想解得&a…

ChatGPT-4 终于来了(文末附免费体验地址)

大家好&#xff0c;我是小钱学长。 ChatGPT4.0 重磅来袭&#xff0c;今天一打开plus页面出现的就是这个GPT-4的体验界面&#xff01;现在就带大家一起看看GPT4.0​。 进入之后是这样的 看到最下面有一行话&#xff0c;目前应该是4个小时限制100条消息。 GPT-4有什么优势&…

手把手学会DFS (递归入门)

目录 算法介绍 递归实现指数型枚举 递归实现排列型枚举 递归实现组合型枚举 算法介绍 &#x1f9e9;DFS 即 Depth First Search &#xff0c;中文又叫深度优先搜索&#xff0c;是一种沿着树的深度对其进行遍历&#xff0c;直到尽头之后再进行回溯&#xff0c;再走其他路线的…

springboot复习(黑马)

学习目标基于SpringBoot框架的程序开发步骤熟练使用SpringBoot配置信息修改服务器配置基于SpringBoot的完成SSM整合项目开发一、SpringBoot简介1. 入门案例问题导入SpringMVC的HelloWord程序大家还记得吗&#xff1f;SpringBoot是由Pivotal团队提供的全新框架&#xff0c;其设计…

GPT-4技术报告

摘要 链接&#xff1a;https://cdn.openai.com/papers/gpt-4.pdf 我们汇报了GPT-4的发展&#xff0c;这是一个大规模的多模态模型&#xff0c;可以接受图像和文本输入并产生文本输出。虽然在许多现实场景中&#xff0c;GPT-4的能力不如人类&#xff0c;但它在各种专业和学术基…

数智链接,新一代校园招聘解决方案

疫情3年市场巨变&#xff0c;00后新生代初登上求职舞台&#xff0c;中和作用下&#xff0c;牛客发现新生代求职发生明显变化&#xff0c;企业校招也要随之而变&#xff0c;并率先提出以种草、精准、专业为特点的新一代校园招聘解决方案。01.学生求职变了&#xff01;安全感、非…

奇异值分解(SVD)原理与在降维中的应用

奇异值分解(SVD)原理与在降维中的应用 奇异值分解(Singular Value Decomposition&#xff0c;以下简称SVD)是在机器学习领域广泛应用的算法&#xff0c;它不光可以用于降维算法中的特征分解&#xff0c;还可以用于推荐系统&#xff0c;以及自然语言处理等领域。是很多机器学习算…

GPT-4来袭:开启人工智能新时代

文章目录介绍GPT4 模型演示示例示例 1示例 2示例 3示例 4示例 5最后Reference介绍 2023年3月15日&#xff0c;OpenAI公司正式发布了先进的自然语言处理模型GPT-4&#xff0c;前不久发布的GPT-3.5模型只能理解文字的语言模型&#xff0c;而新发布的GPT4则是多模态模型&#xff…

【java】了解常见集合类

了解常见集合类 一、集合类框架 1、集合类框架结构图 首先我们要对集合类结构有一个大体的认识&#xff0c;所有集合都继承于迭代器&#xff0c;分为单列集合和映射集合&#xff0c;单列集合分为有序可重复和有序不可重复&#xff0c;大概结构如下图所示 2、主要集合类的介…

你真的知道如何系统高效地学习数据结构与算法吗?

文章目录前言&#xff1a;什么是数据结构&#xff1f;什么是算法&#xff1f;学习这个算法需要什么基础&#xff1f;学习的重点在什么地方&#xff1f;一些可以让你事半功倍的学习技巧1.边学边练&#xff0c;适度刷题2.多问、多思考、多互动3.打怪升级学习法4.知识需要沉淀&…