归并排序算法

特点：归并排序是稳定的排序.即相等的元素的顺序不会改变,  速度仅次于快速排序，但较稳定。

归并操作

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如：设有数列 [6，202，100，301，38，8，1]

初始状态：6, 202, 100, 301, 38, 8, 1

第一次归并后：[6, 202], [100, 301], [8, 38], [1]，比较次数：3；

第二次归并后：[6, 100, 202, 301]，[1, 8, 38]，比较次数：4；

第三次归并后：[1, 6, 8, 38, 100, 202, 301]，比较次数：4；

总的比较次数为：3+4+4=11,；

逆序数为14；

// Completed on 2014.10.11 17:20

// Language: C99

// 版权所有（C）codingwu (mail: oskernel@126.com) 

// 博客地址：http://www.cnblogs.com/archimedes/

#include stdio.h 

#include stdlib.h void merge_sort(int *list, const int first, const int last)

 int len= last-first+1; 

 int left_min,left_max; //左半区域边界 

 int right_min,right_max; //右半区域边界 

 int index;

 int i;

 int *tmp;

 tmp = (int *)malloc(sizeof(int)*len);

 if( tmp == NULL || len = 0 )

 return;

 for( i = 1; i len; i *= 2 )

 for( left_min = 0; left_min len - i; left_min = right_max)

 int j;

 right_min = left_max = left_min + i;

 right_max = left_max + i;

 j = left_min;

 if ( right_max len )

 right_max = len;

 index = 0;

 while( left_min left_max right_min right_max )

 tmp[index++] = (list[left_min] list[right_min] ? list[right_min++] : list[left_min++]);

 while( left_min left_max )

 list[--right_min] = list[--left_max];

 while( index 0 )

 list[--right_min] = tmp[--index];

 free(tmp);

int main()

 int a[] = {288, 52, 123, 30, 212, 23, 10, 233};

 int n, mid;

 n = sizeof(a) / sizeof(a[0]);

 mid = n / 2;

 merge_sort(a, 0, n - 1);

 for(int k = 0; k k++)

 printf("%d ", a[k]);

 printf("\n");

 return 0;

}

使用递归实现：

// Completed on 2014.10.11 18:20

// Language: C99

// 版权所有（C）codingwu (mail: oskernel@126.com) 

// 博客地址：http://www.cnblogs.com/archimedes/

#include stdio.h 

#include stdlib.h 

void merge(int *array,const int first, const int mid, const int last)

 int i,index;

 int first1,last1;

 int first2,last2;

 int *tmp;

 tmp = (int *)malloc((last-first+1)*sizeof(int));

 if( tmp == NULL )

 return;

 first1 = first;

 last1 = mid;

 first2 = mid+1;

 last2 = last;

 index = 0;

 while( (first1 = last1) (first2 = last2) )

 if( array[first1] array[first2] )

 tmp[index++] = array[first1];

 first1++;

 else{

 tmp[index++] = array[first2];

 first2++;

 while( first1 = last1 )

 tmp[index++] = array[first1++];

 while( first2 = last2 )

 tmp[index++] = array[first2++];

 for( i=0; i (last-first+1); i++)

 array[first+i] = tmp[i];

 free(tmp);

void merge_sort(int *array, const int first, const int last)

 int mid = 0;

 if(first last)

 mid = (first + last) / 2;

 merge_sort(array, first, mid);

 merge_sort(array, mid + 1, last);

 merge(array, first, mid, last);

int main()

 int a[] = {288, 52, 123, 30, 212, 23, 10, 233};

 int n, mid;

 n = sizeof(a) / sizeof(a[0]);

 mid = n / 2;

 merge_sort(a, 0, n - 1);

 for(int k = 0; k k++)

 printf("%d ", a[k]);

 printf("\n");

 return 0;

}

【算法】归并排序算法 归并排序是一种将递归和分治结合到一起实现的一种排序算法。将一个序列通过递归拆分为越来越小的半子序列，然后再对半子序列合并为 一个大的有序序列。
【算法基础】归并排序解析 归并排序是建立在归并操作上的一种有效，稳定的排序算法，它是采用分治法的一个非常典型的应用。将待排序数组分为两条线逐级拆分，将子序列进行排序，然后沿两条线逐级合并，得到完全有序序列。这种通过递归，层层合并的方法，称为归并。
归并排序算法 主要思想：分治，但与快速排序有些不同，快速排序是先调整范围再递归左右两边，归并是先递归再归并左右两边