/*
* File: mergesort.c
* Time: 2014-07-19 HJJ
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
static void merge1(int array[], int tmp[], int lpos, int rpos, int rend);
static void msort1(int array[], int tmp[], int left, int right);
void merge_sort1(int array[], int n)
{
assert(array!=NULL && n>1); //条件不满足，退出程序并打印错误语句。
int *tmp = (int *)malloc(sizeof(int) * n);
assert(tmp != NULL);
int i;
for (i = 0; i < n; i ++) {
tmp[i] = array[i];
}
msort1(array, tmp, 0, n-1);
free(tmp);
}
//递归的调用此函数，实现折半划分，只完成划分，不实现排序，最终返回array[]数组有序
static void msort1(int array[], int tmp[], int left, int right)
{
assert(array!=NULL && tmp!=NULL);
if (left == right)
return;
int center = (left + right) / 2;
msort1(tmp, array, left, center);
msort1(tmp, array, center+1, right);
merge1(tmp, array, left, center+1, right);
}
//该函数实现，将array[]的左右两半排好序的数组，归并为tmp[]，并排序
static void merge1(int array[], int tmp[], int lpos, int rpos, int rend)
{
assert(array!=NULL && tmp!=NULL);
int lend = rpos - 1;
int tmp_pos = lpos;
while (lpos<=lend && rpos<=rend) {
if (array[lpos] <= array[rpos])
tmp[tmp_pos++] = array[lpos++];
else
tmp[tmp_pos++] = array[rpos++];
}
while (lpos <= lend)
tmp[tmp_pos++] = array[lpos++];
while (rpos <= rend)
tmp[tmp_pos++] = array[rpos++];
}
int main(int argc, char *argv[])
{
int a[7] = {6, 5, 4, 3, 2, 1, 7};
merge_sort1(a, 7);
int i;
for (i = 0; i < 7; i ++) {
printf("%3d", a[i]);
}
printf("n");
return 0;
}
算法3：
程序开始处分配一个大的数组，只是每次用array[]将数据给tmp[]排好序后，最后再将tmp[]给array[]赋值，这样就能完成每次调用的时候，入口都一样。
void merge_sort1(int array[], int n)
{
assert(array!=NULL && n>1); //条件不满足，退出程序并打印错误语句。
int *tmp = (int *)malloc(sizeof(int) * n);
assert(tmp != NULL);
int i;
for (i = 0; i < n; i ++) {
tmp[i] = array[i];
}
msort1(array, tmp, 0, n-1);
free(tmp);
}
//递归的调用此函数，实现折半划分，只完成划分，不实现排序，最终返回array[]数组有序
static void msort1(int array[], int tmp[], int left, int right)
{
assert(array!=NULL && tmp!=NULL);
if (left == right)
return;
int center = (left + right) / 2;
msort1(tmp, array, left, center);
msort1(tmp, array, center+1, right);
merge(tmp, array, left, center+1, right);
}
实现方法二：
void merge(int array[],int tmp[],int lpos,int rpos,int rend)
{
int i,leftend,num,tmppos;
leftend = rpos - 1;
num = rend - lpos + 1;
tmppos = lpos;
while(lpos <= leftend && rpos <= rend){
if(array[lpos] <= array[rpos])
tmp[tmppos++] = array[lpos++];
else
tmp[tmppos++] = array[rpos++];
}
while(lpos <= leftend)
tmp[tmppos++] = array[lpos++];
while(rpos <= rend)
tmp[tmppos++] = array[rpos++];
for(i = 0;i < num;i++,rend--)
array[rend] = tmp[rend];
}
