腾讯c++开发一面面经

• 确定分界点（左端点，右端点，中间断点）；
• 调整区间（小于选定数放左边，大于选定数放右边）；
• 递归处理左右两个区间；

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

const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if( l >= r) return;
    int mid = q[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i++; while(q[i] < mid);
        do j--; while(q[j] > mid);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    for(int i = 0; i < n; i++) printf("%d ", q[i]);
    return 0;
}

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

const int N = 1e5 + 10;

int n, m;
int h[N], sizen;

void down(int u)
{
    int t = u;
    if( 2 * u <= sizen && h[2* u] < h[t]) t = 2 * u;
    if(2 * u + 1 <= sizen && h[2 * u + 1] < h[t]) t = 2 * u + 1;
    if(u != t)
    {
        swap(h[t], h[u]);
        down(t);
    }
    
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &h[i]);
    sizen = n;
    for(int i = sizen / 2; i > 0; i--) down(i);
    while(m--)
    {
        printf("%d ", h[1]);
        h[1] = h[sizen--];
        down(1);
    }
    return 0;
    
}