从插入排序到希尔排序

从插入排序到希尔排序

  插入排序

  原理

  

插入排序是一种简朴直观的排序算法，其根本头脑是通过将每个元素逐个插入到已排序的部分中，渐渐构建一个有序序列。

  操作步骤

  

• 初始化：将第 1 个元素视为已经有序的部分（初始时长度为 1）。
  
  
• 遍历数组：从第 2 个元素开始，依次将其视为待插入的“新”元素。
  
  
• 查找位置：在已排序部分中找到该元素的精确位置，并将其插入到适当的位置。
  
  

  

• 从已排序部分的末尾向前查找，找到第 1 个小（大）于等于 arr 的元素位置。
  
  
• 将 arr 插入到该位置之后。
  
  

  

重复步骤：直到全部元素都处理完毕。

  排序过程

  

  

• 默认[ 3 ]视为有序部分。
  
  
• 第 1 轮遍历排序 8，将其插入 3 前面，并将 [ 8 3 ] 视为有序部分。
  
  
• 第 2 轮遍历排序 5，将其插入 8 后面，并将 [ 8 5 3 ] 视为有序部分。
  
  
• 第 3 轮遍历排序 1，将其插入 3 后面，并将 [ 8 5 3 1 ] 视为有序部分。
  
  
• 第 4 轮遍历排序 2，将其插入 3 后面，并将 [ 8 5 3 2 1] 视为有序部分。
  
  
• 第 5 轮遍历排序 6，将其插入 8 后面，并将 [ 8 6 5 3 2 1 ] 视为有序部分。
  
  
• 第 6 轮遍历排序 9，将其插入 8 前面，并将 [ 9 8 6 5 3 2 1 ] 视为有序部分。
  
  
• 第 7 轮遍历排序 7，将其插入 8 后面，并将 [ 9 8 7 6 5 3 2 1 ] 视为有序部分。
  
  

  代码实现

1. /**
2.  * @ 简单插入排序
3.  * @ arr - 待排序的数组     num - 数组元素个数
4.  * @ 要求从大到小排序数据
5.  * */ 
6. void simple_insertion_sort(int *arr, int num)
7. {
8.     int i, j, tmp;
10.     for (i=1; i<num; i++) {
11.         j = i - 1;      /* 有序部分最后一个索引 */
12.         tmp = arr[i];   /* 当前待插入的元素 */
14.         /* 1. 若插入数据比有序部分最后一个元素还小，无需处理 */
15.         if (arr[j] >= tmp) {
16.             continue;
17.         }
19.         /* 2. 查找带插入数据位置，并后移数据腾出位置 */
20.         while (j >= 0) {          
21.             if (arr[j] >= tmp)
22.                 break;
24.             arr[j+1] = arr[j];
25.             j--;
26.         }
28.         /* 3. 插入到正确位置 */
29.         arr[j+1] = tmp;
30.     }
31. }

复制代码

技能点

  

• 提前制止内层循环：在内层循环中，如果当前已排序部分的第一个元素已经小于等于待插入元素，则无需继续比较，直接结束内层循环。这可以减少不须要的比较操作。
  
  

  进阶代码

  

插入排序，可以理解为从序列中第 1 个元素开始，隔断固定 1 个元素，进行的序列排序。

  

假设程序猿想要在序列中从任意元素 (start_pos) 位置开始，隔断固定元素个数 (gap) 提取成新的序列进行插入排序，此时代码又该怎样进行通用筹划呢？

1. /**
2.  * @ 插入排序
3.  * @ arr - 待排序的数组                 num - 数组元素个数
4.  * @ start_pos - 待处理元素起始位置     gap - 间隔
5.  * @ 要求从大到小排序数据
6.  * */ 
7. void insertion_sort(int *arr, int num, int start_pos, int gap)
8. {
9.     int i;
10.     int index;          /* 用于有序部分数据遍历索引 */
11.     int insert_data;    /* 用于记录待插入的数据 */
13.     for (i=start_pos+gap; i<num; i+=gap) {
14.         index = i - gap;        /* 有序部分最后一个索引，从最后一个开始索引 */
15.         insert_data = arr[i];   /* 当前待插入的元素 */
17.         /* 1. 若插入数据比有序部分最后一个元素还小，无需处理 */
18.         if (arr[index] >= insert_data) {
19.             continue;
20.         }
22.         /* 2. 查找带插入数据位置，并后移数据腾出位置 */
23.         while (index >= 0) {          
24.             if (arr[index] >= insert_data)
25.                 break;
27.             arr[index + gap] = arr[index];
28.             index -= gap;
29.         }
31.         /* 3. 插入到正确位置 */
32.         arr[index + gap] = insert_data;
33.     }
34. }

复制代码

