算法基础：排序算法：归并排序

算法思路

• 归并排序在理解上的那点复杂性主要在于其递归方式的分而治之的拆分与合并。归并在汉语中本身就含有合并的意义，实际上更准确的说，应该是拆分合并算法，拆分至单个元素，这样最小力度都是有序的，然后递归的合并就可以在有序的基础上进行了，而有序状况下的合并复杂度是很容易可以做到O(n)的，由于分层是可以达到对数级的效率，所以整体的复杂度为O(nlogn).

算法要点

选择排序的主要要点如下所示：

• 拆分条件：left + 1 < right
• 主函数：主函数里面使用dfs进行深度遍历，按照拆分条件顺次做算中值，根据中值分而治之，根据中值递归调用左半区和右半区（最终拆至left+1==right，即每个里面只含有一个元素），然后进行合并。
• 合并函数：O(n)的复杂度体现在从left循环至right的循环，使用两个下标分别控制左半端数组和右半端数组的移动，设定下标最大元素之后的元素保存一个较大的值，这样循环可以写的简单一些，只要一个简单的比较就可以了。
• 稳定性：使用left[i] <= right[i]来进行判断，优先使用左端部分，即可保证归并算法的稳定性。当然一个不小心就很容易将本来是稳定的算法变成不稳定的算法，虽然对结果的输出看起来没有影响。

模拟实现

void merge(int* arr, int num, int left, int mid, int right) { int left_length = mid - left; int right_length = right - mid; for (int i=0; i<left_length; i++) left_array[i] = arr[left+i]; for (int i=0; i<right_length; i++) right_array[i] = arr[mid+i]; left_array[left_length] = INT_MAX; right_array[right_length] = INT_MAX; int i=0, j=0; for (int k=left; k<right; k++) { if (left_array[i] <= right_array[j]) { arr[k] = left_array[i++]; } else { arr[k] = right_array[j++]; } } } void merge_sort(int* arr, int num, int left, int right) { if (left + 1 < right) { int mid = (left + right)/2; merge_sort(arr,num,left,mid); merge_sort(arr,num,mid,right); merge(arr,num,left,mid,right); } } 

结果验证

加上打印和调用的示例代码，可以使用如下方式进行验证

#include  #include  #include  #include  int* left_array; int* right_array; void merge(int* arr, int num, int left, int mid, int right) { int left_length = mid - left; int right_length = right - mid; for (int i=0; i<left_length; i++) left_array[i] = arr[left+i]; for (int i=0; i<right_length; i++) right_array[i] = arr[mid+i]; left_array[left_length] = INT_MAX; right_array[right_length] = INT_MAX; int i=0, j=0; for (int k=left; k<right; k++) { if (left_array[i] <= right_array[j]) { arr[k] = left_array[i++]; } else { arr[k] = right_array[j++]; } } } void merge_sort(int* arr, int num, int left, int right) { if (left + 1 < right) { int mid = (left + right)/2; merge_sort(arr,num,left,mid); merge_sort(arr,num,mid,right); merge(arr,num,left,mid,right); } } void print_array(int* arr, int num) { for (int i=0; i<num; i++) printf("%d ",arr[i]); printf("\n"); } int main() { int n = 0; while (scanf("%d",&n) != EOF) { int* array = (int *)malloc(sizeof(int)*n); left_array = (int *)malloc(sizeof(int)*(n/2 + 2)); right_array = (int *)malloc(sizeof(int)*(n/2 + 2)); memset(array,0,sizeof(int)*n); for (int i=0; i<n; i++) { scanf("%d",&array[i]); } merge_sort(array,n,0,n); print_array(array,n); free(array); array= NULL; free(left_array); left_array= NULL; free(right_array); right_array= NULL; } } 

执行结果示例

9
9 8 8 7 6 5 5 4 3
3 4 5 5 6 7 8 8 9