【基础算法篇】快速排序笔记

一、前言

从这里开始会记录y总算法基础课笔记，初心是为了让自己反顾看，提升代码能力。只记录实现思路和ac代码

二、 算法思路

快排属于分治算法，分治算法都有三步：

1. 分成子问题
2. 递归处理子问题
3. 子问题合并

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)
    &#123;
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    &#125;
    //第二步：递归处理子问题
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
    //第三步：子问题合并.快排这一步不需要操作，但归并排序的核心在这一步骤
&#125;

三 、AC代码

#include <iostream>

using namespace std;
const int N = 100010;
int q[N];
int n;

void quick_sort(int q[], int l, int r)
&#123;
    if(l >= r) return;
    int x = q[(l + r + 1) / 2], i = l - 1, j = r + 1;
    while(i < j)
    &#123;
        do i ++; while(q[i] < x);
        do j --; while(q[j] > x);
        if(i < j)
            swap(q[i], q[j]);
    &#125;

    quick_sort(q, l, i - 1);
    quick_sort(q, i, r);
&#125;

int main()
&#123;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> q[i];
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i ++ ) cout << q[i] << " "; 
    return 0;
&#125;

例题 第k个数

题目

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

地址

https://www.acwing.com/problem/content/description/788/

算法思路

1. 快排的每一趟，数轴的左边都会是 <= x 的， 右边都是 >= x 的。
2. 初始化时，总元素个数是是 s1 = j - l + 1,
3. 如果k <= s1 的话，那么下次递归的区间就是左边，否则右边。
4. 直到 l == r 时返回q[l]。

AC代码

#include <iostream>

using namespace std;
const int N = 100010;
int q[N];
int n, k;

int quick_sort_k(int l, int r, int k)
&#123;
    if(l == r) return q[l];
    int x = q[l], i = l - 1, j = r + 1;
    while(i < j)
    &#123;
        while(q[++ i] < x);
        while(q[-- j] > x);
        if(i < j) swap(q[i], q[j]);
    &#125;

    int s1 = j - l + 1;
    if(k <= s1) return quick_sort_k(l, j, k); // 左半边
    else return quick_sort_k(j + 1, r, k - s1);
&#125;

int main()
&#123;
    cin >> n >> k;
    for (int i = 0; i < n; i ++ ) cin >> q[i];
    cout << quick_sort_k(0, n - 1, k) << endl; 
    return 0;
&#125;