明天面试问到快排可咋办鸭

每天多学一点新算法

stl里的sort不好用吗,为什么非要手写快排呢?
还要冒着退化成n^2的风险
因为听说面试不会写快排十分致命

快排的核心在于设置一个枢纽值
在枢纽值的前半部分的值均小于等于枢纽值,后半部分均大于等于枢纽值
然后分别对前半部分和后半部分再次快排最终得到有序数组

对于我刚刚学习的这个快排,就是对于待排序的数组
取出数组中的第一个值作为枢纽值
然后在数组中找出枢纽值合适的位置

设定first和last两个指针只要,first 小于 last,
从后向前找到第一个小于枢纽值的位置,并把这个值存在first的位置
从前向后找到第一个大于枢纽值的位置,并把这个值存在last的位置
每次赋值的位置一定为空,是枢纽值取出的位置。

最后将枢纽值放在first指针的位置。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<vector>
using namespace std;
vector <int> a;
void Qsort(vector <int> &a,int low,int high)
{
if(low >= high)
return;
int first = low;
int last = high;
int key = a[first]; //枢纽值
while(first < last)
{
while(first < last && a[last] >= key)
--last;
a[first] = a[last];
while(first < last && a[first] <= key)
++first;
a[last] = a[first];
}
a[first] = key;
Qsort(a,low,first-1);
Qsort(a,first+1,high);
}
int main()
{
int n,x;
cin >> n;
for(int i=0;i<n;i++)
{
cin >> x;
a.push_back(x);
}
Qsort(a,0,a.size()-1);
}