学步园

/* 7-13-11-20-22.33.c -- 第七章第十三题 */<br /> #include <stdio.h><br /> #include <stdlib.h></p> <p>#define SIZE 8</p> <p>int main (void) ;<br /> void print_array (const int * const array, const int size) ;<br /> void merge_sort (int * const array, const int size) ;<br /> void merge_sort_entity (int * const array, int * const temp, const int left_position, const int right_position) ;<br /> void merge (int * const array, int * const temp, int left_position, int right_position, int right_end) ;</p> <p>int main (void)<br /> {<br /> int array[SIZE] = {3, 1, 4, 1, 5, 9, 2, 6} ;<br /> int size = SIZE ;</p> <p> print_array (array, size) ;<br /> merge_sort (array, size) ;<br /> print_array (array, size) ;</p> <p> return 0 ;<br /> }</p> <p>void print_array (const int * const array, const int size)<br /> {<br /> int i ;</p> <p> for (i = 0; i < size; i++)<br /> printf ("%d ", array[i]) ;<br /> putchar ('/n') ;<br /> }</p> <p>void merge_sort (int * const array, const int size)<br /> {<br /> int * temp ;</p> <p> temp = (int *) malloc (sizeof (int) * size) ;<br /> if (temp)<br /> {<br /> merge_sort_entity (array, temp, 0, size - 1) ;<br /> free (temp) ;<br /> }<br /> else<br /> puts ("Out of space.") ;<br /> }</p> <p>void merge_sort_entity (int * const array, int * const temp, const int left_position, const int right_position)<br /> {<br /> int center ;</p> <p> if (left_position < right_position)<br /> {<br /> center = (left_position + right_position) / 2 ;<br /> merge_sort_entity (array, temp, left_position, center) ;<br /> merge_sort_entity (array, temp, center + 1, right_position) ;<br /> merge (array, temp, left_position, center + 1, right_position) ;<br /> }<br /> }</p> <p>/* left_position = start of left half, right_position = start of right half */<br /> void merge (int * const array, int * const temp, int left_position, int right_position, int right_end)<br /> {<br /> int i, left_end, count, temp_position ;</p> <p> left_end = right_position - 1 ;<br /> temp_position = left_position ;<br /> count = right_end - left_position + 1 ;</p> <p> /* main loop */<br /> while (left_position <= left_end && right_position <= right_end)<br /> {<br /> if (array[left_position] <= array[right_position])<br /> temp[temp_position++] = array[left_position++] ;<br /> else<br /> temp[temp_position++] = array[right_position++] ;<br /> }<br /> while (left_position <= left_end)<br /> temp[temp_position++] = array[left_position++] ;<br /> while (right_position <= right_end)<br /> temp[temp_position++] = array[right_position++] ;<br /> for (i = 0; i < count; i++, right_end--)<br /> array[right_end] = temp[right_end] ;<br /> }   接触排序第四天,照着书上的代码写出的递归实现.思路基本理解,贴出来.