排序与算法：归并排序

执行效果 归并排序的执行效果是这样的：

呃……看不懂吗？没关系，接着往下看介绍 

算法介绍 归并排序（Merge Sort）是创建在归并操作上的一种有效的排序算法，效率为 O(n log n)。1945 年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。 算法档案 时间复杂度：O(n * logn) 最优时间复杂度：O(n) 平均时间复杂度：O(n * logn) 空间复杂度：O(n) 稳定性：稳定 算法步骤

把 n 个元素看成 n 个长度为 1 的有序子表进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表重复第 2 个步骤直到所有记录归并成一个长度为 n 的有序表为止

算法实现

#include <stdio.h> void merge_sort(int array[], int length); void merge_sort_recursive(int array[], int reg[], int start, int end); void merge_sort_recursive(int array[], int reg[], int start, int end) { if (start >= end) { return; } int k = start; int length = end - start; int mid = (length / 2) + start; int start1 = start, end1 = mid; int start2 = mid + 1, end2 = end; merge_sort_recursive(array, reg, start1, end1); merge_sort_recursive(array, reg, start2, end2); while (start1 <= end1 && start2 <= end2) { reg[k++] = array[zxsq-anti-bbcode-start1] < array[zxsq-anti-bbcode-start2] ? array[start1++] : array[start2++]; } while (start1 <= end1) { reg[k++] = array[start1++]; } while (start2 <= end2) { reg[k++] = array[start2++]; } for (k = start; k <= end; k++) { array[zxsq-anti-bbcode-k] = reg[zxsq-anti-bbcode-k]; } } void merge_sort(int array[], int length) { int reg[zxsq-anti-bbcode-length]; merge_sort_recursive(array, reg, 0, length-1); } int main(void) { int array[] = {73, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109}; int i, length; length = sizeof(array) / sizeof(array[zxsq-anti-bbcode-0]); merge_sort(array, length); printf("排序后的结果是："); for (i = 0; i < length; i++) { printf("%d ", array[zxsq-anti-bbcode-i]); } putchar('\n'); return 0; }

程序实现如下：