排序篇 - 快速排序的实现

原创
2012/10/20 23:28
阅读数 257

快速排序这个名字来源于它的实际效率。它也是使用分治算法实现的一种排序算法,对于基本数据类型的排序,它比归并排序的实际效率高些(100万数据的话,排序时间稳定为归并排序的1/2的样子)。

算法时间复杂度为O(N*logN),最坏算法为O(N^2),但是通过实际的编程可以避免这种情况的出现。

该算法的核心问题在于找“pivot(枢纽元)”(可以有效的避免O(n^2)的出现),和“分割策略”。本实现采用”左中又三值分割“法来获取枢纽元。

本实现中,对于小数据量,我采用的是”插入排序“来代替。

这里不介绍算法的具体过程,给出C和Java的实现(维基百科的实现,也是我写的。代码用了很久了,可以直接拿来用,已泛型化)。

C的实现:


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

#define CUTOFF 11


/*
 * a static method to swap the value.
 * 
 * @param * the first pointer.
 * @param * the second pointer.
 * @param size the bytes of one item.
 */
void swap_value( void *a, void *b, size_t size ) {
	
	unsichar_t *__a = ( unsichar_t * ) a;
	unsichar_t *__b = ( unsichar_t * ) b;
	register unsichar_t tmp;
	
	do {
		tmp = *__a;
		*__a++ = *__b;
		*__b++ = tmp;
	} while ( --size > 0 ) ;
}

/*
 * a static function to get the median of the partition.
 * 
 * @param *a the pointer of the array to be sort.
 * @param left the left-most index of the subarray.
 * @param right the right-most index of the subarray.
 * @param comp the compare function pointer. 
 */
static unsichar_t *median( unsichar_t *a, size_t size, \
		compare_fn_t comp, size_t left, size_t right ) {
	register size_t center = ( left + right ) / 2;
	
	unsichar_t *lp = a + left * size;
	unsichar_t *cp = a + center * size;
	unsichar_t *rp = a + right * size;
	
	if ( comp( lp, cp ) > 0 )
		swap_value( lp, cp, size );
	if ( comp( lp, rp ) > 0 )
		swap_value( lp, rp, size );
	if ( comp( cp, rp ) > 0 )
		swap_value( cp, rp, size );
		
	//move the pivot to the right - a positon.
	swap_value( cp, rp - size, size );
	//return the pivot
	return rp - size;
	
}


/*
 * a static function to do the partition.
 * @see quicksort( void *, size_t, size_t, compare_fn_t );
 */
static void quick_sort( unsichar_t *a, size_t size, \
		compare_fn_t comp, size_t left, size_t right ) {
	if ( left + CUTOFF <= right ) {
		//get the privot of the subarray.
		unsichar_t *pivot = median( a, size, comp, left, right );
		//printf("pivot=%d\n", * (( int * ) pivot));
		//start partitioning.
		register i = left, j = right - 1;
		for ( ; ; ) {
			while ( comp( a + (++i * size), pivot ) < 0 ) ;
			while ( comp( a + (--j * size), pivot ) > 0) ;
			if ( i < j ) 
				swap_value( a + i * size, a + j * size, size );
			else
				break;
		}
		//printf("i=%d, j=%d\n", i, j);
		//swap the privot back to the small colleciton.
		//swap( a + i * size, a + ( right - 1 ) * size, size );
		swap_value( a + i * size, pivot, size );
		
		quick_sort( a, size, comp, left, i - 1 );		//sort the small collection
		quick_sort( a, size, comp, i + 1, right);
		
	} else {
		//if the number of the items is less than CUTOFF use insertion sort instead.
		insertion_sub_sort( a, size, comp, left, right );
	}
}

/*
 * quick 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 item in the array.
 * @param comp the compare function pointer. 
 */
void quicksort( void *a, size_t len, size_t size, compare_fn_t comp ) {
	unsichar_t *__a = ( unsichar_t * ) a;
	quick_sort( __a, size, comp, 0, len - 1 );
}


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

Java的实现:


/**
	 * method to swap elements in an array.<br />
	 * 
	 * @param arr an array of Objects. <br />
	 * @param idx1 the index of the first element. <br />
	 * @param idx2 the index of the second element. <br />
	 */
	public static <T> void swapReferences( T[] arr, int idx1, int idx2 ) {
		T tmp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = tmp;
	}
	
	public static final int CUTOFF = 11; /**
	 * quick sort algorithm. <br />
	 * 
	 * @param arr an array of Comparable items. <br />
	 */
	public static <T extends Comparable<? super T>> void quicksort( T[] arr ) {
		quicksort( arr, 0, arr.length - 1 );
	}
	
	/**
	 * get the median of the left, center and right. <br />
	 * order these and hide the pivot by put it the end of
	 * of the array. <br />
	 * 
	 * @param arr an array of Comparable. <br />
	 * @param left the most-left index of the subarray. <br />
	 * @param right the most-right index of the subarray.<br />
	 * @return T
	 */
	public static <T extends Comparable<? super T>>
	T median( T[] arr, int left, int right ) {
		
		int center = ( left + right ) / 2;
		
		if ( arr[left].compareTo( arr[center] ) > 0 )
			swapReferences( arr, left, center );
		if ( arr[left].compareTo( arr[right] ) > 0 )
			swapReferences( arr, left, right );
		if ( arr[center].compareTo( arr[right] ) > 0 )
			swapReferences( arr, center, right );
		
		swapReferences( arr, center, right - 1 );
		return arr[ right - 1 ];
	}
	
	/**
	 * method to sort an subarray from start to end
	 * 		with insertion sort algorithm. <br />
	 * 
	 * @param arr an array of Comparable items. <br />
	 * @param start the begining position. <br />
	 * @param end the end position. <br />
	 */
	public static <T extends Comparable<? super T>> 
	void insertionSort( T[] arr, int start, int end ) {
		int i;
		for ( int j = start + 1; j <= end; j++ ) {
			T tmp = arr[j];
			for ( i = j; i > start && tmp.compareTo( arr[i - 1] ) < 0; i-- ) {
				arr[ i ] = arr[ i - 1 ];
			}
			if ( i < j ) arr[ i ] = tmp;
		}
	}
	
	/**
	 * internal method to sort the array with quick sort algorithm. <br />
	 * 
	 * @param arr an array of Comparable Items. <br />
	 * @param left the left-most index of the subarray. <br />
	 * @param right the right-most index of the subarray. <br />
	 */
	private static <T extends Comparable<? super T>> 
	void quicksort( T[] arr, int left, int right ) {
		if ( left + CUTOFF <= right  ) {
			//find the pivot
			T pivot = median( arr, left, right );
			
			//start partitioning
			int i = left, j = right - 1;
			for ( ; ; ) {
				while ( arr[++i].compareTo( pivot ) < 0 ) ;
				while ( arr[--j].compareTo( pivot ) > 0 ) ;
				if ( i < j )
					swapReferences( arr, i, j );
				else
					break;
			}
			
			//swap the pivot reference back to the small collection.
			swapReferences( arr, i, right - 1 );
			
			quicksort( arr, left, i - 1 );		//sort the small collection.
			quicksort( arr, i + 1, right );		//sort the large collection.
			
		} else {
			//if the total number is less than CUTOFF we use insertion sort instead.
			insertionSort( arr, left, right );
		}
	}


看到主程序中的高效的循环了,这是快速排序快于归并排序的主要原因。

这个主程序,只有在采用“三值分割法”取枢纽元的前提下才不会出问题。

(仔细想想?快速选择算法是不是出来了)。

有问题我们一起讨论。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部