排序算法实现：插入排序与希尔排序

目录

一、引言 

二、代码整体结构 

三、宏定义与头文件 

四、插入排序函数（Insertsort）

函数作用 

代码要点分析 

五、希尔排序函数（ShellSort） 

函数作用 

代码要点分析 

六、打印数组函数（PrintSort） 

 函数作用 

代码要点分析 

七、测试函数（TestSort）与主函数（main） 

 函数作用 

代码要点分析 

八、总结 

---

一、引言
 

在计算机科学领域，排序算法是非常基础且重要的内容。不同的排序算法有着各自的特点和适用场景。本文将基于给定的C语言代码，深入剖析插入排序（Insertion Sort）和希尔排序（Shell Sort）的实现过程，帮助读者更好地理解这两种排序算法的原理与应用。

 

作者主页：共享家9527-CSDN博客
二、代码整体结构
 

代码主要包含了插入排序函数、希尔排序函数、打印数组函数以及测试函数和主函数，整体结构清晰，便于理解和维护。下面我们对每个函数进行详细分析。

三、宏定义与头文件
 

c#define _CRT_SECURE_NO_WARNINGS
#include"Sort.h"

 
 #define _CRT_SECURE_NO_WARNINGS  这一宏定义的作用是在使用一些被认为可能存在安全风险的C标准库函数（如 scanf 、 strcpy 等）时，避免编译器产生警告信息。 #include"Sort.h"  表示包含自定义的头文件 Sort.h ，虽然在给出的代码中未看到该头文件的具体内容，但通常它会包含一些函数声明、类型定义等内容，方便代码的模块化管理。

四、插入排序函数（Insertsort）

c//插排
void Insertsort(int* a, int n){for (int i = 1;i < n;i++){int end = i - 1;int temp = a[i];while (end >= 0){if (temp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = temp;}
}

函数作用
 

插入排序函数的功能是对给定的整数数组进行排序，排序的基本思想是将一个数据插入到已经排好序的数组中的适当位置。
 

代码要点分析
 

1. 外层循环： for (int i = 1;i < n;i++)  从数组的第二个元素开始（因为第一个元素可以看作是已经排好序的子数组），依次将每个元素插入到前面已排序的子数组中的合适位置。
 
2. 初始化变量： int end = i - 1;  定义 end 变量表示已排序子数组的最后一个元素的下标。 int temp = a[i];  将当前待插入的元素暂存到 temp 变量中。
 
3. 内层循环： while (end >= 0)  当 end 大于等于0时，继续循环，即只要还在已排序的子数组范围内，就进行比较和移动操作。 if (temp < a[end])  如果待插入元素小于当前已排序子数组的最后一个元素，则将该元素向后移动一位，同时 end 减1，继续向前比较。当遇到不满足该条件的元素时，说明找到了待插入元素的合适位置，通过 break 跳出循环。
 
4. 插入操作： a[end + 1] = temp;  将暂存的待插入元素插入到合适的位置。
 

五、希尔排序函数（ShellSort）

c//希尔
void ShellSort(int* a, int n)
{int gap = 9;while (gap > 0){gap /= 2;for (int j = 0;j < gap;j++){for (int i = j;i < n - gap;i += gap){int end = i;int temp = a[i + gap];while (end >= 0){if (temp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = temp;}}}
}

 

函数作用
 

希尔排序是插入排序的一种改进版本，通过将数组按照一定的间隔（ gap ）进行分组，对每组分别进行插入排序，随着间隔逐渐减小，最终完成整个数组的排序。
 

代码要点分析
 

1. 初始间隔设置： int gap = 9;  定义初始的分组间隔，这里设置为9，不同的初始间隔可能会影响排序的效率。
 
2. 间隔调整循环： while (gap > 0)  当间隔大于0时，继续进行排序操作。每次循环中， gap /= 2;  将间隔逐渐缩小，直到间隔为1时，相当于进行一次普通的插入排序。
 
3. 分组循环： for (int j = 0;j < gap;j++)  对每个分组进行遍历，确保每个分组都能进行插入排序操作。
 
4. 组内插入排序循环： for (int i = j;i < n - gap;i += gap)  对每个分组内的元素进行插入排序，类似于插入排序的过程，但这里元素之间的比较和移动是按照间隔 gap 进行的。
 
5. 插入操作：与插入排序类似，通过比较和移动元素，将当前元素插入到分组内合适的位置。
 

六、打印数组函数（PrintSort）
 

cvoid PrintSort(int* a, int n)
{for (int i = 0;i < n;i++){printf("%d ",a[i]);}printf("\n");
}

 
函数作用
 

该函数的功能是将给定的整数数组按照顺序打印输出，方便查看数组在排序前后的状态。
 

代码要点分析
 

通过一个简单的 for 循环遍历数组，使用 printf 函数逐个输出数组元素，并在最后换行，使输出结果更加清晰易读。
 

七、测试函数（TestSort）与主函数（main）
 

cvoid TestSort()
{int arr[] = { 9,5,1,3,7,8,4,2,6,0 };int n = sizeof(arr) / sizeof(arr[0]);PrintSort(arr, n);Insertsort(arr, n);//ShellSort(arr, n);PrintSort(arr, n);
}int main()
{TestSort();return 0;
}

 
函数作用
 

 TestSort 函数用于测试排序算法的正确性，在函数内部创建一个测试数组，先打印数组的初始状态，然后调用插入排序函数对数组进行排序，再次打印排序后的数组状态。 main 函数则是程序的入口，调用 TestSort 函数来执行测试。
 

代码要点分析
 

1. 在 TestSort 函数中， int arr[] = { 9,5,1,3,7,8,4,2,6,0 };  创建一个包含10个整数的测试数组。 int n = sizeof(arr) / sizeof(arr[0]);  计算数组的元素个数。
 
2. 调用 PrintSort 函数打印数组初始状态，然后调用 Insertsort 函数进行排序，注释掉的 ShellSort(arr, n);  表示如果需要测试希尔排序，可取消注释。最后再次调用 PrintSort 函数打印排序后的数组。
 
3.  main 函数中仅调用 TestSort 函数，程序从这里开始执行。
 

八、总结

通过对上述代码的详细分析，我们深入了解了插入排序和希尔排序的实现过程。插入排序简单直观，适用于小规模数据的排序；希尔排序作为插入排序的改进算法，通过分组和逐渐缩小间隔的方式，提高了排序效率，尤其在处理大规模数据时表现更为出色。在实际应用中，我们可以根据数据的特点和规模，选择合适的排序算法来满足需求。