快速排序
快速排序
平均运行时间：
最佳情形：
最坏情形：
实现方法：快速排序也是一种分治的递归算法，实现步骤如下：
1、如果S中元素个数是0或1，则返回
2、取S中任一元素v，称之为枢纽元（pivot），通常取S中开始、结束、中间3个值的中值。
3、将S-{v}(S中其余元素}划分成两个不相交的集合：
4、返回{quicksort(S1)，后跟v，继而{quicksort(S2)}。
注：S中元素个数通常在10个以上，不然最好用插入排序。
图解：
分割策略：
初始数组，枢纽元为6
在分割阶段要做的就是把所有小元素移到数组的的左右，大元素移到数组的右边。大小是相对于枢纽元而言。
当i在j的左边时，我们将i右移，移过那些小于枢纽元的元素，并将j左移，移过那些大于枢纽元的元素。当i和j停止时， i指向一个大元素而j指向一个小元素。如果i在j的左边，那么将这两个元素互换，其效果是把一个大元素推向右边而把 小元素推向左边。
交换i和j 指向的元素，重复该过程直到i和j 彼此交错
此时i和j 已经交错，故不再交换。分割的最后一步是将枢纽元与i 所指向的元素交换。
程序实现：
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////快速排序/////////////////////////////////////////////////////////////
template<typename Object>
void quickSort(vector <Object> &a)
{
quickSort(a, 0, a.size() - 1);
}
template<typename Object>
void quickSort(vector<Object> &a, int left, int right)
{
if (left + 10 < right)
{
Object pivot = (median3(a, left, right));
//begin partitioning
int i = left, j = right - 1;
for (;;)
{
while (a[++i] < pivot) {};
while (pivot < a[--j]) {};
if (i < j)
swap(a[++i], a[--j]);
else
break;
}
swap(a[i], a[right - 1]);//Restore pivot
quickSort(a, left, i - 1); //sort small elements
quickSort(a, i + 1, right); //sort large elements
}
else
insertionSort(a);
}
/*选取枢纽元*/
template<typename Object>
const Object median3(vector<Object> &a, int left, int right)
{
int center = (left + right) / 2;
if (a[center] < a[left])
swap(a[center], a[left]);
if (a[left] > a[right])
swap(a[left], a[right]);
if (a[center] > a[right])
swap(a[center], a[right]);
swap(a[center], a[right - 1]);
return a[right - 1];
}