快速排序算法

快速排序

方法思想:分治法

将Array[l—r]分为Array[l-x]和Arrar[x-r](l和r为左右边界)

  • 左边的数组全部小于等于x
  • 右边的数组全部大于等于x
  • x只是一个参考值,随意

步骤:

  1. 确定分界点:q[l],q[(l+r)/2],q[r] (随便选一个作为分界点)
  2. ⭐调整区间

20220108113406

使左边的区间全部小于等于x,右边的区间全部大于等于x

只需要保证区间≤x 或者 ≥x 就行,区间内部的顺序不需要管

  1. 递归处理左右两段区间

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void quick_sort(int q[], int l, int r)
{
//递归的终止情况
if(l >= r) return;
//第一步:分成子问题
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while(i < j)
{
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
//第二步:递归处理子问题
quick_sort(q, l, j), quick_sort(q, j + 1, r);
//l---j -x- i---r
//第三步:子问题合并.快排这一步不需要操作,但归并排序的核心在这一步骤
}


题目

最小K个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
quick_sorr(arr,0,arr.size()-1);
vector<int> temp;
temp.assign(arr.begin(),arr.begin()+k);
return temp;
}
private:
void quick_sorr(vector<int>& arr,int l,int r){
if(l>=r) return;
int i=l-1,j=r+1,x=arr[(l + r) >> 1];
while(i<j){
do i++;while(arr[i]<x);
do j--;while(x<arr[j]);
if(i<j) swap(arr[i],arr[j]);
}
quick_sorr(arr,l,j),quick_sorr(arr,j+1,r);
}
};

最接近原点的K个点

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
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
quick_sorr(points,0,points.size()-1);

return {points.begin(),points.begin()+k};
}

private:
void quick_sorr(vector<vector<int>>& a, int l,int r){
if(l >= r) return ;

int i = l - 1,j = r + 1;
int sum = a[(l + r) >> 1][0]*a[(l + r) >> 1][0]+a[(l + r) >> 1][1]*a[(l + r) >> 1][1];
while(i < j){
do i++; while(a[i][0] * a[i][0] + a[i][1] * a[i][1] < sum);
do j--; while(a[j][0] * a[j][0] + a[j][1] * a[j][1] > sum);
if(i < j) swap(a[i],a[j]);
}

quick_sorr(a,l,j);
quick_sorr(a,j+1,r);
}
};