前言：数据结构概览之第八章排序整理

　　插入排序

思想：

从待排关键字序列中的第二个关键字开始一直到最后的一个关键字结束，不论待排序的关键字是否有序，都要执行 len -1 次排序；

把当前的关键字currentElem用哨兵记录；

比较哨兵和currentElem之前的关键字的大小，并且适当的进行后移的操作；

到最后找到哨兵的位置，进行插入。

代码如下：

1 /** 2  插入排序 3  4  @param R 数组 5  @param len 数组中元素个数 6  */ 7 void insertSort(int R[],int len); 8  9 void insertSort(int R[],int len){10     int i,j;11     int temp;12     for(i = 1;i < len;i ++){13         j = i - 1;14         temp = R[i];15         while (j >= 0 && temp < R[j]) {16             R[j+1] = R[j];17             --j;18         }19         R[j+1] = temp;20     }21 }

测试函数以及输出：

1 int R[] = {
    1,2,-2,3,4,-3,0};2         insertSort(R, sizeof(R)/sizeof(int));3         for (int i = 0; i < 7; i ++) {4             printf("%d\t",R[i]);5         }6 //        -3    -2    0    1    2    3    4    Program ended with exit code: 0

和课本不同之处：记得之前的课本上是用的一个"哨兵"来记录这个当前待排序的关键字，这里用temp的话原理是一样的；

 

参考资料：

数据结构高分笔记

数据结构严蔚敏版配套PPT

 

OS交流群欢迎你的加入！

群二维码：

先写到这么多

如有问题，敬请指正；

如需转载，请注明出处，谢谢!