Notes-QuickSort

本文最后更新于:2020年10月10日 中午

思路

快排基本思路应该就是二分+递归,从两侧同时(实则先从右往左)往中间找,同时和参变量对比,发现位置颠倒后交换位置,然后通过二分将其一块一块的分割开,直到分割到一个元素位置,即完成了快排。

代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>

using namespace std;

int a[101],n;

void quicksort(int left,int right)
{
int i,j,t,temp;//temp存基准数
if(left>right) return;

temp=a[left];
i=left;
j=right;
while(i!=j)
{
while(a[j]>=temp && i<j) j--;
while(a[i]<=temp && i<j) i++;

if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}

a[left]=a[i];
a[i]=temp;

quicksort(left, i-1);
quicksort(i+1,right);
return;
}

int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
quicksort(1,n);

for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}

return 0;
}

总结

快排应该是最常用的模板了,时间复杂度也比较理想

PS.致敬一波快排的提出者东尼·霍尔(C. A. R. Hoare)


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!