------<a href="http://www.itheima.com" target="blank">Java培训、Android培训、iOS培训、.Net培训</a>、期待与您交流！ -------
瑞士计算机科学家尼克劳斯.沃思提出了一个着名的公式~数据结构+算法=程序。从此公式可以看出，算法是构成程序的一个重要组成部分，而所谓的算法 ，可以理解为解决某一确定问题所采用的具体步骤和方法。那么作为程序开发者，就必须掌握一些常见算法，之前几篇博客提到了排序，这里来个收尾，给大家分享下较为经典的排序~归并排序。
归并排序又称合并排序，其算法思想是将待排序序列分为两个部分，依次对分得的两个部分再次使用归并排序，之后再对其进行合并。仅从算法上了解归并排序很抽象的说。接下来以序列a[0],a[1],...a[n-1]进行讲解，在此采用自顶向下的实现方法，操作步骤如下：
1)将所有进行的排序序列分为左右两个部分，如果要进行排序序列的起始元素下标，为first，最后一个元素为last，那么左右两部分之间的临界点下标mid=（first+last）/2这两部分分别是a[fiirst...mid],a[mid+1...last].
2)将上面所划分得两部分为序列继续按1）继续进行划分，直到划分区间长度为1.
3)将划分结束后的序列进行归并排序，排序方法为对所有分的n个子序列进行两两合并，得到n/2或n/2+1个含有两个元素的子序列，再对得到的子序列进行合并。直到得到一个长度为n的有序序列为止。
且看下面代码实现归并排序：
#include <stdio.h>
#include <stdlib.h>
#define N 7
void merge(int arr[], int low, int mid, int high)
{
int i, k;
int *tmp = (int *) malloc((high-low+1) * sizeof(int));
//申请空间，使其大小为两个
int left_low = low;
int left_high = mid;
int right_low = mid + 1;
int right_high = high;
for (k = 0; left_low <= left_high && right_low <= right_high; k++) //比较两个指针所指向的元素
{
if(arr[left_low]<=arr[right_low])
{
tmp[k] = arr[left_low++];
}
else
{
tmp[k] = arr[right_low++];
}
}
if(left_low <= left_high)
//若第一个序列有剩余，直接复制出来粘到合并序列尾
{
// memcpy(tmp+k, arr+left_low, (left_high-left_low+1)*sizeof(int));
for(i=left_low;i<=left_high;i++)
tmp[k++] = arr[i];
}
if(right_low <= right_high)
//若第二个序列有剩余，直接复制出来粘到合并序列尾
{
// memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
for(i=right_low;i<=right_high;i++)
tmp[k++] = arr[i];
}
for(i=0;i<high-low+1;i++)
arr[low+i] = tmp[i];
free(tmp);
return ;
}
void merge_sort(int arr[], unsigned int first, unsigned int last)
{
int mid = 0;
if(first<last)
{
mid = (first+last)/2; /*注意防止溢出*/
/*mid = first/2 + last/2;*/
//mid = (first & last) + ((first ^ last) >> 1);
merge_sort(arr, first, mid);
merge_sort(arr, mid+1,last);
merge(arr,first,mid,last);
}
return ;
}
int main()
{
int i;
int a[N]={32,12,56,78,76,45,36};
printf("排序前
");
for(i=0;i<N;i++)
printf("%d ",a[i]);
merge_sort(a,0,N-1);
printf("
排序后
");
for(i=0;i<N;i++)
printf("%d ",a[i]);
printf("
");
return 0;
}
运行效果：
