快速排序

快速排序

1. 选取数组的最后一个数为pivot，使数组的前半部分数都比pivot小，后半部分都比pivot大，在前后两个部分再进行排序
2. 快速排序的时间复杂度：

• 平均：O(nlog2n)
• 最有情况：O(nlogn)
• 最坏情况：O(n^2)

可以运行的快速排序代码

#include <iostream>
#include <vector>
using namespace std;

void quick_sort(vector<int>& num, int beg, int end)
{
if(beg>=end)
return;

int key=num[end];
int i=beg;
int j=end;
while(i!=j)
{
while(num[i]<=key && i<j)
++i;
swap(num[i],num[j]);
while(num[j]>=key && i<j)
--j;
swap(num[i],num[j]);
}

quick_sort(num,beg,i-1);
quick_sort(num,i+1,end);
}
int main()
{
vector<int> num{2,1,7,9,3,6,8,5};
quick_sort(num,0,7);

for(auto c:num)
cout<<c<<" ";
cout<<endl;
return 0;
}