归并排序

归并排序的定义您可以查查百度百科，有较为详细的说明。下面是按照我的理解给您的描述：归并排序的算法思想是将几个有序的序列合并为一个有序序列，较常见的是2路归并排序，即将两个有序序列合并为一个有序序列。其通常采用递归算法实现：1. 将序列划分为两个序列，通过归并排序分别对两个序列进行排序2. 将两个归并排序后的有序序列归并成一个有序序列其算法描述如下：void mergerSort(int array[], int begin, int end){ if (begin >= end) //只有一个元素，或不合法则返回 return; mid = (begin + end) / 2; mergerSort(array,begin,mid); mergerSort(array,mid + 1,end); //归并序列[begin,mid]与[mid+1,end] //归并的方法有很多，可以是将后一个序列插入前一个序列中 //也可以通过冒泡排序等方式使得两个序列有序 //也可以借助第三方空间}

#include<stdio.h>#include<stdlib.h>#include<time.h>int b[ 10 ];void Merge( int c[], int d[], int l, int m, int r ){ int i = l, j = m + 1, k = l; while( ( i <= m ) && ( j <= r ) ) if( c[ i ] <= c[ j ] ) d[ k++ ] = c[ i++ ]; else d[ k++ ] = c[ j++ ]; if( i > m ) for( int q = j; q <= r; q++ ) d[ k++ ] = c[ q ]; else for( int q = i; q <= m; q++ ) d[ k++ ] = c[ q ];}void Copy( int c[], int d[], int n1, int n2 ){ for( int i = n1; i <= n2; i++ ) c[ i ] = d[ i ];}void MergeSort( int a[], int left, int right ){ if( left < right ) { int i = ( left + right ) / 2; //取中点，分成两路 MergeSort( a, left, i ); MergeSort( a, i + 1, right ); Merge( a, b, left, i, right ); //合并到数组b Copy( a, b, left, right ); //复制到数组a }}int main(){ int a[ 10 ], i; srand( time( 0 ) ); for( i = 0; i < 10; i++ ) a[ i ] = rand() % 100; //随机生成 for( i = 0; i < 10; i++ ) //输出随机生成的数据 printf( "%d ", a[ i ] ); printf( " " ); MergeSort( a, 0, 9 ); for( i = 0; i < 10; i++ ) //输出排序后的结果 printf( "%d ", a[ i ] ); printf( " " ); return 0;} //在vc++6.0上调试运行成功。若有不明白的地方，call me!!!