好了，废话不多说，直接来干货。
首先说下快速排序的思想，一般网上说的都是Horno（Horno这个人提出来的算法）法，我这里除此之外还介绍另外的两种方法。
1、找一个基准值key（一般三数取中法），本题中基准值为数组中最右的元素，再定义两个指针begin（指向首元素）和end（指向尾元素）
2、begin从前往后走找比基准值key大的元素（找到后停下），end从后往前走找比基准值小的元素（找到后也停下），
然后，交换
array[begin]和
array[end]，依次循环操作。
3、当begin与end相遇，将
array[begin]或
array[end]与基准值交换。
代码：
算法思想：
1、找一个基准值key（一般三数取中法），本题中基准值为数组中最右的元素，再定义两个指针begin（指向首元素）和end（指向尾元素）
2、begin从前往后走找比基准值key大的元素（找到后停下），end从后往前走找比基准值小的元素（找到后也停下），
然后，交换
array[begin]和
array[end]，依次循环操作。
3、当begin与end相遇，将
array[begin]或
array[end]与基准值交换。*/
int partion1(
int *
array,
int left,
int right)
{
int key =
array[right];
int begin = left;
int end = right;
while (begin<end)
{
while (begin<end&&
array[begin] <= key)
begin++;
while (begin<end&&
array[end] >= key)
end--;
if (begin < end)
std::swap(
array[begin],
array[end]);
}
if (begin!=right)
std::swap(
array[begin],
array[right]);
return begin;
}
1、定义begin和end分别指向数据的第一个元素和最后一个元素，基准值key为数组最后一个元素，
array[end]元素的位置为一个坑
2、begin从前往后走，找比key大的值，找到之后，将
array[begin]赋值给
array[end]，填充end位置的坑，此时begin位置为一个坑
3、end从后往前走，找比key小的值，找到之后，将
array[end]赋值给
array[begin]，填充begin位置的坑，此时end位置为一个新的坑
4、此类方法依次填坑，当begin和end相遇，则循环结束，将key的值填最后一个坑。
int partion2(
int *
array,
int left,
int right)
{
int key =
array[right];
int begin = left;
int end = right;
while (begin<end)
{
while (begin<end&&
array[begin] <= key)
begin++;
if (begin < end)
{
array[end] =
array[begin];
end--;
}
while (begin<end&&
array[end] >= key)
end--;
if (begin<end)
{
array[begin] =
array[end];
begin++;
}
}
if (begin != right)
std::swap(
array[begin], key);
array[begin] = key;
return begin;
}
算法思想：
1、选择一个基准值key，定义两个指针pPre和pPcur（pPre指向pPcur的前一个位置），pPre和pPcur同时走，当pPcur标记的元素比key大时，只有pPcur继续向前走（此时pPre停下来），当pPcur走到标记的元素比pPre小时，pPcur停下，此时交换
array[pPcur]和
array[pPre+
1],然后，pPre往前走一步，pPcur继续往前走。
2、当pCur走出界了，则将pPre+
1位置的值与key交换。
int partion3(
int *
array,
int left,
int right)
{
int pPcur = left;
int pPre = left-
1;
int key =
array[right];
while (pPcur<right)
{
if (
array[pPcur ]< key)
{
swap(
array[pPre +
1],
array[pPcur]);
pPre++;
}
pPcur++;
}
swap(
array[right],
array[++pPre]);
return pPre;
}
void QuickSort(
int *
array,
int left,
int right )
{
if (left < right)
{
int goal = partion3(
array, left, right);
QuickSort(
array, left, goal-
1);
QuickSort(
array, goal+
1, right);
}
}
void QuickSortNor(
int *
array,
int size)
{
stack<int>s;
s.push(
0);
s.push(size -
1);
while (!s.empty())
{
int right = s.top();
s.pop();
int left = s.top();
s.pop();
int mid = partion1(
array, left, right);
if (left <= right)
{
s.push(mid +
1);
s.push(right);
s.push(left);
s.push(mid -
1);
}
}
}
分析：快速排序
待排数据是升序（降序），需要用快速排序来排成降序（升序）的情况下
性能是最差的，可以采用三数取中间法来优化（三数可能相等，但是概率小）
快速排序在最好的情况下是O（NlogN），最坏的情况下是O（N^
2），平均的情况下是O（NlogN）,当然了，它是不稳定的排序。
