C++插入排序算法详解：原理和示例代码

插入排序是一种常用的排序算法，原理是将一个数据插入到已排序的数据中，使整个数据从小到大排序。C++中的插入排序算法实现如下：

算法步骤

• 从第一个元素开始，该元素可以认为已经被排序
• 取出下一个元素，在已经排序的元素序列中从后向前扫描
• 如果该元素（已排序）大于新元素，将该元素移到下一位置
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
• 将新元素插入到该位置后
• 重复步骤2~5

示例代码

void insertSort(int arr[], int length)
{
    int i, j, temp;
    for (i = 1; i < length; i++)
    {
        temp = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > temp)
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }
}

以上就是C++插入排序的原理和示例代码，它的比较次数和移动次数均与被排序的记录数成正比，但它的性能比选择排序要好的多，因为它只需要比较记录的大小，而不需要移动记录。