网站开发的完整流程,建设工程招聘网,云搜索引擎,网络建设服务与网站运营推广文章目录 一、插入排序的基本原理二、插入排序的C语言实现三、代码解析 插入排序 C语言实例 一、插入排序的基本原理
插入排序的基本思想是将数组中的元素逐一取出#xff0c;然后将其插入到已经排好序的部分中的适当位置#xff0c;直到整个数组排序完成。具体步骤如下然后将其插入到已经排好序的部分中的适当位置直到整个数组排序完成。具体步骤如下 初始状态假设数组的第一个元素已经排好序。 从第二个元素开始依次取出每个元素与已经排好序的部分进行比较。 找到插入位置在已经排好序的部分中从后向前扫描找到该元素应该插入的位置。 插入元素将该元素插入到找到的位置并将插入位置之后的所有元素向后移动一位。 重复步骤重复上述步骤直到所有元素都被插入到适当位置。
二、插入排序的C语言实现
下面是一个用C语言实现的插入排序示例代码 #include stdio.h // 插入排序函数 void insertionSort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; // 将arr[i]插入到已经排好序的arr[0…i-1]中 while (j 0 arr[j] key) { arr[j 1] arr[j]; j j - 1; } arr[j 1] key; } } // 打印数组函数 void printArray(int arr[], int size) { for (int i 0; i size; i) { printf(“%d “, arr[i]); } printf(”\n”); } int main() { int arr[] {12, 11, 13, 5, 6}; int n sizeof(arr) / sizeof(arr[0]); printf(“排序前的数组: \n”); printArray(arr, n); insertionSort(arr, n); printf(“排序后的数组: \n”); printArray(arr, n); return 0; }
三、代码解析
函数定义 insertionSort(int arr[], int n)接受一个整数数组和数组的大小作为参数对数组进行排序。 printArray(int arr[], int size)接受一个整数数组和数组的大小作为参数打印数组内容。 排序过程 在insertionSort函数中使用两层循环实现排序。外层循环变量i从1开始表示当前要插入的元素。内层循环变量j从i-1开始向前扫描已经排好序的部分。 如果arr[j]大于key当前要插入的元素则将arr[j]向后移动一位。 当找到合适的位置后将key插入到该位置。 主函数 定义一个待排序的数组arr。 调用printArray函数打印排序前的数组。 调用insertionSort函数对数组进行排序。 再次调用printArray函数打印排序后的数组。 四、插入排序的性能分析 时间复杂度 最好情况O(n)数组已经有序 平均和最坏情况O(n^2)数组完全逆序 空间复杂度O(1)不需要额外的存储空间 稳定性稳定相同元素的相对顺序保持不变 插入排序适用于小规模数据排序或者部分有序的数据集。虽然其时间复杂度在最坏情况下较高但由于其实现简单且稳定在实际应用中仍有一定的价值。
