# 排序篇 - 快速排序的实现

2012/10/20 23:28

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