数据结构本章有关的概念介绍：1、排序的定义（基于关键词的比较）2、排序的分类（分类的依据）3、稳定性（基于关键词的计算）4、排序的存储结构（1）比较：对于关键词key5、排序涉及的操作（2）移动：对于整条记录一、插入排序1、直接插入排序<1>、排序策略：在有序表中的恰当处插入一个元素，并且保持该表的有序性。（即：当插入第i个元素时，前i-1个元素已经排列有序）这里，r[0]的作用是监视哨。（1）监视表头（结束）；（2）中间变量单元使用。<2>、直接插入排序示例(1)对{49,38,65,97,76,13,27,49}进行直接插入排序：（i=12345678）[初始关键字]：(49)38659776132749R[0]第1趟i=2(3849)65977613274938第2趟i=3(384965)977613274965第3趟i=4(38496597）7613274997第4趟i=5(3849657697）13274976第5趟i=6(133849657697）274913第6趟i=7(13273849657697）4927第7趟i=8(1327384949657697）49当i=1时，只有1个数据，不需要比较。每一趟排序的序列将增加一个元素。如果序列中有n元素，那么最多进行n-1趟即可。直接插入排序思想：进行第i趟排序时，将R[i]的关键字Ki存放在监视哨R[0]中，将R[0]中的关键字Ki与R[i-1]、R[i-2]……(与前面已经排好的关键字进行比较)，同时将大于Ki的关键字后移直至找到第一个不大于关键字Ki的关键字Kj，（2）以数组存储{49,38,65,97,76,13,27,49}，并进行插入排序。i=2（49与38比较38比49小，49往后移动）（直至比较到监视哨或比38小的数为止）i=3（同理，将R[3]内的KEY放入R[0]内，且分别与前面的KEY做比较，直至比较到监视哨或比65少的数为止）<3>直接插入排序算法voidInsertSort(){//对记录序列r[1]..r[n]作直接插入排序for(i=2;i<=n;i++)//从第二个元素开始比较{r[0]=r[i];//r[0]为监视哨j=i-1;while(r[0].key<r[j].key){r[j+1]=r[j];j--;}//记录后移,边移动边找插入位置r[j+1]=r[0]；//插入到正确位置}}//InsertSort<4>算法分析（1）时间分析:(用移动和比较次数可作为衡量时间复杂性的标准)正序时：比较次数∑1=n-1,移动次数0逆序时：比较次数∑i,移动次数∑(i+1)所以时间复杂度T(n)=O(n2)（2）空间分析:在移动时不需要另增加存储空间，所以空间复杂度S(n)=O(1)（3）稳定性由于是在线性表中逐一比较，所以该算法是稳定的。<5>、适用范围（1）n较小时（2）局部有序时。<6>、进一步思考（1）在有序表r[1]..r[i-1]中能否进行折半（二分）查找？（2）能否以链表为存储结构，实现该算法？（3）排序过程中能否将后移的间距加大些？若加以改进，算法的效率是否可以提高。2、希尔（shell）排序希尔排序（Shell’sSort）又叫“缩小增量排序”，是对直接插入排序所作的改进。<1>、排序策略:先将整个待排序的记录序列分割成为若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。<2>、希尔（shell）排序示例:<3>、算法设计voidShellsort(){//对记录序列r[1]..r[n]作shell排序,增量是dd=n/2;//取d1=n/2,di=di-1/2(采用分组排序)while(d>=1){for(i=d+1;i<=n;i++){r[0]=r[i];j=i-d;//r[0]是暂存单元while(j>0)&&(r[0].key<r[j]key)){r[j+d]=r[j];//记录后移，查找插入位置j=j-d;}r[j+d]=r[0];//插入}d=d/2;//取di=di-1/2}}二、交换排序第三趟排序<3>、起泡排序算法voidBubbleSort(){//对r[1]..r[n]进行起泡排序，策略：从上至下逐个进行两两比较i=n;do{//进行n-1趟起泡排序或某趟无交换止swap=0;for(j=1;j<i;j++)//第i趟起泡排序if(r[j].key>r[j+1].key){swap=1;//swap=1:表示进行过交换r[0]=r[j];r[