排序&哈希&查找

《排序&哈希&查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、排序&哈希&查找排序的基本概念(续)内部排序外部排序插入排序（直插排序、二分排序、希尔排序）交换排序（冒泡排序、快速排序）选择排序（直选排序、树型排序、堆排序）归并排序（二路归并排序、多路归并排序）分配排序（多关键字排序、基数排序）多路平衡归并排序置换－选择排序最佳归并树排序直接插入排序过程示例初始关键字序列3412492831525149*123456780监视哨i=21234492831525149*12i=31234492831525149*49i=41228344931525149*28i=51228313449525149*31i=61

2、228313449525149*52i=71228313449515249*51i=8122831344949*515249*直接插入排序算法数据结构定义#defineMAXSIZE20typedefintKeytype;//定义关键字类型为整型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其他数据项}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵intlength;//顺序表长度}SqList;//顺序表类型直接插

3、入排序算法以顺序表作为存储结构的直接插入排序算法voidInsertSort(SqList&L){for(i=2;i<=L.ength;i++)if(L.r[i].key

4、ey

5、次数为:0最坏情况下(逆序)元素的比较次数:(n+2)(n-1)/2元素的移动次数为：(n+4)(n-1)/2交换排序1.起泡排序起泡排序(BubbleSorting)的基本思想是：将相邻位置的关键字进行比较，若为逆序则交换之。第i趟排序过程为从L.r[1]至L.r[n-i+1]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序过程终止的条件是“在一趟排序过程中没有进行过交换记录的操作”起泡排序过程示例初始关键字序列：4938659776132749*123

6、4567838496576132749*97第一趟排序后：384965132749*7697第二趟排序后：3849132749*657697第三趟排序后：3813274949*657697第四趟排序后：1327384949*657697第五趟排序后：1327384949*657697第六趟排序后：起泡排序算法以顺序表作为存储结构的起泡排序算法voidBubbleSort(SqList&L){for(i=2;i<=L.ength;i++)if(L.r[i].key

7、;for(j=i-2;L.r[0].key

8、.r[0];}//for}//ifchange=FALSE;for(j=1;j