排序---归并排序

一、定义

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

二、实现原理

归并排序的思想是：将数组分成左右两个数组，假如左右两个数组都有序了，那么可以借用一个临时数组来对这两个有序数组进行拼接，使整体有序（归并过程）。而该两个左右数组又可分成左右子数组（递归过程），以此类推，当子数组元素个数为1时，就可以认为这个子数组是有序的，然后用临时数组对这两个子数组进行排序，再将已经有序的临时数组拷贝给原数组。

三、代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>//时间复杂度：O(N*logN),空间复杂度：O(N)void MergeSort(int* arr, int* tmp, int begin, int end)
{if (begin >= end) {return;}//分区间：int mid = (begin + end) / 2;//[begin,mid] mid [mid+1,end]  ,区间要这样分，防止死循环，如： begin=2,end=3,mid=2;//                           假如区间以这种方式递归：(arr,tmp,begin,mid-1)==(arr,tmp,2,1)：正常//                                                   (arr,tmp,mid,end)==(arr,tmp,2,3) ：这里会导致死循环MergeSort(arr, tmp, begin, mid);MergeSort(arr, tmp, mid + 1, end);       //下面这种区间分法就不会：(arr,tmp,begin,mid)==(arr,tmp,2,2)//                                                                 (arr,tmp,mid+1,end)==(arr,tmp,3,3)//归并：int left1 = begin, right1 = mid;int left2 = mid + 1, right2 = end;int i = begin; //临时数组开始存储数据的位置要在begin的位置开始，否则在拷贝临时数组给原数组时，//会将原数组的数据弄乱while (left1 <= right1 && left2 <= right2) {if (arr[left1] <= arr[left2]) {tmp[i++] = arr[left1++];}else {tmp[i++] = arr[left2++];}}//剩余的：while (left1 <= right1) {tmp[i++] = arr[left1++];}while (left2 <= right2) {tmp[i++] = arr[left2++];}//将已经有序的tmp数组复制到arr中，注意拷贝的起始位置起点和目标位置起点也是要根据begin来确定的//起始位置是tmp+begin ,目标位置是arr+beignmemcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));//end-begin+1是待拷贝数组的元素个数
}void Print(int* p, int size)
{for (int i = 0; i < size; i++) {printf("%d ", p[i]);}printf("\n");
}
void test()
{int arr[] = { 5,3,7,2,8,4,6,1 };int size = sizeof(arr) / sizeof(int);int* tmp = (int*)malloc(sizeof(int) * size);MergeSort(arr,tmp,0,size-1);Print(arr, size);free(tmp);
}
int main()
{test();return 0;
}