C++插入排序怎么实现

C++插入排序是一种比较简单的排序算法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

C++插入排序的实现步骤如下：

1、首先设置一个标志变量j，将要插入的数据元素赋值给j。

2、从有序表中比较元素，如果j小于有序表中的元素，则将有序表中的元素向后移动，直到找到j应该插入的位置。

3、将j插入到有序表中，插入完成后，有序表中新增一个元素。

4、重复步骤1-3，直到所有元素都插入到有序表中，排序完成。

C++插入排序的实现代码如下：

void InsertSort(int a[], int n)
{
    int i, j;
    for(i=1; i0 && a[j-1]>temp; j--)
            a[j] = a[j-1];
        a[j] = temp;
    }
}

上面的代码中，首先外层循环从第二个元素开始，将每一个元素赋值给变量temp，内层循环从temp的右边开始，将大于temp的元素向后移动，直到找到temp应该插入的位置，将temp插入到有序表中，完成一次插入排序，外层循环继续，直到所有元素都插入到有序表中，排序完成。

C++插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)，当记录较少时，插入排序效率比较高。但它的缺点是比较慢，而且当记录数较多时，性能会变得很差。