归并排序

#include<stdio.h> #include<stdlib.h> #define N 18 void Merge(int *a,int low,int mid,int high,int *b) {//将一个数组按照从小到大的顺序排序 int i = low; int j = mid + 1; int k = low; while (i <= mid &&j <= high) { if (a[i] <= a[j]) b[k] = a[i++]; else b[k] = a[j++]; k++; } while (i <= mid) b[k++] = a[i++]; while (j <= high) b[k++] = a[j++]; } void M_Sort(int *a,int low,int high,int *res) { int mid; int temp[N]; if (high == low)//如果高坐标和低坐标相等，则直接赋值返回 { res[low] = a[low]; } else { mid = (high + low) / 2; M_Sort(a,low,mid,temp); //递归的时候，首先将数组一直对半分，直到 剩下 一个数据（默认为一个数有序）， M_Sort(a,mid+1,high,temp); //在返回的途中，将数据 按照从小到大的顺序 合在一起， Merge(temp,low,mid,high,res); } } void Merge_Sort(int *a,int len) { M_Sort(a,0,len-1,a); //数组、数组排序的低位、数组排序的高位、结果数组 } int main(void) { int a[] = { 2,3,4,5,6,7,8,9,6,5,6,7,7,9,4,2,3,0 }; int len = sizeof(a) / sizeof(int); Merge_Sort(a,len);//归并排序，传入的是将要排序的数组 for (int i = 0; i < len; i++) printf("%d ",a[i]); printf("\n"); return 0; }

下面是 输出排序过程的结果 的源代码（附结果图）：

#include<stdio.h> #include<stdlib.h> #define N 18//数组的长度 int count = 0; void print(int *a, int len) { for (int i = 0; i < len; i++) printf("%d ", a[i]); printf("\n"); } void Merge(int *a,int low,int mid,int high,int *b) { int i = low; int j = mid + 1; int k = low; while (i <= mid &&j <= high) { if (a[i] <= a[j]) b[k] = a[i++]; else b[k] = a[j++]; k++; } while (i <= mid) b[k++] = a[i++]; while (j <= high) b[k++] = a[j++]; printf("第%d趟:\n ", count++); for (int i = low; i <= high; i++) printf("%d ",a[i]); printf("\n"); } void M_Sort(int *a,int low,int high,int *res) { int mid; int temp[N]; if (high == low) { res[low] = a[low]; } else { mid = (high + low) / 2; M_Sort(a,low,mid,temp); M_Sort(a,mid+1,high,temp); Merge(temp,low,mid,high,res); } } void Merge_Sort(int *a,int len) { M_Sort(a,0,len-1,a); } int main(void) { int a[] = { 2,3,4,5,6,7,8,9,6,5,6,7,7,9,4,2,3,0 }; int len = sizeof(a) / sizeof(int); printf("原始数据:\n"); print(a, len); Merge_Sort(a,len); printf("排序后的数据:\n"); print(a,len); return 0; }