C++插入排序算法实例

没事喜欢看看数据结构和算法，增加自己对数据结构和算法的认识，同时也增加自己的编程基本功。插入排序是排序中比较常见的一种，理解起来非常简单。现在比如有以下数据需要进行排序：10 3 8 0 6 9 2当使用插入排序进行升序排序时，排序的步骤是这样的：10 3 8 0 6 9 2 // 取元素3，去和10进行对比3 10 8 0 6 9 2 // 由于10比3大，将10向后移动，将3放置在原来10的位置；再取8与前一个元素10进行对比3 8 10 0 6 9 2 // 同理移动10；然后8再和3比，8大于3，所以不再移动；如此重复下去……插入排序的最差时间复杂度为O(n^2)。同时，该算法不需要开辟额外的空间，都是在原空间上进行移动操作。