什么是直接插入排序算法？详述直接插入排序算法的原理？用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函数实现直接插入排序算法，并打印出排序前和排序后的数组。