插入排序法

插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。这种算法对大数据集的效率较低，但对小数据集或者部分有序的数据，插入排序表现良好。在C语言中实现插入排序，通常涉及以下几个关键步骤： 1. **初始化**：我们需要一个函数来执行插入排序，这个函数通常接收一个数组和数组的大小作为参数。在函数内部，我们设置一个指针`i`，从1开始，因为它表示第一个未排序的元素。 2. **主循环**：外层循环通常是一个for循环，从`i = 1`开始，到`i < n`结束，其中`n`是数组的长度。这个循环用于遍历所有未排序的元素。 3. **内层循环**：在每次外层循环中，我们会有一个`j`指针，从`i - 1`开始，向后移动，直到找到正确的位置将`arr[i]`插入。内层循环是这样的：`while (j >= 0 && arr[j] > arr[j + 1])`，当满足条件时，交换`arr[j]`和`arr[j + 1]`。 4. **插入元素**：一旦找到正确的位置，我们将`arr[i]`插入到`arr[j + 1]`的位置。这一步不需要实际的交换操作，因为在内层循环结束后，`arr[i]`已经处在了正确的位置。 5. **递增指针**：在外层循环结束后，`i`增加1，然后继续处理下一个未排序的元素。 6. **结束条件**：当`i`达到`n`时，所有元素都已经排序，排序过程结束。 在C语言中，这个算法可以被实现为以下代码片段（以`INSERTSO.C`为例）： ```c #include <stdio.h> void insertionSort(int arr[], int n) { int i, j, key; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } /* A utility function to print array of size n*/ void printArray(int arr[], int n) { int i; for (i=0; i<n; i++) printf("%d ", arr[i]); printf("\n"); } /* Driver program to test insertion sort*/ int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr)/sizeof(arr[0]); insertionSort(arr, n); printf("Sorted array: \n"); printArray(arr, n); return 0; } ``` 这段代码首先定义了一个`insertionSort`函数，然后在`main`函数中调用该函数对一个整数数组进行排序，并打印排序后的结果。`printArray`函数用于输出数组的内容。 插入排序的时间复杂度为O(n²)，空间复杂度为O(1)，因为它是原地排序算法，不需要额外的存储空间。尽管它不是最高效的排序算法，但对于小规模数据或部分有序的数据，插入排序仍然是一种实用且高效的解决方案。在实际应用中，根据具体需求和数据特性，可能会选择更适合的排序算法，例如快速排序、归并排序等。