【数据结构—数据—插入排序】

这篇具有很好参考价值的文章主要介绍了【数据结构—数据—插入排序】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

前言

一、插入排序

1.1基本思想:

1.2直接插入排序:

1.3直接插入排序的代码实现

二、希尔排序( 缩小增量排序 )

2.1算法讲解

2.2希尔排序的代码实现

总结


前言

世上有两种耀眼的光芒,一种是正在升起的太阳,一种是正在努力学习编程的你!一个爱学编程的人。各位看官,我衷心的希望这篇博客能对你们有所帮助,同时也希望各位看官能对我的文章给与点评,希望我们能够携手共同促进进步,在编程的道路上越走越远!


提示:以下是本篇文章正文内容,下面案例可供参考

一、插入排序

1.1基本思想:

直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。

实际中我们玩扑克牌时,就用了插入排序的思想

【数据结构—数据—插入排序】,数据结构,c语言,排序算法,算法

1.2直接插入排序:

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

【数据结构—数据—插入排序】,数据结构,c语言,排序算法,算法

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

1.3直接插入排序的代码实现

Sort.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>

//打印数组
void PrintArray(int* a, int n);

//插入排序(最坏的情况下:逆序,才是等差数列)
void InsertSort(int* a, int n);
Sort.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
#include"Stack.h"

//打印数组
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

