2、pe;typedefElemTypelisttp[MAXSIZE]；§10-2插入排序一、直接插入排序：思路:通过不断的将某记录插入到一个已经有序的表中来实现。有一组关键字{49，38，76，27，49};i=2(49)38,76,27,49┏━┛i=3(38,49),76,27,49i=4(38,49,76),27,49┏━━━━━┛i=5(27,38,49,76),49┏━┛end.(27,38,49,49,76)-直接插入排序算法voidstraisort(listtpr);{for(i=2;i<=n;i++){r[0]=r[i]
3、;/*设置监视哨*/j=i-1;k=r[i].key;while(r[j].key>k)/*大值的记录后移*/{r[j+1]=r[j];j--;}r[j+1]=r[0];/*插入位置*/}}/*straisort*/-直接插入排序算法算法分析：排序是稳定的;原来：（49，38，76，27，49）排序后：(27,38,49,49,76)排时间复杂度为：T(n)=O(n2)§10-3交换排序一、起泡排序(由小到大）思路:第1趟aj与aj+1比,较大数=>aj+1(j=1,...n-1）第2趟aj与aj+1比,较大数=>aj+1(j=1,..
4、.n-2)第n-1趟a1与a2比,较大数=>a2(j=1,n-(n-1))一、起泡排序(由小到大）算法描述：（1）voidbuble_sort(listtpr){for(i=1;i<=n-1;i++)/*共计n-1趟*/for(j=1;j<=n-i;j++)if(r[j].key>r[j+1].key){x=r[j];r[j]=r[j+1]r[j+1]=x;}}/*bubble_sort*/起泡排序实例图示：排序表长度n=8初始状态第1趟后第2趟后第3趟后第4趟后第5趟后第6趟后49383838381313384949491327276
5、56565132738389776132749494976132749494949132749656565652749767676767649979797979797起泡排序改进方法（2）Voidbubble_sort2(listtpr){i=1;do{bool=1;for(j=1;j<=n-i;j++)if(r[j].key>r[j+1].key){x=r[j];r[j]=r[j+1];r[j+1]=x;bool=0;}i++;}while(bool==0&&i<=n-1);}/*bubble_sort2*/当某一趟仅有比较而无数据交
6、换，表明序列已经有序。可以结束排序过程。起泡排序算法分析时间复杂度：一般情况下：T(n)=0(n2)当原始序列有序是：T(n)=0(n)起泡排序算法是稳定的。排序算法小结:直接插入排序稳定，时间复杂度为：0(n2)交换排序的起泡排序是稳定，一般，时间复杂度为：0(n2)当原始序列有序，时间复杂度为：0(n)上一讲内容回顾排序基本概念插入排序直接插入排序稳定T(n)=O(n2)希尔排序不稳定T(n)=n1.3交换排序起泡排序稳定T(n)=O(n2)原表有序时T(n)=O(n)本讲内容交换排序起泡排序稳定T(n)=O(n2)快速排序不稳定T
7、(n)=O(n.log2n)选择排序简单选择排序稳定T(n)=O(n2)堆排序不稳定T(n)=O(n.log2n)§10.3交换排序二、霍尔快速排序存储结构：顺序存储结构,常称为表。#defineMAXSIZE30;/*表中记录的个数*/Typedefstruct{intkey；/*或其他类型*/.../*其他次关键字域*/}ElemType;typedefElemTypelisttp[MAXSIZE]；1.霍尔快速排序思路（1）以r[1].key为枢轴，经过比较将:r[1]，r[2],………,r[n]分成两个子表：[.....ki..
8、...]k1[.....kj.....],左子表关键字=k11.霍尔快速排序思路每一趟具体做法：先以第一个关键字为枢轴。设置左右两个指针分别指向表的两端，i=1,j=n。从表的右端开始比
