(1).  设计一个程序，完成以下功能：

a)    产生一个20个随机数组成的数组，编写快速排序算法完成这些数从小到大排序，并将排序后结果输出；（最好能打印每轮排序结果）

b)    输入其中任何一个数字，编写折半查找算法查找该元素在排序后数组中的位置；

c)     利用分治法求解这组数中的top n元素，既是这组数中第n（n<20）大的数据。

调用标准函数行不？

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

int main( void )
{
    int arr[20];

    // a) 产生一个20个随机数组成的数组，编写快速排序算法完成这些数从小到大排序，并将排序后结果输出
    {
        std::generate( std::begin(arr), std::end(arr), [mt=std::mt19937{std::random_device{}()},dis=std::uniform_int_distribution<>(0,99)]()mutable{return dis(mt);} );
        std::sort( std::begin(arr), std::end(arr) );
        std::copy( std::begin(arr), std::end(arr), std::ostream_iterator<decltype(*arr)>(std::cout," ") );
        std::cout << std::endl;
    }

    // b) 输入其中任何一个数字，编写折半查找算法查找该元素在排序后数组中的位置
    {
        std::remove_cvref_t<decltype(*arr)> n;
        if( !(std::cin>>n) )
            return 1;
        auto p = std::lower_bound( std::begin(arr), std::end(arr), n );
        if( p==std::end(arr) || *p!=n )
            std::cout << "没发现.\n";
        else
            std::cout << std::distance(std::begin(arr),p) << std::endl;
    }

    // c) 利用分治法求解这组数中的top n元素，既是这组数中第n（n<20）大的数据
    // 这就奇怪了呀，数组已经排序好了，第i大元素就是 arr[20-1-i] 呀
    // 好吧，假设我就当数组没排序过
    {
        size_t n;
        if( !(std::cin>>n) || n>=std::size(arr) )
            return 1;
        std::nth_element( std::begin(arr), std::next(std::begin(arr),std::size(arr)-1-n), std::end(arr) );
        std::cout << arr[std::size(arr)-1-n] << std::endl;
    }
}

大哥，你这个我看的很蒙，没看懂啊

先讲随机数

C语言的随机数函数是 srand / rand
srand 的问题是，用什么作为随机种子？如果种子并不随机的话，那么随机序列就完全确定了。
通常，使用当前时间作为随机种子。然而有两个缺点：第一，在足够短的时间内，当前时间是不变的；第二，当前时间是可以被人预估或预设的。
rand 的问题是，它的随机数范围绝大多数时并不是用户需要的范围，需要经过复杂的缩放，。另外，它只能产生均匀分布的随机数。

C++的解决办法是
提供多种随机数算法，有的算法速度快，有的算法效果好，……。比如常用的 MT19937伪随机数生成算法。
提供一个真随机数，也就是 std::random_device。一般只在关键地方（比如作随机算法的种子）才使用它，因为它很珍贵，一旦耗尽需要很长时间才能新生。
提供多种分布器，将随机数分布到指定范围，及不同的几率分布。比如 均匀分布、正态分布、……。

示例，以下代码产生10组，每组20个元素，元素值在[0,99]范围内的序列

#include <iostream>
#include <algorithm>
#include <random>

int main( void )
{
    std::mt19937 gen{ std::random_device{}() };
    std::uniform_int_distribution<> dis(0,99);

    for( size_t cnt=10; cnt--; )
    {
        int a[20];
        for( auto& v : a )
            v = dis(gen);
        
        for( size_t i=0; i!=std::size(a); ++i )
            printf( "%d%c", a[i], " \n"[i+1==std::size(a)] );
    }
    return 0;
}

一种可能的输出是

61 36 85 27 78 19 85 28 33 97 87 34 47 38 34 89 3 12 74 98
77 28 29 48 16 6 38 80 44 67 54 55 92 61 40 31 6 98 53 35
78 71 20 55 62 39 89 72 21 32 82 53 7 36 49 50 72 8 96 17
42 88 47 12 45 31 23 2 8 93 42 17 89 92 7 35 99 98 13 0
20 24 37 86 43 34 91 24 56 10 30 39 40 38 82 11 53 91 64 82
22 91 83 65 42 92 68 83 10 49 50 3 71 65 46 60 52 87 14 9
47 94 47 8 99 7 14 78 50 43 2 98 19 69 51 55 54 98 33 11
9 89 53 52 63 93 69 29 28 70 6 33 72 78 14 43 21 9 61 42
46 64 69 20 72 28 96 92 46 81 57 0 69 87 7 8 62 17 81 24
33 86 0 42 48 62 91 53 24 58 24 56 90 86 38 80 83 5 58 16

------ 有时间再讲其它的吧，蛮耗费时间的 ------

[此贴子已经被作者于2020-12-24 10:41编辑过]

再讲排序算法中最常用的快速排序

快速排序，在C语言中有 qsort，比较难用，且因为比较器是个无状态的函数，所以无法定制
在C++语言中有 std::sort，它的主体算法也是快速排序，但不仅仅是快速排序，因为它会根据情况自动切换成其它排序算法

对你的这道题目来说，如果你的老师禁止你使用标准库函数，要你手写快速排序算法的话，那也简单，例如

void quicksort( int a[], size_t len )
{
    if( len <= 1 )
        return;

    int key = a[0];
    size_t i=0, j=len-1;
    for( ; i!=j; )
    {
        for( ; i!=j && !(a[j]<key); --j );
        a[i] = a[j];

        for( ; i!=j && !(key<a[i]); ++i );
        a[j] = a[i];
    }
    a[i] = key;
    quicksort( a, i );
    quicksort( a+i+1, len-i-1 );
}

既然有了快速排序，那顺便将你题目中最后一个问题“第k大”解决掉

快速排序是每一个元素都排，而“第k大”只需要确保 k位之前的数都小于等于第k个数 且 k位之后的数都大于等于第k个数 就行。
也就是只需要在 快速排序 算法中，只排序k所在的那半段就可以了。
在快排算法的基础上更改以下最后的递归，也就是

void nth_element( int a[], size_t len, size_t nth )
{
    if( len <= 1 )
        return;

    int key = a[0];
    size_t i=0, j=len-1;
    for( ; i!=j; )
    {
        for( ; i!=j && !(a[j]<key); --j );
        a[i] = a[j];

        for( ; i!=j && !(key<a[i]); ++i );
        a[j] = a[i];
    }
    a[i] = key;
    if( nth < i )
        return nth_element(a, i, nth);
    if( nth > i )
        return nth_element(a+i+1, len-i-1, nth-i-1);
}

顺便说一下，C++标准库有求“第K大”的函数，名字叫 std::nth_element

折半查找算法那是最简单的算法之一了，不多说

// 返回第一个大于等于value的元素的下标
size_t lower_bound( const int a[], size_t len, int value )
{
    const int* p = a;
    for( size_t n=len; n>0; )
    {
        if( p[n/2] < value )
        {
            p += n/2+1;
            n -= n/2+1;
        }
        else
            n /= 2;
    }
    return p-a;
}

顺便说一下，
C标准库的折半查找函数名 bsearch
C++标准库的折半查找函数名 std::binary_search / std::equal_range / std::lower_bound / std::upper_bound

------ 结束，全剧终 ------