//插入排序
//时间复杂度:O(N^2)
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		//[0,end],我们把end+1为下标的元素插入前面的有序的区间,后保持有序
		int end = i;
		int tmp = a[end + 1];
		//一趟插入排序
		while (end >= 0)
		{
			if (tmp > a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"

void TestInsertSort()
{
	int a[] = { 3,2,6,8,4,6,0,9,5,1,7 };
	InsertSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}


int main()
{
	TestInsertSort();
	return 0;
}

【数据结构—数据—插入排序】,数据结构,c语言,排序算法,算法

二、希尔排序( 缩小增量排序 )

2.1算法讲解

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

【数据结构—数据—插入排序】,数据结构,c语言,排序算法,算法

希尔排序的特性总结:
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的希尔排序的时间复杂度都不固定:

《数据结构(C语言版)》--- 严蔚敏

【数据结构—数据—插入排序】,数据结构,c语言,排序算法,算法

《数据结构-用面相对象方法与C++描述》--- 殷人昆

【数据结构—数据—插入排序】,数据结构,c语言,排序算法,算法

【数据结构—数据—插入排序】,数据结构,c语言,排序算法,算法

4. 稳定性:不稳定

2.2希尔排序的代码实现

Sort.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>

//打印数组
void PrintArray(int* a, int n);


//希尔排序
void ShellSort(int* a, int n);
Sort.c

一组一组的预排序

//希尔排序
//步骤:1、预排序(接近有序);2、直接插入排序
//预排序:分别对每个分组进行插入排序
void ShellSort(int* a, int n)
{
	//把间隔为gap的值看作一组
	int gap = 3;
	//gap组预排序
	for (int j = 0; j < gap; j++)
	{
		//一组预排序
		for (int i = 0; i < n - gap; i += gap)
		{
			//[0,end],我们把end+gap为下标的元素插入前面的有序的区间,后保持有序
			int end = i;
			int tmp = a[end + gap];
			//一趟插入排序
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}

	}
}

多组一块预排序

//希尔排序(时间复杂度:平均是O(N^1.3))
//步骤:1、预排序(接近有序);2、直接插入排序
//预排序:分别对每个分组进行插入排序(gap越大,大的值更快调到后面,小的值更快调到前面,但是越不接近有序)
//(gap越小,跳的越慢,但是越接近有序。如果gap == 1就是直接插入排序),所以gap不能是固定值。
void ShellSort(int* a, int n)
{
	//把间隔为gap的值看作一组
	int gap = n;
	//gap > 1时是预排序,目的是让他接近有序
	//gap == 1是直接插入排序,目的是让它有序
	while (gap > 1)
	{
		//gap = gap / 2;//上下两个都行
		gap = gap / 3 + 1;//一定要保证gap最后一次是1
		//多组一块预排序
		for (int i = 0; i < n - gap; i++)
		{
			//[0,end],我们把end+gap为下标的元素插入前面的有序的区间,后保持有序
			int end = i;
			int tmp = a[end + gap];
			//一趟插入排序
			while (end >= 0) 
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"


void TestShellSort()
{
	int a[] = { 3,2,6,8,4,6,0,9,5,1,7 };
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
	TestSelectSort();
	return 0;
}

【数据结构—数据—插入排序】,数据结构,c语言,排序算法,算法


总结

好了,本篇博客到这里就结束了,如果有更好的观点,请及时留言,我会认真观看并学习。
不积硅步,无以至千里;不积小流,无以成江海。文章来源地址https://www.toymoban.com/news/detail-786535.html

到了这里,关于【数据结构—数据—插入排序】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法:插入排序&希尔排序

    假设现在你有一个有序的数组,你要把一个数据插入到数组中,保证插入后依然有序,要怎么做? 对于人来说,这个问题就像是在整理扑克牌,瞄一眼就知道应该插入什么位置。但是对于程序来说,就需要一一对比,直到找到一个位置 左边比它大,右边比它小 ,就算找到了

    2024年01月17日
    浏览(55)
  • 【数据结构】常见排序算法——常见排序介绍、插入排序、直接插入排序、希尔排序

      在计算机科学中,排序是将一组数据按照指定的顺序排列的过程。排序算法由于执行效率的不同可以分为多种不同的算法。   通常情况下,排序算法可以分为两类,即 内部排序和外部排序 。内部排序是指数据全部加载到内存中进行排序,适用于数据量较小的情况,而

    2024年02月08日
    浏览(60)
  • 数据结构算法--2 冒泡排序,选择排序,插入排序

    思想就是将相邻元素两两比较,当一个元素大于右侧相邻元素时,交换他们的位置,小于右侧元素时,位置不变,最终序列中的最大元素,像气泡一样,到了最右侧。 这时冒泡排序第一轮结束,数列最右侧元素9的位置可认为是一个有序区,有序区目前有一个元素. 第二轮排序

    2024年02月13日
    浏览(62)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(81)
  • 【数据结构与算法】插入排序和希尔排序

      目录 一.插入排序  InsertSort 基本思想 动图演示  特性总结 二.希尔排序  ShellSort 基本思想 图例 特性总结 基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。 当插入第i(i=1)个元素

    2023年04月18日
    浏览(86)
  • 【数据结构与算法】:插入排序与希尔排序

    🔥 个人主页 : Quitecoder 🔥 专栏 : 数据结构与算法 欢迎大家来到初阶数据结构的最后一小节:排序 排序是一种将一组对象按照某种特定顺序重新排列的过程。在计算机科学中,排序是数据处理中非常基本且重要的操作,它可以帮助人们更有效地理解和分析数据。排序的顺序

    2024年03月18日
    浏览(38)
  • 【数据结构与算法】直接插入排序和希尔排序

    进入了初阶数据结构的一个新的主题——排序。所谓排序,就是一串记录, 按照其中的某几个或某些的大小(一定的规则) , 递增或递减排列起来的操作 。 排序的 稳定性 :在一定的规则下,两个值相等的元素,在排序算法处理前后的相对位置是否发生变化,如果相

    2024年04月13日
    浏览(41)
  • 【数据结构】排序算法(一)—>插入排序、希尔排序、选择排序、堆排序

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.直接插入排序 2.希尔排序 3.直接选择排序 4.堆排序 本篇文章博主将介绍排序算法中的插入排序:直接

    2024年02月08日
    浏览(47)
  • 『初阶数据结构 • C语言』⑥ - 插入排序&希尔排序

    学习目标 写在前面 1.插入排序 2.插入排序实战  3.插入排序的实现  4.插入排序的效率 5.平均情况 6.希尔排序 7.希尔排序的实现 8.希尔排序的效率 9.总结   之前我们衡量一个算法的效率时,都是着眼于它在最坏情况下需要多少步。原因很简单,连最坏的情况都做足准备了,其

    2024年02月15日
    浏览(40)
  • 【数据结构与算法篇】手撕排序算法之插入排序与希尔排序

    ​👻内容专栏:《数据结构与算法篇》 🐨本文概括: 讲述排序的概念、直接插入排序、希尔排序、插入排序和希尔排序的区别。 🐼本文作者:花 碟 🐸发布时间:2023.6.13 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的

    2024年02月09日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包