【数据结构与算法】插入排序和希尔排序

简介: 【数据结构与算法】插入排序和希尔排序

一.插入排序  InsertSort

基本思想

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。

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

动图演示

特性总结

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

2. 时间复杂度:

       a.最坏情况下是O(N^2)

       b.最好情况下,也就是说数据是有序的,这时是O(N)

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

4. 稳定性:稳定;

1. void InsertSort(Sdatatype* arr, int n)
2. {
3.  int end = 0, tmp = 0;
4.  int i = 0;
5.  for (i = 1; i < n; i++)
6.  {
7.    end = i - 1;
8.    tmp = arr[i];
9.    while (end >= 0)
10.     {
11.       if (tmp < arr[end])
12.       {
13.         arr[end + 1] = arr[end];
14.         end--;
15.       }
16.       else
17.         break;
18.     }
19.     arr[end + 1] = tmp;
20.   }
21. 
22. 
23. }

二.希尔排序  ShellSort

基本思想

希尔排序分为预排序(即分组插排,让数组接近有序)和直接插入排序

希尔排序是把数据分成gap组,每隔gap距离的属于一组数据,对每一组内的数据进行插入排序,这样就可以让整体数据更接近有序状态,这样其内部的插入排序的时间复杂度就接近于O(N);

假设要排升序:

gap越大,跳的越快,循环的次数越少,大的数据能更快的到后面去;

gap越小,跳的越慢,循环的次数越多。

那这个gap取多少合适呢?

我们可以采用动态的gap,当一组gap跑完时,让gap/2,以此类推,因为是/2,所以gap最后的值一定是1,gap==1时就是直接插入排序了。

我们既可以采用一组一组排的方式,也可以采用多组同时进行的方式。

图例

 

 

特性总结

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

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

3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些书中给出的希尔排序的时间复杂度都不固定:但是我们一般认为是O(N^1.3)

4.稳定性:不稳定

1. void ShellSort(Sdatatype* arr, int n)
2. {
3.  int i = 0, j = 0;
4.  int end = 0, tmp = 0;
5.  int gap = n;
6.  //一组一组地排
7.  /*while (gap > 1)
8.  {
9.    gap /= 2;
10.     for (j = 0; j < gap; j++)
11.     {
12.       for (i = 0; i < n - gap; i += gap)
13.       {
14.         end = i;
15.         tmp = arr[end + gap];
16.         while (end >= 0)
17.         {
18.           if (tmp < arr[end])
19.           {
20.             arr[end + gap] = arr[end];
21.             end -= gap;
22.           }
23.           else
24.             break;
25.         }
26.         arr[end + gap] = tmp;
27.       }
28.     }
29.   }*/
30. 
31.   //同时进行排序
32.   while (gap > 1)
33.   {
34.     gap /= 2;
35.     for (i = 0; i < n-gap; i++)
36.     {
37.       end = i;
38.       tmp = arr[end + gap];
39.       while (end >= 0)
40.       {
41.         if (tmp < arr[end])
42.         {
43.           arr[end + gap] = arr[end];
44.           end -= gap;
45.         }
46.         else
47.           break;
48.       }
49. 
50.       arr[end + gap] = tmp;
51.     }
52.   }
53. }

🐬🤖本篇文章到此就结束了,若有错误或是建议的话,欢迎小伙伴们指出;🕊️👻

😄😆希望小伙伴们能支持支持博主啊,你们的支持对我很重要哦;🥰🤩

😍😁谢谢你的阅读。😸😼


目录
相关文章
|
2月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
33 1
|
2月前
|
算法 搜索推荐
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
本文介绍了冒泡排序、选择排序和插入排序三种基础排序算法的原理、实现代码和测试结果。
24 0
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
|
2月前
|
搜索推荐 算法
【排序算法(一)】——插入排序,选择排序 —> 深层解析
【排序算法(一)】——插入排序,选择排序 —> 深层解析
|
5月前
|
搜索推荐 测试技术
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
|
5月前
|
算法 搜索推荐 C#
|
5月前
|
算法 搜索推荐 Shell
|
6月前
|
人工智能 搜索推荐 JavaScript
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
46 0
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
191 9
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
32 1
|
24天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
45 5