C语言实现冒泡、插入与折半插入排序详解

本文档详细介绍了如何使用C语言实现三种常见的排序算法：冒泡排序、插入排序以及折半插入排序。这些排序方法在计算机科学中具有重要的应用，尤其是在处理小型到中型数据集时。 1. **冒泡排序**：这是一种简单的排序方法，通过不断比较相邻的元素并交换它们的位置，如果前一个元素大于后一个，直到整个数组有序。冒泡排序的时间复杂度为O(n^2)，其中n是数组的长度。其特点是稳定，即相等的元素相对位置不会改变。在实现中，引入了一个布尔变量`hasSwap`来优化，检查数组是否已经有序，若无交换则提前结束循环。 ```c void bubble_sort(int arr[], size_t len){ size_t i, j; bool hasSwap = false; for (i = 0; i < len; i++) { for (j = 1; j < len - i; j++) { if (arr[j - 1] > arr[j]) { swap(&arr[j - 1], &arr[j]); hasSwap = true; } } if (!hasSwap) { break; } } } ``` 2. **插入排序**：逐个元素插入到已排序部分的适当位置，确保整体保持有序。插入排序的时间复杂度同样为O(n^2)，但常用于小型数组或基本有序的数据，此时效率较高。插入排序也是稳定的。 ```c void insert_sort(int arr[], int len){ int i, j; for (i = 1; i < len; i++) { int key = arr[i]; for (j = i - 1; j >= 0 && arr[j] > key; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = key; } } ``` 3. **折半插入排序**：对插入排序的改进，使用半分查找确定插入位置，这使得在平均情况下效率提高。尽管仍为O(n^2)，但在某些情况下性能优于简单插入排序。此方法同样保持了稳定性。 ```c void half_insert_sort(int arr[], int len){ // ...（省略半分查找的具体实现） } ``` 这三种排序方法虽然在大规模数据上不如更高效的算法如快速排序、归并排序等，但对于理解基本的排序原理和实现技巧具有重要意义，并且在特定场景下可能仍然适用。通过这些C语言实现，学习者能够掌握基础排序算法的实现过程，进一步提升编程技能。