快速排序是最经典，最常用的高效排序算法之一。快排和归并排序算法一样，采用的是分治的思想。具体步骤如下：
分：从未排序数组中选择一个数组作为关键字，对序列进行一次排序，是的关键词左侧的数的数都比关键字小，右侧的数都比关键字大。
治：不用操作，分完已经是有序的了。
- 平均时间复杂度O(nlogn)
- 空间复杂度：快排空间复杂度主要消耗在递归调用。
最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况
最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况
class Solution
{
int quickSortPartition(vector<int> & array, int start, int end)
{
int pivot = array[start];
int i = start, j = end;
while(i < j)
{
while((array[j] >= pivot) && (i < j)) //这里必须加上 i < j的判断
j--;
while((array[i] < pivot) && (i < j))
i++;
swap(array[i],array[j]);
}
swap(array[start], array[i]);
return i; //最后返回partition的位置
}
void quickSortHelper(vector<int> & array, int start, int end)
{
if(start < end)
{
int mid = quickSortPartition(array,start,end);
quickSortHelper(array,start,mid);
quickSortHelper(array,mid+1,end);
}
return;
}
void quickSort(vector<int> & array)
{
int num = array.size();
quickSortHelper(array,0,array.size()-1);
return;
}
}
