排序&哈希&查找.ppt

排序&哈希&查找排序的基本概念(续)直接插入排序过程示例直接插入排序算法直接插入排序算法交换排序起泡排序过程示例起泡排序算法38快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序选择排序简单选择排序过程示例简单选择排序算法归并排序二路归并排序算法二路归并算法哈希哈希解决冲突办法关键码集为{47，7，29，11，16，92，22，8，3}，
设：哈希表表长为m=11；
哈希函数为Hash(key)=keymod11；
拟用线性探测法处理冲突。建哈希表如下：2、链地址法(拉链法）链地址法的静态链表实现二分查找②运算步骤：
(1)low=1,high=11,mid=6，待查范围是[1,11]；
(2)若ST.elem[mid].key<key，说明key[mid+1,high]，
则令：low=mid+1;重算mid＝(low+high)/2；.
(3)若ST.elem[mid].key>key，说明key[low,mid-1]，
则令：high=mid–1;重算mid；
(4)若ST.elem[mid].key=key，说明查找成功，元素序号=mid;
结束条件：（1）查找成功：ST.elem[mid].key=key
（2）查找不成功：high≤low（意即区间长度小于0）练习题