2018-03-28 13:06:39 +08:00
/*
2018-04-16 13:37:25 +08:00
（小数，基准元素，大数）。在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。
2018-03-28 13:06:39 +08:00
快速排序思路：
1. 选取第一个数为基准
2. 将比基准小的数交换到前面，比基准大的数交换到后面
3. 对左右区间重复第二步，直到各区间只有一个数
*/
// ----------------------------------------------------
// 快速排序（递归）
2018-02-11 00:30:01 +08:00
void QuickSort ( vector < int > & v , int low , int high ) {
if ( low > = high ) // 结束标志
return ;
int first = low ; // 低位下标
int last = high ; // 高位下标
2018-03-09 22:08:32 +08:00
int key = v [ first ] ; // 设第一个为基准
2018-02-11 00:30:01 +08:00
while ( first < last )
{
// 将比第一个小的移到前面
while ( first < last & & v [ last ] > = key )
last - - ;
if ( first < last )
v [ first + + ] = v [ last ] ;
// 将比第一个大的移到后面
while ( first < last & & v [ first ] < = key )
first + + ;
if ( first < last )
v [ last - - ] = v [ first ] ;
}
// 基准置位
v [ first ] = key ;
// 前半递归
QuickSort ( v , low , first - 1 ) ;
// 后半递归
QuickSort ( v , first + 1 , high ) ;
2018-03-28 13:06:39 +08:00
}
// ----------------------------------------------------
// 模板实现快速排序（递归）
template < typename T >
void quick_sort_recursive ( T arr [ ] , int start , int end ) {
if ( start > = end )
return ;
T mid = arr [ end ] ;
int left = start , right = end - 1 ;
while ( left < right ) {
while ( arr [ left ] < mid & & left < right )
left + + ;
while ( arr [ right ] > = mid & & left < right )
right - - ;
std : : swap ( arr [ left ] , arr [ right ] ) ;
}
if ( arr [ left ] > = arr [ end ] )
std : : swap ( arr [ left ] , arr [ end ] ) ;
else
left + + ;
quick_sort_recursive ( arr , start , left - 1 ) ;
quick_sort_recursive ( arr , left + 1 , end ) ;
}
template < typename T > //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能
void quick_sort ( T arr [ ] , int len ) {
quick_sort_recursive ( arr , 0 , len - 1 ) ;
}
// ----------------------------------------------------
// 模板实现快速排序（迭代）
struct Range {
int start , end ;
Range ( int s = 0 , int e = 0 ) {
start = s , end = e ;
}
} ;
template < typename T > // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能
void quick_sort ( T arr [ ] , const int len ) {
if ( len < = 0 )
return ; // 避免len等於負值時宣告堆疊陣列當機
// r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素
Range r [ len ] ;
int p = 0 ;
r [ p + + ] = Range ( 0 , len - 1 ) ;
while ( p ) {
Range range = r [ - - p ] ;
if ( range . start > = range . end )
continue ;
T mid = arr [ range . end ] ;
int left = range . start , right = range . end - 1 ;
while ( left < right ) {
while ( arr [ left ] < mid & & left < right ) left + + ;
while ( arr [ right ] > = mid & & left < right ) right - - ;
std : : swap ( arr [ left ] , arr [ right ] ) ;
}
if ( arr [ left ] > = arr [ range . end ] )
std : : swap ( arr [ left ] , arr [ range . end ] ) ;
else
left + + ;
r [ p + + ] = Range ( range . start , left - 1 ) ;
r [ p + + ] = Range ( left + 1 , range . end ) ;
}
2018-02-11 00:30:01 +08:00
}
