常用算法-快速排序

快速排序

时间复杂度：O(Nlog2N)
空间复杂度：O(N)
原理：
以第一个数为基数，前后两端分别记游标i,j,后端的游标j向前移动，大于基准数字继续j–,小于基准数字停下来，前端的游标i向后移动，小于基准数字继续i++,大于基准数字停下来，判断j>i则交换数字，否则推出循环
核心代码：
递归
分片区
int partition(vector &list,int start,int end)
{
int base = start;
while(start < end)
{
while(start < end&&list[end] >= list[base]) end–;
while(start < end&&list[start] <= list[base]) start++;
if(start < end) {swap(list[start],list[end]);}
}
swap(list[base],list[start]);
return start;
}
void quick(vector &list,int start,int end)
{
int base = partition(list,start,end);
quick(list,start,base-1);
quick(list,base+1,end);
}