else {r1[k] = r[j]; j++; k++;} while(i <= m) /*有序表剩余部分处理*/ {r1[k] = r[i]; i++; k++;} while(j <= high) //有序表剩余部分处理 {r1[k] = r[j]; j++; k++;} for(i = low, k = 0; i <= high; i++, k++)/*缓冲向量r1复制到原来的r中*/ r[i] = r1[k]; }
void merge_one(RECNODE *r, int lenth, int n) {/*二路归并中的\一趟归并\算法*/ int i = 0; while(i + 2 * lenth - 1 < n) {merge(r, i, i + lenth - 1, i + 2 * lenth - 1);/*两子序列长度相等的*/ i = i + 2 * lenth;} /*情况下调用merge*/ if(i + lenth - 1 < n - 1) merge(r, i, i + lenth - 1, n - 1); /*序列中的余留部分处理*/ }
void mergesort(RECNODE *r, int n) {/*二路归并排序算法*/ int lenth = 1; /*有序子序列长度初始值 = 1*/ while(lenth < n) {merge_one(r, lenth, n); /*调用\一趟归并\的算法*/ lenth = 2 * lenth;} /*有序子序列长度加倍*/ }
void main() { RECNODE a[MAXSIZE]; int len, b, j, k; int loop = 1; while (loop) { printf(\排序综合练习\\n\\n\ printf(\退出\\n\ printf(\直接插入排序\\n\ printf(\简单交换(冒泡)排序\\n\ printf(\快速排序\\n\ printf(\简单选择排序\\n\ printf(\堆排序\\n\ printf(\二路归并排序\\n\ printf(\请选择项号 ： \ scanf(\ printf(\ if(b >= 0 && b <= 6) switch(b) { case 0: loop = 0; break; case 1: len = createList(a); frontdisplayList(a,len); insertsort(a,len); reardisplayList(a,len); break; case 2: len = createList(a); frontdisplayList(a,len); bublesort(a, len);
- 24 -
reardisplayList(a,len); break;
case 3: len = createList(a); frontdisplayList(a,len); quicksort(a, 1, len); reardisplayList(a,len); break;
case 4: len = createList(a); frontdisplayList(a,len); selesort(a, len); reardisplayList(a,len); break;
case 5: len = createList(a); frontdisplayList(a,len); heapsort(a, len); reardisplayList(a,len); break; case 6:
printf(\输入待排序数据(整数，以空格隔开，0 结束) : \scanf(\
while(j != 0) { k++; a[k-1].key = j; scanf(\ len = k;
printf(\排序前 : \
for (j = 0; j < len; j++) printf(\ printf(\ mergesort(a, len);
printf(\排序后 : \
for (j = 0; j < len; j++) printf(\ printf(\ break; } printf(\结束此练习吗? (0 -- 结束 1 -- 继续) : \ scanf(\ printf(\ } }
六、注意事项
1、mid的变化。
2、一趟快速排序如何产生了两个独立的待排子序列。 2、堆排序中如何生成堆顶元素。 七、思考题
1、在用拉链法解决冲突的散列表上如何插入元素？
- 25 -