排序--归并排序
原理：归并排序采用分治的思想，将一组数据进行二分，划分次数为nlgn（先分），再从最小区间开始逐级往上进行排序合并（再治），合并操作是一次遍历完成，所以时间复杂度是n，整个算法的时间复杂度为nlgn。此外，归并排序需要额外的空间存储，大小为n。
源代码：用户先录入设定大小个数的元素，元素在一行用空格分隔，然后进行排序，在一行输出结果，元素用空格分隔，可循环实现。
#includevoid merge_sort(int *array, int left, int mid,int right) { int *temp = (int*)malloc(sizeof(int)*(right - left + 1));
/* num用于存储temp数组的下标 */ int num = 0; int left_start = left; int right_start = mid + 1;
/* 对两个区间进行排序，归并入temp数组内 */ while(left_start <= mid && right_start <= right) { if(array[left_start] <= array[right_start]) { temp[num] = array[left_start]; left_start++; num++; } else { temp[num] = array[right_start]; right_start++; num++; } }
/* 当需要合并的两区间个数不一致，将剩余数字直接插入数组 */ while(left_start <= mid) { temp[num++] = array[left_start++]; }
while(right_start <= right) { temp[num++] = array[right_start++]; }
/* 节省空间，将临时数组释放 */ num = 0; while(left <= right) { array[left++] = temp[num++]; } free(temp); }
void split_merge_sort(int *array, int left, int right) { if(left >= right) return; int mid = (left + right)/2;
/* 先分再治 */ split_merge_sort(array, left, mid); split_merge_sort(array, mid + 1, right); merge_sort(array, left, mid, right); }
int main() { while(1) { int num = 0; int i = 0; printf("请输入需要排序的数字的个数\n"); scanf("%d",&num); printf("输入整数大小为：%d\n", num); int array[num]; memset(array, 0, num); if(i < num) { while(scanf("%d",&array[i++])) { if(getchar() == '\n') break; } }
split_merge_sort(array, 0, i); printf("归并排序后的结果为："); for(int j = 0; j < num; j++) { printf("%d ", array[j]); } system("pause"); } return 0; }