• 注意：我们只需将start_pos = 0 且 gap = 1 就相当于简朴插入排序。
  
  

  运行效果

  
  

  总结

  

插入排序作为基础排序算法之一，虽然在最坏环境下性能不佳，但在某些特定场景下仍然具有其独特的优势。通过优化如“提前制止内层循环”等方法，可以在一定程度上提升效率，使其更恰当于小规模数据或部分有序的数据。然而，对于大规模数据来说，仍然建议使用更高效的排序算法。

  希尔排序

  原理

  

希尔排序是一种改进的插入排序，它答应在远距离的元素之间进行比较和互换，从而减少排序的时间复杂度。

  

• 确定步长：选择一个初始步长 gap，通常取数组长度的一半。
  
  
• 分组排序：将数组分成若干个子序列，每个子序列中的元素隔断为当前的步长 gap。
  
  
• 渐渐缩小步长：对每一个子序列进行插入排序或其他排序算法（如互换排序），然后减小步长 gap，重复分组和排序的过程，直到步长为1，此时整个数组视为一个子序列，进行一次插入排序。
  
  

  操作步骤

  

• 初始化步长：设置初始步长 gap = n / 2，其中 n 是数组的长度。
  
  
• 循环调解步长：当前步长减半：gap = gap / 2 直到步长为 0
  
  
• 分组排序：对于每个子序列（元素隔断为当前步长），进行插入排序或其他稳定排序算法。
  
  

  排序过程

  

     
   

• 确定序列元素数目 n=8
  
  
• 第 1 次排序
  
  
  
  
  • 将序列分为  n/2 = 4 组,每组固定隔断  gap = n/2 = 4 元素。
    
    
  • 分组环境 [ 3 2 ]   [ 8 6 ]   [ 5 9 ]   [ 1 7 ]。
    
    
  • 对于每组进行插入排序得到 [ 3 2 ]   [ 8 6 ]   [ 9 5]   [ 7 1]。
    
    
  • 归并之后的序列为 [ 3 8 9 7 2 6 5 1]。
    
    
  
  
• 第 2 次排序
  
  
  
  
  • 将序列分为  gap/2 = 2组,每组固定隔断  gap = gap/2 = 2元素。
    
    
  • 分组环境 [ 3 9 2 5 ]   [ 8 7 6 1 ]。
    
    
  • 对于每组进行插入排序得到 [ 9 5 3 2 ]   [ 8 7 6 1 ]。
    
    
  • 归并之后的序列为 [ 9 8 5 7 3 6 2 1]。
    
    
  
  
• 第 3 次排序
  
  
  
  
  • 将序列分为  gap/2 = 1组,每组固定隔断  gap = gap/2 = 1元素。
    
    
  • 等同于简朴插入排序。
    
    
  • 排序之后的序列为 [ 9 8 7 6 5 3 2 1]。
    
    
  
  

  代码实现

1. /**
2.  * @ 希尔排序，插入排序的优化
3.  * @ arr - 待排序的数组     num - 数组元素个数
4.  * @ 要求从大到小排序数据
5.  * */ 
6. void shell_sort(int *arr, int num)
7. {
8.     int i;
9.     int gap = num / 2;    /* 控制间距, 默认从 num/2 开始 */
11.     while (gap > 0) {           /* 控制间距 */
12.         for (i=0; i<gap; i++) { /* 控制组数 */
13.             /* 调用插入排序 */
14.             insertion_sort(arr, num, i, gap);
15.         }
16.         gap /= 2;
17.     }
18. }

复制代码

分析

  

• 希尔排序主要还是引入了分组的概念，通太过组将序列拆分成小序列，并且根据隔断实现远距离数据的快速排序，从而减少数据比较与移位的处理，降低时间复杂度。
  
  
• 相对于插入排序，希尔排序主要多了两层循环，一层用于控制隔断 gap，一层用于当前隔断下各个组的插入排序处理。
  
  

  运行效果

  

  缺点

  

• 希尔排序在大多数实现中并不是稳定的排序算法。这意味着，当两个相等的元素出现时，它们的相对顺序大概会被打乱。
  
  
• 在某些特定的数据分布下，希尔排序的时间复杂度大概退化到O(n²)，这与普通的插入排序相当，无法发挥其高效的理论优势。
  
  
• 希尔排序的性能严峻依赖于步长序列的选择。如果步长选择不妥，大概导致算法效率低下或排序失败。
  
  

  优化方法

  

