工具人:哨兵
思路:往后挪动元素,找位置插队
代码实现:
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