第3种排序算法——直接插入排序

直接插入排序的平均时间复杂度为 O(n^2)，因此其适用范围较为有限。

直接插入排序的基本原理如下： 在每一轮处理中，依次取出一个元素，并将其放置到已排序的子序列中的合适位置，直至所有元素均被处理完成。

下面将提供一个动画演示示例：

通过上述分析，我们可以识别出若干优势：

（1） 实现过程较为简便，相较于其他排序方式具有更高的运算效率；
（2） 在数据已大致有序的情况下，其运行效能表现突出；
（3） 排序过程保持稳定，且所需辅助存储资源较少；
（4） 对新增数据具备良好的响应能力，能够迅速完成处理；

借助动画演示，有助于我们更直观地理解以下C++代码的执行逻辑：

    void insertsort (int data[], int n){
    int j, temp;    
    // 外层循环负责依次处理每一个元素（忽略第一个）
    for (int i = 1; i < n; i++){
        j = i;
        // 内层循环负责移动数据直到找到插入的位置