7，冲突处理采用线性探测法。
解：H(15)=15 MOD 7=1 H(14)=14 MOD 7=0
H(28)=28 MOD 7=0 冲突 H1(28)=1 又冲突H2(28)=2 H(26)=26 MOD 7=5 H(56)=56 MOD 7=0 冲突 H1(56)=1 又冲突 H2(56)=2 又冲突 H3(56)=3
H(23)=23 MOD 7=2 冲突 H1(23)=3 又冲突 H3(23)=4
各种散列函数所构造的散列表的ASL如下：
17、排序的稳定性
若记录序列中有两个或两个以上关键字相等的记录： Ki =Kj(i≠j，i, j=1, 2, … n)，且在排序前Ri先于Rj(i 排序的分类 待排序的记录数量不同，排序过程中涉及的存储器的不同，有不同的排序分类。 ① 待排序的记录数不太多：所有的记录都能存放在内存中进行排序，称为内部排序； ② 待排序的记录数太多：所有的记录不可能存放在内存中， 排序过程中必须在内、外存之间进行数据交换，这样的排序称为外部排序。 18、插入排序采用的是以 “玩桥牌者”的方法为基础的。即在考察记录Ri之前，设以前的所有记录R1, R2 ,…., Ri-1已排好序，然后将Ri插入到已排好序的诸记录的适当位置。 ============================================================================ 最基本的插入排序是直接插入排序(Straight Insertion Sort) 。 ⑴ 最好情况：若待排序记录按关键字从小到大排列(正序)，算法中的内循环无须执行，则一趟排序时：关键字比较次数1次，记录移动次数2次 ⑵ 最坏情况：若待排序记录按关键字从大到小排列(逆序)，则一趟排序时：算法中的内循环体执行i-1，关键字比较次数i次，记录移动次数i+1。 一般地，认为待排序的记录可能出现的各种排列的概率相同，则取以上两种情况的平均值，作为排序的关键字比较次数和记录移动次数，约为n2/4，则复杂度为O(n2) 。 算法实现 void straight_insert_sort(Sqlist *L) { int i, j ; for (i=2; i<=L->length; i++) { L->R[0]=L->R[i]; j=i-1; /* 设置哨兵 */ while( LT(L->R[0].key, L->R[j].key) ) { L->R[j+1]=L->R[j]; j--; } /* 查找插入位置 */ L->R[j+1]=L->R[0]; /* 插入到相应位置 */ } } =============================================================================== 折半插入排序 当将待排序的记录R[i] 插入到已排好序的记录子表R[1…i-1]中时，由于R1, R2 ,…, Ri-1已排好序，则查找插入位置可以用“折半查找”实现，则直接插入排序就变成为折半插入排序。 从时间上比较，折半插入排序仅仅减少了关键字的比较次数，却没有减少记录的移动次数，故时间复杂度仍然为O(n2) 。 排序示例： 设有一组关键字30, 13, 70, 85, 39, 42, 6, 20，采用折半插入排序方法排序的过程 ⑴ 算法实现 void Binary_insert_sort(Sqlist *L) { int i, j, low, high, mid ; for (i=2; i<=L->length; i++) { L->R[0]=L->R[i]; /* 设置哨兵 */ low=1 ; high=i-1 ; while (low<=high) { if ( LT(L->R[0].key, L->R[mid].key) ) high=mid-1 ; else low=mid+1 ; } /* 查找插入位置 */ for (j=i-1; j>=high+1; j--) L->R[j+1]=L->R[j]; L->R[high+1]=L->R[0]; /* 插入到相应位置 */ }} ============================================================================== 2-路插入排序 排序示例：设有初始关键字集合{49, 38, 65, 13, 97, 27, 76} ，采用2-路插入排序的过程 例：设有关键字集合{49, 38, 65, 97, 76, 13, 27, 49} ，采用表插入排序的过程 =============================================================================== 希尔排序(Shell Sort，又称缩小增量法)是一种分组插入排序方法。 排序示例 设有10个待排序的记录，关键字分别为9, 13, 8, 2, 5, 13, 7, 1, 15, 11，增量序列是5, 3, 1，希尔排序的过程： 算法实现 先给出一趟希尔排序的算法，类似直接插入排序。 void shell_pass(Sqlist *L, int d) /* 对顺序表L进行一趟希尔排序, 增量为d */ { int j, k ; for (j=d+1; j<=L->length; j++) { L->R[0]=L->R[j] ; /* 设置监视哨兵 */ k=j-d ; while (k>0&<(L->R[0].key, L->R[k].key) ) {L->R[k+d]=L->R[k] ; k=k-d ; } L->R[k+j]=L->R[0] ; } } void shell_sort(Sqlist *L, int dk[], int t) /* 按增量序列dk[0 … t-1],对顺序表L进行希尔排序 */ { int m ; for (m=0; m<=t; m++) shll_pass(L, dk[m]) ; } ===============================================================================冒泡排序 排序示例 ： 设有9个待排序的记录，关键字分别为23, 38, 22, 45, 23, 67, 31, 15, 41，冒泡排序的过程： void Bubble_Sort(Sqlist *L) { int j ,k , flag ; for (j=0; j for (k=1; k<=L->length-j; k++) /* 一趟排序 */ if (LT(L->R[k+1].key, L->R[k].key ) ) { flag=FALSE ; L->R[0]=L->R[k] ; L->R[k]=L->R[k+1] ; L->R[k+1]=L->R[0] ; } if (flag==TRUE) break ; } } 算法分析: 时间复杂度: 最好情况(正序)：比较次数：n-1；移动次数：0； 最坏情况(逆序)： 故时间复杂度：T(n)=O(n2) 空间复杂度：S(n)=O(1) ===============================================================================快速排序的平均时间复杂度是：T(n)=O(n㏒2n) 从所需要的附加空间来看，快速排序算法是递归调用，系统内用堆栈保存递归参数，当每次划分比较均匀时，栈的最大深度为[㏒2n]+1 。 ∴ 快速排序的空间复杂度是：S(n)=O(㏒2n) 从排序的稳定性来看，快速排序是不稳定的。 一趟排序示例 设有6个待排序的记录，关键字分别为29, 38, 22, 45, 23, 67，一趟快速排序的过程