算法设计与分析课后习题

.

*/

for (i = 0; i <= (right - left); i++){ arr[left + i] = tmpArr[i]; }

free(tmpArr); }

void DatasetNatureMerge(type_t arr[], int n){ int *tmpArr; int i, k = 0; int s = 1;

int group; /*记录分割组的数目*/ int count = 0;

int left, between, right; int arrLen = n; /*

*tmpArr 用来存储数组元素下标分割点 */

tmpArr = (int*)malloc(n * sizeof(int)); if (!tmpArr){ return; }

memset(tmpArr, -1, (n * sizeof(int))); /*

* 存储首分割点 */

tmpArr[k++] = 0;

for (i = 0; i < arrLen - 1; i++){ if (arr[i] > arr[i+1]){ tmpArr[k] = i; k++; } } /*

* 存储尾分割点 */

tmpArr[k] = n - 1; /*

* k 和 group 分别记录分割数组长度 */

group = k;

#if DEBUG

printf(\数组分割点为:\\n\

Word 文档

.

printf(\

for (i = 0; i <= group; i++){ if (i == 10){

printf(\ }

printf(\ }

printf(\#endif s = 1;

for (group; group != 1; group = ((group % 2 == 0) ? (group / 2) : (group / 2 + 1))){ /*

*合并次数，例如：5组合并需要两次，4组合并也需要两次 */

count = group / 2; /*

*进行第一次合并 */

left = 0;

between = s; right = 2 * s; if (right > k){ right = k; }

DatasetMerge(arr, tmpArr[left], tmpArr[between], tmpArr[right]); /*

* 进行生下来的合并 */

for (i = 1; i < count; i++){ left = right;

between = left + s; right = between + s; if (right > k){ right = k; }

DatasetMerge(arr, tmpArr[left + 1], tmpArr[between], tmpArr[right]); }

s += s; }

free(tmpArr); }

(2). 链表实现法： #if LINK

typedef struct node *link_t;

Word 文档

.

struct node { int item; link_t next; };

link_t LinkMerge(link_t a, link_t b){ link_t c, head;

c = head = malloc(sizeof(struct node));

while ((a != NULL) && (b != NULL)){ if (a->item < b->item){ c->next = a; c = a;

a = a->next; }else{

c->next = b; c = b;

b = b->next; } }

c->next = (a == NULL) ? b : a; return head->next; }

link_t LinkNuturalMergesort(link_t t){ link_t a, b; link_t u, v;

QUEUE Q;

if (t == NULL || t->next == NULL) return t;

for (u = t; t != NULL; t = u){

while (u && u->next && u->item <= u->next->item){ u = u->next; }

v = u;

u = u->next;

v->next = NULL; Q.ENQUEUE(t); }

Q.DEQUEUE(t); while (!Q.EMPTY()){ Q.ENQUEUE(t);

Word 文档

.

Q.DEQUEUE(a); Q.DEQUEUE(b); t = LinkMerge(a, b); } return t; }

#endif

Word 文档