直接插入排序的C语言

直接插入排序是一种简单直观的排序算法，它的工作原理类似于打扑克牌时整理手牌的过程。在C语言中，它的基本步骤如下：

1. **假设有一个待排序的数组**：例如 `int arr[] = {9, 5, 6, 1, 8, 2}`。

2. **从数组的第一个元素开始**（通常索引为0），将当前元素视为已排序部分的最后一个元素。

3. **对于剩余的每个元素**（索引i从1到n-1），进行以下操作：
a. **比较当前元素arr[i]与已排序部分的最后一个元素**，如果arr[i]小于这个元素，则将该元素逐个向右移动一位，腾出位置。
b. **当找到大于或等于arr[i]的元素或到达数组末尾时**，停止移动，将arr[i]插入到适当的位置。

4. **循环结束后**，整个数组就被认为是有序的，因为所有元素都按照升序排列。

以下是C语言中直接插入排序的一个简单示例：

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        // 将大于key的元素向右移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // 插入关键值
    }
}