#include <iostream>
using namespace std;
/* 快速排序
** 思想：采用了分治策略，选用数组任一记录（一般为第一个）为Pivot
** 根据这个Pivot，将数组分为左、右两个较小的子区间，且左边记录的关键字
** 均小于等于Pivot的关键字，右边记录的关键字均大于等于Pivot的关键字
** 以此思想递归之。
** 注：Pivot可翻译为支点
*/
int a[] = {
49,
38,
65,
97,
76,
13,
27,
49 };
void swap(
int & lValue,
int &
rValue )
{
int temp =
lValue;
lValue =
rValue;
rValue =
temp;
return;
}
// 一次划分
int Partition(
int * Sq,
int low,
int high )
{
int pivotkey =
Sq[low];
while ( low <
high )
{
while ( low < high && Sq[high] >=
pivotkey )
{
--
high;
}
swap( Sq[low], Sq[high] );
while ( low < high && Sq[low] <=
pivotkey )
{
++
low;
}
swap( Sq[low], Sq[high] );
}
return low;
}
// 更高效率的划分
int Partition1(
int * Sq,
int low,
int high )
{
int temp =
Sq[low];
int pivotkey =
Sq[low];
while ( low <
high )
{
while ( low < high && Sq[high] >=
pivotkey )
{
--
high;
}
Sq[low] =
Sq[high];
while ( low < high && Sq[low] <=
pivotkey )
{
++
low;
}
Sq[high] =
Sq[low];
}
Sq[low] =
temp;
return low;
}
void QSort(
int * Sq,
int low,
int high )
{
if ( low <
high )
{
int pivotloc =
Partition1( Sq, low, high );
QSort( Sq, low, pivotloc -
1 );
QSort( Sq, pivotloc +
1, high );
}
return;
}
int main()
{
QSort( a, 0,
7 );
for (
int i =
0; i <
8; ++
i )
{
cout << a[i] <<
endl;
}
return 0;
}
转载于:https://www.cnblogs.com/c007136/archive/2012/04/25/2470730.html
