工具人：哨兵
思路：往后挪动元素，找位置插队
代码实现：
1.排序方法
void InsertSort(int a[],int n){
int i,j,flag; //flag表示哨兵
for(int i=1;i<n;i++){
flag=a[i];
for(j=i;flag<a[j-1];j--){
a[j]=a[j-1]; //往后挪动元素
}
a[j]=flag; //找位置插队
print(i,n,a);
}
}
- 输出方法
void print(int i,int n,int a[]){
printf("第%d趟排序：",i);
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
printf("\n");
}
3.主函数
int main(){
int a[]={37,26,56,32,18,39,78,61};
InsertSort(a,8);
}
4.运行结果
第1趟排序：26 37 56 32 18 39 78 61
第2趟排序：26 37 56 32 18 39 78 61
第3趟排序：26 32 37 56 18 39 78 61
第4趟排序：18 26 32 37 56 39 78 61
第5趟排序：18 26 32 37 39 56 78 61
第6趟排序：18 26 32 37 39 56 78 61
第7趟排序：18 26 32 37 39 56 61 78
