6-2 直接插入排序

### 关于直接插入排序的算法实现与解释

#### 插入排序的概念
插入排序是一种简单直观的排序方法，适用于较小规模的数据集。该算法通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入[^1]。

#### 工作机制解析
假设存在一个数组`arr[]`，长度为`n`。插入排序的工作过程如下：

- 将第一个元素视为已经排序的部分；
- 对于每一个新元素（即第i个元素），将其插入到前面已经排好序的子数组中的适当位置上；
- 这样做会使得每次迭代之后，前i个元素总是保持有序状态；

具体来说，当处理第i个元素时，如果这个数小于它的前驱，则继续比较更早之前的数值直到遇到不大于当前考察对象的位置为止，并在此处放置待插入项。

#### C++代码示例
以下是使用C++编写的直接插入排序函数的具体实现:

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) { // 遍历整个列表
        key = arr[i];          // 当前要插入的值设为key
        j = i - 1;

        /* 向左移动较大的元素 */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;      // 找到了合适的位置就插入
    }
}

这段程序实现了上述描述的过程：遍历输入数组，逐步将每个元素按正确顺序放入之前部分形成的有序区段内[^2]。