quiksort.h

来自「C++参考书」· C头文件 代码 · 共 48 行

#ifndef QUIKSORT_H
#define QUIKSORT_H

template<typename T>
inline void swap( T &t1, T &t2 )
{
	T hold = t2 ;
	t2 = t1 ;
	t1 = hold ;
}

template<typename T>
void quickSort( T *array, int hi, int lo = 0 )
{
	while ( hi > lo ) {

		int i = lo ;
		int j = hi ;

		do {

			while ( array[i] < array[lo] && i < j )
				i++ ;

			while ( array[--j] > array[lo] ) ;

			if ( i < j )
				swap( array[j], array[i] ) ;

		} while ( i < j ) ;

		swap( array[lo], array[j] ) ;

		if ( j - lo > hi - ( j + 1 ) ) {
			quickSort( array, j - 1, lo ) ;
			lo = j + 1 ;
		}
		else {
			quickSort( array, hi, j + 1 ) ;
			hi = j - 1 ;
		}

	}
}

#endif