C语言归并排序(合并排序)算法及代码.docxVIP

C C 语言归并排序(合并排序)算法及代码 归并排序也称合并排序，其算法思想是将待排序序列分 为两部分，依次对分得的两个部分再次使用归并排序，之后 再对其进行合并。仅从算法思想上了解归并排序会觉得很抽 象，接下来就以对序列 A[0], A[l]…,A[n-1]进行升序排列来进 行讲解，在此采用自顶向下的实现方法，操作步骤如下。 ( 1 )将所要进行的排序序列分为左右两个部分，如果要进行 排序的序列的起始元素下标为 first ，最后一个元素的下标为 last，那么左右两部分之间的临界点下标 mid=(first+last)/2 ， 这两部分分别是 A[first … mid] 和 A[mid+1 … last]。 (2)将上面所分得的两部分序列继续按照步骤 (1)继续进行划 分，直到划分的区间长度为1 分，直到划分的区间长度为 1。 (3)将划分结束后的序列进行归并排序，排序方法为对所分 的n个子序列进行两两合并，得到n/2或n/2+l个含有两个元 素的子序列，再对得到的子序列进行合并，直至得到一个长 度为 n 的有序序列为止。下面通过一段代码来看如何实现归 并排序。 #include #include #define N 7 void merge(int arr[], int low, int mid, int high){ int i, k; int *tmp = (int *)malloc((high-low+1)*sizeof(int)); //申请空间，使其大 小为两个 int left_low = low; int left_high = mid; int right_low = mid + 1; int right_high = high; for(k=0; left_lowleft_high right_lowright_high; k++){ // 比较两个 指针所指向的元素 if(arr[left_low]arr[right_low]){ tmp[k] = arr[left_low++]; }else{ tmp[k] = arr[right_low++]; } } if(left_low left_high){ // 若第一个序列有剩余，直接复制出 来粘到合并序列尾 //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int)); for(i=left_low;ileft_high;i++) tmp[k++] = arr[i]; } if(right_low right_high){ //若第二个序列有剩余， 直接复制 出来粘到合并序列尾 //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int)); for(i=right_low; iright_high; i++) tmp[k++] = arr[i]; } for(i=0; ihigh-low+1; i++) arr[low+i] = tmp[i]; free(tmp); return; } void merge_sort(int arr[], unsigned int first, unsigned int last){ int mid = 0; if(firstlast){ mid = (first+last)/2; /* 注 意防止溢出 */ /*mid = first/2 + last/2;*/ //mid = (first last) + ((first 八 last) 1); merge_sort(arr, first, mid); merge_sort(arr, mid+1,last); merge(arr,first,mid,last); } return; } int main(){ int i; int a[N]={32,12,56,78,76,45,36}; printf ( 排序前 \n); merge_sort(a,0,N-1); // merge_sort(a,0,N-1); // 排序 printf (\n 排序后 \n); for(i=0;iN;i++) printf(%d\t,a[i]); printf(\n);system(pause); return printf(%d\t,a[i]); printf(\n); system(pause); return 0; } #include #include #define N 7void merge(int arr[], int low, int mid, int high){ int i, k; int *tmp =