有哪些网站做明星周边,贵州百度竞价网页设计,网站开发的需求文档,有公司如何制作网站欢迎来到CILMY23的博客
#x1f3c6;本篇主题为#xff1a;【数据结构与算法】选择排序篇----详解直接插入排序和哈希排序
#x1f3c6;个人主页#xff1a;CILMY23-CSDN博客
#x1f3c6;系列专栏#xff1a;Python | C | C语言 | 数据结构与算法 | 贪心算法 | Linux… 欢迎来到CILMY23的博客
本篇主题为【数据结构与算法】选择排序篇----详解直接插入排序和哈希排序
个人主页CILMY23-CSDN博客
系列专栏Python | C | C语言 | 数据结构与算法 | 贪心算法 | Linux | 算法专题 | 代码训练营
感谢观看支持的可以给个一键三连点赞关注收藏。 前言
本期要讲解的是常见排序算法中的插入排序插入排序又分两种一种是直接插入排序一种是希尔排序。 一、直接插入排序
1.1 插入排序的基本思想
插入排序是一种简单的插入排序方法其基本思想是
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。
实际中我们玩扑克牌时就用了插入排序的思想我们从桌面抽一张牌然后把牌按照我们所想的情况排序插入到合适的位置这就是插入排序的大致过程。 1.2 直接插入排序操作
当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 1.3 直接插入排序的特性总结
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)逆序最好情况是O(N) (顺序有序)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定
1.4 代码实现
第一部分
先写单趟的排序现在取 end 之前的位置都是有序的要比对的数值是 end1 的位置数这里我们用一个变量 tmp 来存储。
我们想实现升序的tmp
如果 tmp 比 end 位置的值小那么就要把 end 位置的数值往后移动end 往前移动直到我们找到 tmp 比 end 位置的数值小我们就可以直接插入。 特殊情况
当 end1 处的位置为最小值时此时 end 为 -1 tmp 也就是 end1 的位置处于 0 。 代码
首先先不管end 是多少我们知道[0,end]是有序那end 1 位置就是我们要比较的数假设这个数比end位置小那前面的位置就往后移动直到数组尽头或者找到比 end位置要大的数在这个数的后面进行插入。
int end;
int tmp a[end1];
while(tmp a[end])
{a[end1] a[end];end--;
}
a[end1] tmp
为什么最后是end1 取第二种极端情况也就是插入排序的end走到尽头了此时end 为 -1 这时候我们要在数组下标0的位置插入所以要1。 第二部分
确认多趟的情况 首先得保证前 end 都是有序的想要确认end前有序我们就再套一层循环从0开始让 end 从 0 的位置开始遍历每个数值过去这样整个数组都可以实现排序了。
void Insert_Sort(int* a, int n)
{for (int 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];end--;}else{break;}}a[end 1] tmp;}
} 1.5 动图理解 二、希尔排序缩小增量排序
2.1 基本思想
希尔排序法又称缩小增量法。
希尔排序法的基本思想是
先选定一个整数把待排序文件中所有记录分成按距离的个组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达gap1时所有记录在统一组内排好序。
例如下图
第一趟排序gap 5,从第一个数开始每隔五个数取一组9和4为一组1和8为一组2和6为一组5和3为一组7和5为一组这样整个数组都分好了然后在每个小组里面进行排序9和4排序因为9比4大所以9在后面4在前面以此类推……
第二趟排序gap 3从第一个数开始每隔三个数取一组4,2,5,8,5为一组1,3,9,6,7为一组这样整个数组就又分好了然后在每个小组里面进行排序42585排序排好后就是42585.同样以此类推排第二个小组。
在这样的排序下就逐渐接近了有序的数组。我们把这样的操作叫做预排序。
最后第三趟排序当gap 1时你会发现这个跟直接插入排序没有区别开始取第一个数保证第一个数有序然后开始走直接插入的思想。 通过这样的过程我们就可以发现直接插入排序也是希尔排序中的一步骤。
2.2 希尔排序的特性总结
1. 希尔排序是对直接插入排序的优化。 2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样排序起来就会很快。对整体而言可以达到优化的效果。 3. 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的希尔排序的时间复杂度都不固定但也有大致算出来的。估计结果为O(n^1.3)
4. 稳定性不稳定
2.3 希尔排序代码
void Shell_Sort(int *a,int n)
{int gap n;while (gap 1){gap gap / 2;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{tmp;}}a[end] tmp;}}
}
2.4 希尔排序操作详解 希尔排序分两步走一步是预排序它的目的是让整个数组接近有序第二步是直接插入排序。
第一种预排序一组一组排序
预排序的思路如下 先把数组分成以gap为距离的各个小组把分好的各单位小组进行插入排序对每个小组进行插入排序 第一步
假设我们现在有这样的三个小组分别用红橙绿三种颜色进行标记。 把红色的第一个小组单独拿出来 我们标上下标我们发现对这一个小组进行插入排序原先的end1就变成了endgap。
现在是交换红色的部分橙色和绿色我们并不在乎。因为tmp nums[end],所以只需要比较end处和endgap处的值然后继续直接插入排序的操作即可。 我们可以仿照直接插入排序写出如下的红色单区排序。
int gap 3;
int end 0;
int tmp a[end gap];
while (end 0)
{if (tmp a[end]){a[end gap] a[end];end - gap;}else{tmp;}
}
a[end] tmp;
第二步 然后控制多个红色小组 我们套一层for循环注意j不能超过n-gap防止endgap越界。
最大的地方是endgap n - 1
所以 j end n-gap-1 j n - gap。
int gap 3;
for (int j 0; j n - gap; j gap)
{int end 0;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{tmp;}}a[end] tmp;
}
第三步
控制多个组进行插入排序
int gap 3;
for (int i 0; i gap; i)
{for (int j 0; j n - gap; j gap){int end 0;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{tmp;}}a[end] tmp;}
} 第二种预排序多组并排 其实这里的多组并排原理很简单就是让end按照顺序走下去 也就是将第二步和第三步合并了这就很接近我们刚开始的步骤。 所以预排序 gap越大大的值更快调整到后面小的值更快调用到前面 越不接近有序 gap越小 跳的越慢 越接近有序如果gap1那就是插入排序。 代码
end每次只走一步这样一组组的跳就是多组并排了。
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{tmp;}}a[end] tmp;
}
第二步 直接插入排序
要想最后接近有序每次gap就要变化最后一次gap1所以gap要跟着n进行变化 所以在外围添加一个循环当gap 1的时候是预排序当gap 1的时候是直接插入排序。
int gap n;
while (gap 1)
{gap gap / 2;//觉得一次2太小//gap gap / 3 1//...
}
2.5 希尔排序动图 ️感谢各位同伴的支持本期数据结构与算法---选择排序篇就讲解到这啦如果你觉得写的不错的话可以给个一键三连点赞关注收藏若有不足欢迎各位在评论区讨论。
