排序算法(三)--插入排序

一、插入排序的基本原理

插入排序的基本思想是将数组中的元素逐一取出，然后将其插入到已经排好序的部分中的适当位置，直到整个数组排序完成。具体步骤如下：
初始状态：假设数组的第一个元素已经排好序。
从第二个元素开始：依次取出每个元素，与已经排好序的部分进行比较。
找到插入位置：在已经排好序的部分中，从后向前扫描，找到该元素应该插入的位置。
插入元素：将该元素插入到找到的位置，并将插入位置之后的所有元素向后移动一位。
重复步骤：重复上述步骤，直到所有元素都被插入到适当位置。

二、插入排序的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)（不需要额外的存储空间）
稳定性：稳定（相同元素的相对顺序保持不变）
插入排序适用于小规模数据排序，或者部分有序的数据集。虽然其时间复杂度在最坏情况下较高，但由于其实现简单且稳定，在实际应用中仍有一定的价值。