堆排序之所以效率比较高是利用了完全二叉树，但是堆排序的设计本身是比较复杂的
那就引出一个问题，有没有更简单的使用完全二叉树来排序的算法呢？
这就引出了归并排序算法
归并排序就是利用归并的思想实现的排序方法，原理是假设初始序列含有n个记录，则可以看出是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或者1的有序子序列；再两两归并。。。。如此反复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路规定排序
其排序的过程就是完全二叉树
归并排序的时间复杂度也是nlogn,且这是归并排序中最好，最坏，平均的时间性能,因此归并排序是一种稳定的排序
其空间复杂度为n+logn
也就是说，归并排序是一种比较占用内存，但是效率高且稳定的算法
#include
#define MAXSIZE 10
// 实现归并，并把最后的结果存放到list1里
void merging(int *list1, int list1_size, int *list2, int list2_size)
{
int i, j, k, m;
int temp[MAXSIZE];
i = j = k = 0;
while( i < list1_size && j < list2_size )
{
if( list1[i] < list2[j] )
{
temp[k++] = list1[i++];
}
else
{
temp[k++] = list2[j++];
}
}
while( i < list1_size )
{
temp[k++] = list1[i++];
}
while( j < list2_size )
{
temp[k++] = list2[j++];
}
for( m=0; m < (list1_size + list2_size); m++ )
{
list1[m] = temp[m];
}
}
void MergeSort(int k[], int n)
{
if( n > 1)
{
int *list1 = k;
int list1_size = n/2;
int *list2 = k + n/2;
int list2_size = n - list1_size;
MergeSort(list1, list1_size);
MergeSort(list2, list2_size);
merging(list1, list1_size, list2, list2_size);
}
}
int main()
{
int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
MergeSort(a, 10);
printf("排序后的结果是：");
for( i=0; i < 10; i++ )
{
printf("%d", a[i]);
}
printf("\n\n");
return 0;
}
递归本身是有限制的（时间和空间上的性能损耗），之前也说过，大多数递归都是可以改造为迭代
#include
#include
#define MAXSIZE 10
void MergeSort(int k[], int n)
{
int i, next, left_min, left_max, right_min, right_max;
int *temp = (int *)malloc(n * sizeof(int));
for( i=1; i < n; i*=2 )
{
for( left_min=0; left_min < n-i; left_min = right_max )
{
right_min = left_max = left_min + i;
right_max = left_max + i;
if( right_max > n )
{
right_max = n;
}
next = 0;
while( left_min < left_max && right_min < right_max )
{
if( k[left_min] < k[right_min] )
{
temp[next++] = k[left_min++];
}
else
{
temp[next++] = k[right_min++];
}
}
while( left_min < left_max )
{
k[--right_min] = k[--left_max];
}
while( next > 0 )
{
k[--right_min] = temp[--next];
}
}
}
}
int main()
{
int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
MergeSort(a, 10);
printf("排序后的结果是：");
for( i=0; i < 10; i++ )
{
printf("%d", a[i]);
}
printf("\n\n");
return 0;
}
