插入排序详解!!!(简单排序),基本功排序C语言版

发布时间:2024年01月05日

目录

1.什么是插入排序

2.插入排序的源代码

3.源代码详解


1.什么是插入排序

? 这是一个插入排序的流程图,插入排序 很像我们玩斗地主,玩牌,斗地主在开始前,我们是不是要给我们手上的牌排序啊,假设我们理牌有一个规矩就是只能一张一张拿起来。并且我们给牌换位置也只能一张一张换。不能中间跳过一张直接换(因为机器和人脑不同)

那我们拿起第一张的时候,和上图一样我们拿到一个3,那现在就只有一个3,你也不用排序

但我们拿到第二张的时候,这时有两张牌,拿到的是5,它确实比3大,那5就在3的后面就好

我们拿到第三张2的时候,这时候2是不是比5小,那2 和 5就交换,现在手牌就是 3 2 5,然后因为现在 2 的 前一张牌还是大于2,我们就再交换一下,手牌就变成了2 3 5.

这样就完成了一次插入排序。

后面的插入排序也是在这个基础上循环即可

2.插入排序的源代码

#include<stdio.h>
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void My_Insertsort(int* arr,int sz)
{
	for (int i = 1; i < sz; i++)
	{
		if (arr[i] < arr[i - 1])
		{
			for (int j = i - 1; j >= 0; j--)
			{
				if (arr[j] > arr[j + 1])
				{
					Swap(&arr[j], &arr[j+1]);
				}
                else
                {
                    break;
                }
			}
		}
	}
}


int main()
{
	int arr[] = { 2,4,1,6,7,2,10,22,44,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	My_Insertsort(arr, sz);
	return 0;
}

3.源代码详解

#include<stdio.h>
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void My_Insertsort(int* arr,int sz)
{
	for (int i = 1; i < sz; i++)
	{
		if (arr[i] < arr[i - 1])
		{
			for (int j = i - 1; j >= 0; j--)
			{
				if (arr[j] > arr[j + 1])
				{
					Swap(&arr[j], &arr[j+1]);
				}
                else
                {
                    break;
                }
			}
		}
	}
}

?源代码主要解释的是这一块。

1.第一个for循环是为了遍历除了arr【0】之后的数组arr。

2.if 判断语句 现在 i 位置 小于?前一个位置的数据,这是进入下一个循环的前提。因为从头开始我们每一次 都已经把前面的数字排成有序的。才进行下一个数字的排序。就像 你现在手牌上是 3 5 如果抽到的不是2 是 7(下图),那这张7自然而然就是 最后。不用再往前比了。

3. 第二个for循环 ,就是现在i 这个位置的数字,一个一个往后比,直到遇到比这个数字还小的就停止循环。就比如你现在 手牌 还是 3 5 ,你接下来拿到一张4 ,你4这个位置先和5换了,然后在前面一张发现是3,小于4,那你就没必要换了,最后就变成了 3 4 5.

?

文章来源:https://blog.csdn.net/a1275174052/article/details/135316411
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。