排序算法：简单插入排序

简单插入排序（Insertion Sort）是一种简单直观的排序算法，其基本思想是将待排序的序列分成已排序和未排序两个部分，每次从未排序部分中取出一个元素插入到已排序部分的正确位置，直到所有元素都被插入到已排序部分中，排序完成。

简单插入排序的核心操作是将待排序元素插入到已排序部分中的正确位置。假设当前待插入元素为 a，它应该插入到已排序部分中的位置 j。我们可以从后往前依次比较已排序部分中的元素，如果遇到一个元素 b 满足 b > a，那么就将其往后移动一个位置，直到找到合适的位置为止。这个过程中，我们可以利用数组的特性来减少元素的移动次数。

下面是简单插入排序的C++实现示例代码：

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;
    }
}

在这段代码中，我们先遍历数组，依次将 arr[i] 插入到已排序的部分中。我们将 arr[i] 暂时存储到变量 key 中，然后在内部循环中寻找它应该插入的位置 j，并将已排序部分中的元素往后移动一个位置，直到找到合适的位置为止。最后，我们将 key 插入到正确的位置上，这样就完成了一次插入操作。重复以上操作直到所有元素都被插入到已排序部分中，排序完成。

下面是使用上述函数对一个整型数组进行排序的示例：

int main() {
    int arr[] = { 64, 25, 12, 22, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

该程序的输出结果为：

Sorted array: 11 12 22 25 64

在这里，我们首先定义了一个包含 5 个整型元素的数组 arr，然后使用 insertionSort 函数对该数组进行排序，并输出排序后的结果。

假设现在有一个整型数组arr，长度为n，要对它进行插入排序。

初始数组：[4, 2, 7, 1, 3, 5]

1. 第一轮插入排序，将2插入已经排好序的[4]中，得到[2, 4, 7, 1, 3, 5]

2. 第二轮插入排序，将7插入已经排好序的[2, 4]中，得到[2, 4, 7, 1, 3, 5]

3. 第三轮插入排序，将1插入已经排好序的[2, 4, 7]中，得到[1, 2, 4, 7, 3, 5]

4. 第四轮插入排序，将3插入已经排好序的[1, 2, 4, 7]中，得到[1, 2, 3, 4, 7, 5]

5. 第五轮插入排序，将5插入已经排好序的[1, 2, 3, 4, 7]中，得到[1, 2, 3, 4, 5, 7]

最终排序结果为：[1, 2, 3, 4, 5, 7]