• 改进步长序列的选择：使用更科学的步长序列，如Sedgewick提出的步长序列：1, 3, 7, 15, 31,…。这种步长序列可以在一定程度上减少排序过程中的逆序数，提高算法效率。
  
  
• 确保稳定性：在比较和互换元素时，除了比较巨细外，还应考虑元素的原始位置。例如，在比较两个相等的元素时，优先保存原位置较前的元素。这可以通过在键值对中包罗索引信息来实现。
  
  
• 优化排序过程中的细节：在内循环中，只管减少不须要的数据移动和比较操作。例如，当发现当前元素已经位于精确的位置时，可以提前制止内层循环。
  
  
• 联合其他优化技能：将希尔排序与其他排序算法的优点联合起来，如在小规模的数据子集上使用更高效的排序方法（如归并排序或快速排序）进行优化。
  
  

  完备代码

1. /**
2.  * @Filename : insertion_sort.c
3.  * @Revision : $Revision: 1.00 $
4.  * @Author : Feng(更多编程相关的知识和源码见微信公众号：不只会拍照的程序猿，欢迎订阅)
5.  * @Description : 从插入排序一步一步到希尔排序
6. **/
8. #include <stdio.h>
9. #include <string.h>
11. #define MAX_NUM     8  
12. staticint cnt = 0; /* 统计排序次数 */
14. /**
15.  * @ 打印数组
16.  * @ arr - 待打印的数组     num - 数组元素个数
17.  * */
18. void print_arr(int *arr, int num) 
19. {
20.     int i;
22.     for (i=0; i<num; i++)
23.         printf("%02d ", arr[i]);
24.     printf("\n");
25. }
27. /**
28.  * @ 插入排序
29.  * @ arr - 待排序的数组                 num - 数组元素个数
30.  * @ start_pos - 待处理元素起始位置     gap - 间隔
31.  * @ 要求从大到小排序数据
32.  * */
33. void insertion_sort(int *arr, int num, int start_pos, int gap)
34. {
35.     int i;
36.     int index;          /* 用于有序部分数据遍历索引 */
37.     int insert_data;    /* 用于记录待插入的数据 */
39.     for (i=start_pos+gap; i<num; i+=gap) {
40.         index = i - gap;        /* 有序部分最后一个索引，从最后一个开始索引 */
41.         insert_data = arr[i];   /* 当前待插入的元素 */
43.         cnt++;
45.         /* 1. 若插入数据比有序部分最后一个元素还小，无需处理 */
46.         if (arr[index] >= insert_data) {
47.             printf("无需移位 第%02d次排序: ", cnt);
48.             print_arr(arr, num);
49.             continue;
50.         }
52.         /* 2. 查找带插入数据位置，并后移数据腾出位置 */
53.         while (index >= 0) {          
54.             if (arr[index] >= insert_data)
55.                 break;
57.             arr[index + gap] = arr[index];
58.             index -= gap;
59.         }
61.         /* 3. 插入到正确位置 */
62.         arr[index + gap] = insert_data;
64.         printf("需要移位 第%02d次排序: ", cnt);
65.         print_arr(arr, num);
66.     }
67. }
69. /**
70.  * @ 简单插入排序
71.  * @ arr - 待排序的数组     num - 数组元素个数
72.  * @ 要求从大到小排序数据
73.  * */
74. void simple_insertion_sort(int *arr, int num)
75. {
76.     printf("排序前数组内容: ");
77.     print_arr(arr, num);
79.     cnt = 0;    /* 清空统计次数 */
80.     insertion_sort(arr, num, 0, 1);
82.     printf("排序后数组内容: ");
83.     print_arr(arr, num);
84. }
86. /**
87.  * @ 希尔排序，插入排序的优化
88.  * @ arr - 待排序的数组     num - 数组元素个数
89.  * @ 要求从大到小排序数据
90.  * */
91. void shell_sort(int *arr, int num)
92. {
93.     int i;
94.     int gap = num / 2;    /* 控制间距, 默认从 num/2 开始 */
96.     printf("排序前数组内容: ");
97.     print_arr(arr, num);
99.     cnt = 0;    /* 清空统计次数 */
101.     while (gap > 0) {           /* 控制间距 */
102.         for (i=0; i<gap; i++) { /* 控制组数 */
103.             /* 调用插入排序 */
104.             insertion_sort(arr, num, i, gap);
105.         }
106.         gap /= 2;
107.     }
109.     printf("排序后数组内容: ");
110.     print_arr(arr, num);
111. }
113. int main(void)
114. {
115.     int buf1[] = {3, 8, 5, 1, 2, 6, 9, 7};
116.     int buf2[] = {3, 8, 5, 1, 2, 6, 9, 7};
118.     printf ("----------简单插入排序---------\n");
119.     simple_insertion_sort(buf1, MAX_NUM);
121.     printf ("---------希尔排序---------\n");
122.     shell_sort(buf2, MAX_NUM);
123.     
124.     return0;
125. }

复制代码

运行效果

  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。