c++数据结构----直接插入排序

1：直接插入排序
基本思想：在插入第i（i>1）个记录时，前面的i-1个记录已经好序
2：例子
i代表插入的记录
r[0]的作用暂存单元 监视哨

3.算法思想
（1）
将第一个记录看作是有序表，从第二个记录起依次插入到这个有序表中，直到第n个记录。
自己的理解是：插入排序，插入第i个记录时，要保证前1~i-1的记录是有序的。

for(i=2;i<=n;i++)
{插入第i个记录 ，即第i趟直接插入排序
}
``
（2）
在i-1个记录的r[1]~r[i-1]中插入记录 r[i],首先先顺序查找r[i]的正确位置，然后将r[i]插入到相应的位置

r[0]的两个作用：
1：进入循环前暂存了r[i]的值，使得
```cpp
r[0]=r[i];//待插入的元素赋值给r[0]
j=i-1;//待插入元素的前一个元素
while(r[0]<r[j])//当前一个元素小于待插入的元素
{r[j+1]=r[j];//将前一个元素后移
j--;//前前一个元素再进行比较，一直循环到第一个元素
｝

（3）直接插入排序的算法

void insertSort(int r[] ,int n)
{for(i=2;i<=n;i++)
{r[0]=r[i];
j=i-1;
while(r[0]<r[j])
{r[j+1]=r[j];
j=j-1;
}
r[j+1]=r[0];//?

（4）算法性能分析
1.最好情况（正序)
比较次数：n-1;
移动次数：2（n-1） //？
时间复杂度：O（n)
2.最坏情况
时间复杂度O(n²）

本文地址：https://blog.csdn.net/zsysingapore/article/details/111078127