快速排序.txt

快速排序的算法描述

//快速排序之确定划分点
{逻辑结构：线性表}
算法思想：
1。假设对线性表List[p..r]确定划分点。定义位序变量i,j。i始终指向已处理的元素列表的末尾，即元素
List[p..i]均不大于List[r]。j始终指向当前要处理的元素，即元素List[(i+1)..(j-1)]均大于List[r]。
2。i = p - 1。j = p。
3。当j<r时，进行如下操作，否则转至步骤6：
4。如果List[j]<=List[r]，则i=i+1，交换List[i]与List[j]。
5。j=j+1。转至步骤3。
6。交换List[i+1]与List[r]。
7。返回i+1。

//算法描述
Partition( List, p, r )  // List为待处理线性表（顺序表），p，i为始末位序。
	i = p - 1;
	j = p;
	while j < r
	[
		if List[j] <= List[r] 
		[
			i = i + 1;
			exchange(List[i], List[j]);
		]
		j = j + 1;
	]
	exchange(List[i+1], List[r]);
	return i+1;
{Partition end}

//算法时间复杂度（最坏）
O(n)

//代码实现
template< typename T >
void	Exchange( 
				 T &  leftElement, 
				 T & rightElement 
				 )
{
	T  temp = leftElement;
	leftElement = rightElement;
	rightElement = temp;
}

template< typename T >
int		Partition( 
				  T List[], 
				  int  nStartPos, 
				  int  nStopPos
				  )
{
	assert( nStartPos >= 0 && nStopPos >= 0 );
	if ( nStartPos < 0 || nStopPos < 0 )
		return -1;

	int  nLessEndPos = nStartPos - 1;
	int  nCurrentDealPos = nStartPos;

	while ( nCurrentDealPos < nStopPos )
	{
		if ( List[nCurrentDealPos] <= List[nStopPos] )
		{
			nLessEndPos ++;
			Exchange( List[nLessEndPos], List[nCurrentDealPos] );
		}
		nCurrentDealPos ++;
	}
	
	Exchange( List[nLessEndPos+1], List[nStopPos] );

	return nLessEndPos + 1;
}


//快速排序
{逻辑结构：线性表}
算法思想：
{对List[p..r]进行快速排序}
1。如果p<r则进行如下操作：
2。调用划分算法，q = Partition(List, p, r)。
3。对List[p..(q-1)]递归调用本算法。
4。对List[(q+1)..r]递归调用本算法。

//算法描述
QuickSort( List, p, r )  // List为待处理线性表（顺序表），p，i为始末位序。
	if p < r
	[
		q = Partition(List, p, r);
		QuickSort(List, p, q-1);
		QuickSort(List, q+1, r);
	]
{QuickSort end}

//算法时间复杂度
最坏的情况下是O(n^2)，最佳的情况下是O(nlgn)

//代码实现
template< typename T >
void	QuickSort( 
				  T List[], 
				  int nStartPos, 
				  int nStopPos
				  )
{
	if ( nStartPos < nStopPos )
	{
		int  nMidPos = Partition<T>( List, nStartPos, nStopPos );
		QuickSort( List, nStartPos, nMidPos - 1 );
		QuickSort( List, nMidPos + 1, nStopPos );
	}
}


//快速排序之随机化版本
//算法描述
{仅划分算法发生改变}
Partition( List, p, r )  // List为待处理线性表（顺序表），p，i为始末位序。
	i = p - 1;
	j = p;
	k = RAN(p, r);  //产生合适随机数
	exchange(List[k], List[r]); //交换
	while j < r
	[
		if List[j] <= List[r] 
		[
			i = i + 1;
			exchange(List[i], List[j]);
		]
		j = j + 1;
	]
	exchange(List[i+1], List[r]);
	return i+1;
{Partition end}

//代码实现
inline int rnd_number( int n )
{
	static __int64 x;
	x = ( 2053 * x + 13849 ) % 0x7fffffff;
	return (int) x % n;
}

template< typename T >
int		Partition_Randomized( 
				  T List[], 
				  int  nStartPos, 
				  int  nStopPos
				  )
{
	assert( nStartPos >= 0 && nStopPos >= 0 );
	if ( nStartPos < 0 || nStopPos < 0 )
		return -1;

	int  nLessEndPos = nStartPos - 1;
	int  nCurrentDealPos = nStartPos;

	int	nTemp = rnd_number( nStopPos - nStartPos + 1) + nStartPos;
	Exchange( List[nTemp], List[nStopPos] );

	while ( nCurrentDealPos < nStopPos )
	{
		if ( List[nCurrentDealPos] <= List[nStopPos] )
		{
			nLessEndPos ++;
			Exchange( List[nLessEndPos], List[nCurrentDealPos] );
		}
		nCurrentDealPos ++;
	}

	Exchange( List[nLessEndPos+1], List[nStopPos] );

	return nLessEndPos + 1;
}

template< typename T >
void	QuickSort_Randomized( 
				  T List[], 
				  int nStartPos, 
				  int nStopPos
				  )
{
	if ( nStartPos < nStopPos )
	{
		int  nMidPos = Partition_Randomized<T>( List, nStartPos, nStopPos );
		QuickSort( List, nStartPos, nMidPos - 1 );
		QuickSort( List, nMidPos + 1, nStopPos );
	}
}

*************************************************************