C语言实现高效插入排序算法

"C语言实现插入排序的代码示例" 在编程领域，排序算法是数据处理的基础，而插入排序是一种简单直观的排序算法。本文将详细解析如何使用C语言来实现插入排序。 插入排序的工作原理可以这样理解：想象一个有序的序列（初始时可能只包含一个元素），然后逐个将未排序的元素插入到已排序序列的正确位置。这个过程就像玩扑克牌，每次从手里拿一张牌，找到它在已排序手牌中的合适位置并插入。 以下C语言实现的插入排序代码： ```c #include<stdio.h> // 定义插入排序函数 void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; // 查找key的正确位置并移动元素 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } // 主函数 int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); // 调用插入排序函数 insertionSort(arr, n); printf("Sorted array:\n"); // 输出排序后的数组 for (int i = 0; i < n; i++) { printf("%d", arr[i]); } return 0; } ``` 在这段代码中，`insertionSort`函数是核心，它接收一个整数数组`arr`和数组的大小`n`作为输入。在内部循环中，`i`从1开始，因为数组的第一个元素被认为是已排序的。`key`变量用于存储当前未排序元素的值，`j`则用来追踪已排序部分的最后一个元素。 `while`循环用于比较`key`和已排序部分的元素，如果`key`小于当前元素，就将当前元素向右移动一位，直到找到`key`的正确位置。最后，`key`被插入到正确的位置，完成一次插入操作。 在`main`函数中，我们定义了一个示例数组`arr`，计算其长度`n`，然后调用`insertionSort`函数对其进行排序。排序完成后，通过`printf`函数打印排序后的数组。 插入排序的时间复杂度在最坏的情况下是O(n²)，当数组已经部分或完全排序时，插入排序可以达到线性时间复杂度O(n)。虽然对于大规模无序数据，插入排序效率较低，但对于小规模或者接近有序的数据，插入排序是非常高效的。 这段C语言代码清晰地展示了插入排序的实现过程，是学习和理解插入排序算法的一个良好起点。在实际应用中，根据具体场景选择合适的排序算法是非常重要的。