NOIP2008普及组初赛 阅读程序 第4题《找第k大》

快排

题目过长，不在截图放原题目了，直接放上，带有注释和cout大法的代码，然后加以解释。

#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

int a[1000001], n, ans = -1;
int m;

void swap(int &a, int &b)
{
    int c;
    c = a, a = b, b = c;
}

int FindKth(int left, int right, int n)
{
    // FindKth的参数，还有当前数组的状态 
    cout << endl <<"进入一个新的FindKth函数" << endl; 
    cout << "参数：left "<< left << " --- right " << right << " --- n "  << n << endl;
    for (int i = 1; i <= m; i++) cout << a[i] << ' ';
    puts("");

    int tmp, value, i, j;
    if (left == right) return left;

    tmp = rand() % (right - left) + left;
    swap(a[tmp], a[left]);
    value = a[left];   //选取枢纽   //1空

    //cout枢纽 
    cout << endl << "tmp --- " << tmp << " value --- " << value << endl;  

    //从大到小排列，找第n大的 
    i = left, j = right;
    while (i < j)
    {
        //看一下当前的下标情况 
        cout << "进入新的一趟while i --- " << i <<  " j --- " << j << endl;

        while (i < j && a[j] < value)    //2空  右边是小于value的 
        {
            j--;
        } 
        if (i < j) a[i] = a[j], i++;         //把大于等于value的值放在i上 
        else break;

        while (i < j && a[i] > value)   //3空   左边是大于value的 
            i++;

        if (i < j) a[j] = a[i], j--;        //把小于等于value的值放在j上 
        else break;
    }
    a[i] = value; //4空
        cout << "i --- " << i << endl;

    //cout一下交换后的a[]数组 
    cout << "交换后的a[]数组：";
    for (int i = 1; i <= m; i++) cout << a[i] << ' ';
    puts("");

    if (i < n) return FindKth(i + 1, right, n);
    if (i > n) return FindKth(left, i - 1 , n);

    //最后返回目标下标 
    cout << "return i --- "<< i << endl;
    return i; 
}

int main()
{
    freopen("kth.in", "r", stdin);
//  int m = 1000000;
    m = 10;

    int i;
    for (i = 1; i <= m; i++) cin >> a[i];

    cin >> n;
    ans = FindKth(1, m, n);  //ans为第n大的位置下标 

    cout << a[ans];

    return 0;
}

我们用这个代码执行一下，下图是输入文件

输出结果如下，找到了第4大的数字，值为17

加入一些解释说明，黄色的字体

进行模拟之后，我们看到了结果，但是考试的时候，是没有那么长的时间用来人脑模拟计算机。所以，要换个角度思考。

回顾一下快排的模板，很类似很类似。题目中去枢纽取的是rand()，大佬的模板枢纽取的是l + r >> 1。道理是一样的。快排的难点是找分界点，往下递归。

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);
}