常见排序算法之插入排序类

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

常见排序算法之插入排序类,C/C++,排序算法,算法,数据结构

顾得泉:个人主页

个人专栏:《Linux操作系统》  《C/C++》  《LeedCode刷题》

键盘敲烂,年薪百万!


 插入排序,是一种简单直观的排序算法,工作原理是将一个记录插入到已经排好序的有序表中,从而形成一个新的、记录数增1的有序表。在实现过程中,它使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素和已排序序列中的元素进行比较并找到正确的位置来插入。

       实际在我们平时玩的扑克牌游戏中,就用到了插入排序的思想:

常见排序算法之插入排序类,C/C++,排序算法,算法,数据结构


一、直接插入排序

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

常见排序算法之插入排序类,C/C++,排序算法,算法,数据结构

具体实现代码如下

void InsertSort(int* a, int n)
{
	for (size_t i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
			--end;
		}
		a[end + 1] = tmp;
	}
}

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

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

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

核心代码解析

  1. 外层循环遍历数组中的每个元素,从第二个元素开始(下标为1)。
  2. 内层循环从当前元素的下一个元素开始向前遍历,直到遇到一个比当前元素小的元素或者到达数组的开头。
  3. 在内层循环中,将当前元素与找到的较小元素交换位置。
  4. 当内层循环结束时,将当前元素插入到正确的位置。

实现结果如下 

 常见排序算法之插入排序类,C/C++,排序算法,算法,数据结构

直接插入排序的特性总结

        1.元素集合越接近有序,直接插入排序算法的时间效率越高

        2.时间复杂度:O(N个2)

        3.空间复杂度:O(1),它是一种稳定的排序算法

        4.稳定性:稳定


二、希尔排序 

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

常见排序算法之插入排序类,C/C++,排序算法,算法,数据结构

具体实现代码如下

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; ++i)
		{
			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;
		}
	}
}

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

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

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

核心代码解析

  1. 定义一个函数ShellSort,接收一个整型指针a和整数n作为参数,其中a指向待排序的数组,n表示数组的长度。
  2. 初始化间隔gap为n。
  3. 当gap大于1时,执行以下操作: a. 更新gap的值,将其除以3并加1。 b. 使用for循环遍历数组,从0到n-gap。 i. 初始化end为当前下标i。 ii. 将a[end+gap]的值赋给临时变量tmp。 iii. 使用while循环,当end大于等于0时执行以下操作: 1) 如果tmp小于a[end],则将a[end]的值赋给a[end+gap],并将end减去gap。 2) 否则,跳出while循环。 iv. 将tmp的值赋给a[end+gap]。
  4. 当gap不再大于1时,排序完成。

 实现结果如下

常见排序算法之插入排序类,C/C++,排序算法,算法,数据结构

希尔排序的特性总结

        1.希尔排序是对直接插入排序的优化。

        2.当gap >1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比.

        3.希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的希尔排序的时间复杂度都不固定

        4.稳定性:不稳定

引用

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

常见排序算法之插入排序类,C/C++,排序算法,算法,数据结构

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

常见排序算法之插入排序类,C/C++,排序算法,算法,数据结构


结语:插入排序的相关分享到这里就结束了,希望对大家的学习会有帮助,如果大家有什么问题或者不同的见解,欢迎大家的留言~~~文章来源地址https://www.toymoban.com/news/detail-756145.html

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

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

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

相关文章

  • 数据结构算法-插入排序

    一、概念及其介绍 插入排序(InsertionSort),一般也被称为直接插入排序。 对于少量元素的排序,它是一个有效的算法。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增 1 的有序表 。在其实现过程使用双层

    2024年02月21日
    浏览(46)
  • 【数据结构与算法】十大经典排序算法-插入排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是将一个记录插入到已排好序的有序序列中,直到所有记录

    2024年02月13日
    浏览(80)
  • 数据结构算法练习 插入排序 冒泡排序

    插入排序 代码如下  package main import \\\"fmt\\\" func main() {     a := []int{4, 5, 6, 1, 3, 2}         b := insert(a)     for i := 0; i len(b); i++ {         fmt.Println(b[i])     } } func insert(a []int) []int {     if len(a) = 1 {                   如果数组长度小于等于1 不用排序直接返回          retur

    2024年02月08日
    浏览(55)
  • 数据结构与算法—插入排序&选择排序

    目录 一、排序的概念 二、插入排序   1、直接插入排序  特性总结: 2、希尔排序 特性总结:  三、选择排序 1、直接选择排序  特性总结: 2、堆排序—排升序(建大堆) 向下调整函数 堆排序函数 特性总结: 代码完整版:   头文件  函数文件  测试文件 排序 :所谓排序,

    2024年01月20日
    浏览(62)
  • 数据结构与算法:插入排序&希尔排序

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

    2024年01月17日
    浏览(55)
  • 数据结构算法--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)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包