直接插入排序算法：C语言实现直接插入排序算法

直接插入排序是一种基础且常用的排序算法，其工作原理可以形象地比喻为打扑克牌时将新拿到的牌插入到已排序好的牌堆中的过程。在计算机科学中，这个过程通过编程语言来实现，C语言是其中一种常用的语言，以其简洁明了的语法特性，非常适合用来演示这种算法。 直接插入排序的基本步骤如下： 1. **初始状态**：数组分为已排序部分（左）和未排序部分（右）。一开始，已排序部分只有一个元素，即数组的第一个元素。 2. **比较与交换**：从未排序部分取出一个元素，与已排序部分的最后一个元素进行比较。如果未排序元素较小，则将两者位置互换，将未排序元素“插入”到已排序部分的正确位置。 3. **重复操作**：继续取出未排序部分的下一个元素，与已排序部分的倒数第二个元素进行比较，如果需要则交换位置。这个过程一直持续到所有元素都插入到已排序部分为止。 4. **结束**：当所有元素都在已排序部分时，排序完成。 在C语言中，实现直接插入排序的代码通常包括以下几个关键部分： - 定义数组：C语言中，可以使用`int arr[N]`来定义一个整数数组，其中N是数组的大小。 - 循环结构：使用`for`循环遍历数组，从第二个元素开始。 - 内部嵌套循环：对于每个未排序的元素，使用`while`循环找到它在已排序部分的正确位置，并将所有大于它的元素向右移动一位。 - 插入操作：将未排序元素放到已排序部分的正确位置，通常使用`swap`函数交换两个元素的位置。 以下是一个简化的C语言实现示例： ```c #include <stdio.h> void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void insertionSort(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; } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); } 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; } ``` 这段代码首先定义了一个`swap`函数用于交换两个元素，然后`insertionSort`函数实现了直接插入排序的核心逻辑。最后的`main`函数创建了一个测试数组，调用排序函数并打印出排序后的结果。 直接插入排序的时间复杂度为O(n^2)，在处理大数据量或部分有序的数组时效率较低，但在小规模数据或者数据基本有序的情况下，性能表现良好。由于其简单直观，它是许多其他高级排序算法（如希尔排序）的基础。在学习排序算法时，理解和掌握直接插入排序是非常重要的一步。