# 排序篇 - 归并排序的实现

2012/10/20 23:12

C的实现：

/*
* merge sort implements functions.
*
* @author chenxin
* @see http://www.webssky.com
*/
#include <stdlib.h>
#include "jsort.h"

/*
* a static function to merge two half subarray.
*
* @param *__char the pointer of the array to be sort.
* @param *tmp the temp array.
* @param size the bytes of one item.
* @param left the start positon from the left half.
* @param right the right position from the right half.
* @param end the right-most index of the right half.
*/
static void merge( unsichar_t *__char, unsichar_t *tmp, size_t size,		\
compare_fn_t comp, size_t left, size_t right, size_t end ) {

register size_t ptmp = left;
register size_t lEnd = right - 1;
register size_t pos = left;

register unsichar_t *ltmp, *rtmp;
//merge the two half subarray.
while ( left <= lEnd && right <= end ) {
if ( comp( (ltmp = __char + left * size ) , (rtmp = __char + right * size) ) < 0 ) {
copy_value_to( ltmp, tmp + pos * size, size );
left++;
} else {
copy_value_to( rtmp, tmp + pos * size, size );
right++;
}
pos++;
}

//copy the rest of the left
while ( left <= lEnd ) {
copy_value_to( __char + left * size, tmp + pos * size, size );
left++; pos++;
}

//copy the rest of the right
while ( right <= end ) {
copy_value_to( __char + right * size, tmp + pos * size, size );
right++; pos++;
}

//copy the items back from the temp array to the old one.
while ( ptmp <= end ) {
copy_value_to( tmp + ptmp * size, __char + ptmp * size, size );
ptmp++;
}
}

/*
* a static function to make a recursive call.
*
* @param *__char the pointer of the array.
* @param *tmp the temp array.
* @param size the bytes of one item.
* @param comp the compare function pointer.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
static void merge_recursive( unsichar_t *__char, unsichar_t *tmp,		\
size_t size, compare_fn_t comp, size_t left, size_t right ) {
if ( left < right ) {
register size_t median = ( left + right ) / 2;
merge_recursive( __char, tmp, size, comp, left, median );			//merge the left half
merge_recursive( __char, tmp, size, comp, median + 1, right );		//merge the right half
merge( __char, tmp, size, comp, left, median + 1, right );
}
}

/*
* merge sort algorithm.
*
* @param *a the pointer of the array to be sort.
* @param len the length of the array.
* @param size the bytes of one element.
* @param comp the compare function pointer.
*/
void merge_sort( void *a, size_t len, size_t size, compare_fn_t comp ) {

unsichar_t *tmp 	= ( unsichar_t * ) calloc( len, size );
unsichar_t *__ca 	= ( unsichar_t * ) a;

merge_recursive( __ca, tmp, size, comp, 0, len - 1);

//free the memory
free( tmp );
}

jsort.h头文件可以在"排序篇 - 插入排序的实现"中找到。

Java的实现：

/**
* merge sort algorithm.
*
* @param arr an array of Comparable item.
*/
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void mergeSort( T[] arr ) {
/*if ( arr.length < 15 ) {
insertionSort( arr );
return;
}*/

T[] tmpArr = (T[]) new Comparable[arr.length];

mergeSort(arr, tmpArr, 0, arr.length - 1);
}

/**
* internal method to make a recursive call. <br />
*
* @param arr an array of Comparable items. <br />
* @param tmpArr temp array to placed the merged result. <br />
* @param left left-most index of the subarray. <br />
* @param right right-most index of the subarray. <br />
*/
private static <T extends Comparable<? super T>>
void mergeSort( T[] arr, T[] tmpArr,
int left, int right ) {
//recursive way
if ( left < right ) {
int center = ( left + right ) / 2;
mergeSort(arr, tmpArr, left, center);
mergeSort(arr, tmpArr, center + 1, right);
merge(arr, tmpArr, left, center + 1, right);
}

/*		int len = 2, pos;
int rpos, offset, cut;
while ( len <= right ) {
pos = 0;
offset = len / 2;
while ( pos + len <= right  ) {
rpos = pos + offset;
merge( arr, tmpArr, pos, rpos, rpos + offset - 1 );
pos += len;
}

//merge the rest
cut = pos + offset;
if ( cut <= right )
merge( arr, tmpArr, pos, cut, right );

len *= 2;
}
merge( arr, tmpArr, 0, len / 2, right );*/
}

/**
* internal method to merge the sorted halves of a subarray. <br />
*
* @param arr an array of Comparable items. <br />
* @param tmpArr temp array to placed the merged result. <br />
* @param leftPos left-most index of the subarray. <br />
* @param rightPos right start index of the subarray. <br />
* @param endPos right-most index of the subarray. <br />
*/
private static <T extends Comparable<? super T>>
void merge( T[] arr, T[] tmpArr,
int lPos, int rPos, int rEnd ) {
int lEnd = rPos - 1;
int tPos = lPos;
int leftTmp = lPos;

while ( lPos <= lEnd && rPos <= rEnd  ) {
if ( arr[lPos].compareTo( arr[rPos] ) <= 0 )
tmpArr[ tPos++ ] = arr[ lPos++ ];
else
tmpArr[ tPos++ ] = arr[ rPos++ ];
}

//copy the rest element of the left half subarray.
while ( lPos <= lEnd )
tmpArr[ tPos++ ] = arr[ lPos++ ];
//copy the rest elements of the right half subarray. (only one loop will be execute)
while ( rPos <= rEnd )
tmpArr[ tPos++ ] = arr[ rPos++ ];

//copy the tmpArr back cause we need to change the arr array items.
for ( ; rEnd >= leftTmp; rEnd-- )
arr[rEnd] = tmpArr[rEnd];
}

0
0 收藏

0 评论
0 收藏
0