💯 博客内容:【数据结构】插入排序详细图解(一看就懂)
😀 作 者:陈大大陈
🦉所属专栏:数据结构笔记
🚀 个人简介:一个正在努力学技术的准前端,专注基础和实战分享 ,欢迎私信!
💖 欢迎大家:这里是CSDN,我总结知识和写笔记的地方,喜欢的话请三连,有问题请私信 😘 😘 😘
目录
前言引入
插入排序的原理
插入排序源码
详细实例过程图解
本章小结
前言引入
插入排序是一种非常有意思且比较高效的排序方法,同时插入排序是希尔排序的基础 。
我预备下一篇博客讲解希尔排序,这一篇就先讲一下插入排序。
在生活中,这种排序方法也随处可见。
例如,我们在玩扑克牌时,总会按照插入排序的方法调整扑克牌的位置。
玩扑克牌怎么会用到插入排序的方法呢?
当我们拿起第二张牌时,就会下意识的与第一张牌进行比较,如果比第一张牌小,我们就会将牌插入至第一张牌的左边,反之就插入至右边。
这样边插入边排序,就是插入排序,插入后的序列依旧是有序的。
大家先看一下下面的原理和代码,然后再看实例图可能会比较好。
插入排序的原理
当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移。
我们将原数组空间看成两个部分,前边是有序部分,后边是无序部分,有序部分我们默认为它就已经是排好序的,在尾部新加入的元素有可能会导致整个有序数组变得无序,因此我们需要进行调整。
调整方式就是将新加入的元素进行对比并往前移动,新加入元素和它前边的元素进行对比,如果它比它前边的元素小,则二者互换位置,不断重复这个过程,直到它前边的元素小于它才会停止,这样一来,他就仍然是有序数组。
插入排序源码
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void InsertSort(int* a, int n)
{
int tmp;
int end;
for (int i = 1; i < n; i++)
{
end = i - 1;
tmp = a[i];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
int main()
{
int a[] = { 45,67,89,12,34,5,6,8,1,2,67,99,55 };
InsertSort(a, sizeof(a) / sizeof(a[0]));
for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++)
{
printf("%d ", a[i]);
}
return 0;
}
/*{ 45,45,89,12,34,5,6,8,1,2,67,99,55 };*/
运行结果
详细实例过程图解
就按这组数据为例,此时end处的值不大于i处的值,不用进入循环, a[end + 1] = tmp;不造成影响
第二次,同理,i++继续往后走。
第三次,这次不一样了!a[end]>a[i],也就是a[end]大于tmp了,进入循环。
循环一次,完成 a[end + 1] = a[end]; end--;a[end+1]=tmp;的操作。
此时end值为1,大于0,循环继续。
循环两次,完成 a[end + 1] = a[end]; end--;a[end+1]=tmp;的操作。
此时end值为0,等于0,循环继续。
循环三次, 完成 a[end + 1] = a[end]; end--;a[end+1]=tmp;的操作。
此时end值为-1,小于0,循环结束。
第一次排序结束,下面的排序也就是比葫芦画瓢了,这里我就不列举了。
本章小结
直接插入排序的特性总结:1. 元素集合越接近有序,直接插入排序算法的时间效率越高2. 时间复杂度:O(N^2)3. 空间复杂度:O(1),是一种稳定的排序算法4. 是否稳定:稳定
下一篇更新希尔排序,博客里如果有问题的话,还请大佬私信我,我会修改的。文章来源:https://www.toymoban.com/news/detail-467002.html
有问题的话请私信问我,我看到就会回的。 文章来源地址https://www.toymoban.com/news/detail-467002.html
到了这里,关于【数据结构】插入排序详细图解(一看就懂)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!