基本原理
- 设置第一个元素为有序区域，有序区域之后的第一个元素设为“标兵”。
- 反向遍历有序区域，如果“标兵”小于其中的某一元素，则使该元素右移。
- 当“标兵”大于某一元素时，将“标兵”插入该位置（因为是有序区域，“标兵”前面的数据一定是有序排列的）。
- 更新有序区域和“标兵”， 持续遍历。
以下 gif 参考https://blog.csdn.net/L_PPP/article/details/108498581：
第一次遍历效果：
20200924111012410.gif
第二次遍历效果：
20200924111230415.gif
代码实现
#include <iostream>
#include <string>
using namespace std;
int main(){
int array[10] = {1, 9, 5, 7, 3, 6, 2, 8, 4, 0};
int len = sizeof(array) / sizeof(array[0]);
int flag = 0; // 标记
for (int i = 0; i < len; i++)
{
flag = i;
for (int j = i; j > 0; j--)
{
int temp = array[j];
if (array[j] < array[j - 1]) // 有可插入的值
{
array[j] = array[j - 1]; // 数据前移
}
else
{
break;
}
array[j - 1] = temp; // 数据插入
}
}
for (int i = 0; i < len; i++)
{
cout << array[i] << " ";
}
}
image.png
