文档章节

排序篇 - 归并排序的实现

狮子的魂
 狮子的魂
发布于 2012/10/20 23:12
字数 935
阅读 121
收藏 0

归并排序,使用分治算法实现的一种高效的排序排序算法,时间复杂度为O(N*logN) 这已经是比较排序最好的结果了(任何一种排序算法都需要omega(N!)次比较)。

算法就不讲解了,谷歌一下,这里给出C和Java的实现。(代码已经用了很久了,可以直接拿来用,维基百科的Java实现也是我写的,已泛型化)。

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);
		}
		
		//loop instead
/*		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];
	}


有递归的实现,也有非递归的实现,但是通过测试发现,递归的实现好像实际效率还高一点。也许和我的实现有关吧。

有问题我们一起讨论。

© 著作权归作者所有

共有 人打赏支持
狮子的魂

狮子的魂

粉丝 205
博文 11
码字总数 11922
作品 7
深圳
CEO
私信 提问
java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯
2018/06/05
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

5、redis分布式锁

参考链接:https://www.cnblogs.com/linjiqin/p/8003838.html 一:介绍 实现分布式锁有三种方式:1、数据库乐观锁,2、基于redis,3、基于zookeeper。 redis服务端是单线程操作,完美地避免了...

刘付kin
20分钟前
3
0
OSChina 周日乱弹 —— 我重新说

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @宇辰OSC :分享矢野立美的单曲《LOVE Theme from TIGA <M-2>》: 《LOVE Theme from TIGA <M-2>》- 矢野立美 手机党少年们想听歌,请使劲儿戳...

小小编辑
今天
56
5
Java单例模式学习记录

在项目开发中经常能遇见的设计模式就是单例模式了,而实现的方式最常见的有两种:饿汉和饱汉(懒汉)。由于日常接触较多而研究的不够深入,导致面试的时候被询问到后有点没底,这里记录一下学习...

JerryLin123
昨天
10
0
VSCODE 无法调试

VSCODE 无法调试 可以运行 可能的原因: GCC 的参数忘了加 -g

shzwork
昨天
5
0
理解去中心化 稳定币 DAI

随着摩根大通推出JPM Coin 稳定币,可以预见稳定币将成为区块链落地的一大助推器。 坦白来讲,对于一个程序员的我来讲(不懂一点专业经济和金融),理解DAI的机制,真的有一点复杂。耐心看完...

Tiny熊
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部