- 相关推荐
C++插入排序算法实例
插入排序是排序中比较常见的一种，下面小编为大家整理了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，所以不再移动；如此重复下去
……
0 2 3 6 8 9 10
也就是说，我们每一次取一个元素，都要将该元素与之前已经排序好的元素进行比较。
插入排序的最差时间复杂度为O(n^2)。同时，该算法不需要开辟额外的空间，都是在原空间上进行移动操作。
代码实现
复制代码 代码如下:
#include
using namespace std;
void InsertSort(int arr[], int length)
{
int temp;
for (int i = 1; i < length; ++i) // 从数组中的第二个元素开始
{
temp = arr[i]; // 记录当前的元素
int j = i - 1;
while (j >= 0 && temp < arr[j]) // 将当前元素与之前的已经排序好的序列元素进行挨个比较
{A
arr[j + 1] = arr[j]; // 已经排序好的序列整体向后移动
--j;A}
arr[j + 1] = temp; // 插入当前的元素
}
}
int main()
{
int arr[10] = {9, 2, 8, 2, 3, 2, 4, 10, 34, 5};
InsertSort(arr, 10);
for (int i = 0; i < 10; ++i)
{
cout<<arr[i]<<" ";
}
cout<<endl;
return 0;
}
【C++插入排序算法实例】相关文章：
C语言插入排序算法及实例代码07-02
php:树形结构的算法实例10-18
C语言冒泡排序算法实例06-15
C与C++之间相互调用的实例07-07
C语言中实现KMP算法实例08-09
C语言选择排序算法及实例代码07-25
C++实现自底向上的归并排序算法09-09
C#实现协同过滤算法的实例代码06-19
C语言实现归并排序算法实例09-18
PHP中奖概率的抽奖算法程序代码实例08-05