什么是直接插入排序算法？详述直接插入排序算法的原理？用C语言实现直接插入排序算法。内附完整代码。
大家好，我是贤弟！
一、什么是直接插入排序？
直接插入排序算法（Insertion Sort）是一种基于比较的排序算法，其原理是将待排序的元素依次与已排序的元素比较，并将其插入到正确位置上，从而得到一个有序的序列。
该算法的时间复杂度为O(N^2)，适用于小规模数据的排序。
直接插入排序算法的具体实现方法如下：
1、首先，将第一个元素看作已排序的序列。
2、然后，从第二个元素开始，将其与前面已排序的序列进行比较。
3、如果当前元素比已排序序列中的某个元素小，则将已排序序列中这个元素向后移动一位，腾出空间给当前元素。
4、重复第3步操作，直到找到当前元素应该插入的位置。
5、将当前元素插入到正确位置上，将其后面的元素向后移动一位（如果存在）。
6、重复步骤2至5，直到所有元素都插入到正确位置上。
二、代码示例
下面是使用C语言实现直接插入排序算法的示例代码：
#include
void insertion_sort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; }}
int main() { int arr[] = {5, 2, 4, 6, 1, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("Before sorting:\n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } insertion_sort(arr, n); printf("\nAfter sorting:\n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0;}
备注：
该程序中使用了insertion_sort函数实现直接插入排序算法，并打印出排序前和排序后的数组。
- 发表于:
- 原文链接：https://page.om.qq.com/page/OPBwfqggIvc8pPYJzathOWYw0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
