加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

两种求一组数中的第 k 大数的算法

发布时间:2020-12-14 03:37:13 所属栏目:大数据 来源:网络整理
导读:我的主力博客:半亩方塘 算法一: 将这组数存入数组,用冒泡排序(或者其他排序方法)将这组数以? 递减 ?顺序进行排序,然后返回位于第 k - 1 位置的数,假如这组数中共有 10 个数的话: #include stdio.h#define MAX_SIZE 10int main(){ int mar[MAX_SIZE];

我的主力博客:半亩方塘

算法一:

将这组数存入数组,用冒泡排序(或者其他排序方法)将这组数以?递减?顺序进行排序,然后返回位于第 k - 1 位置的数,假如这组数中共有 10 个数的话:

#include <stdio.h>
#define MAX_SIZE 10
int main()
{
    int mar[MAX_SIZE];
    printf("输入这 10 个数:n");
    for (int i = 0; i < MAX_SIZE; ++i)  // 将 10 个数输入到数组中
        scanf("%d",&mar[i]);

    // 将这 10 个数用冒泡排序法进行递减排序
    int temp = 0;
    for (int m = 0; m < MAX_SIZE - 1; ++m)
        for (int n = m + 1; n < MAX_SIZE; ++n)
            if (mar[m] < mar[n]) {
                temp = mar[m];
                mar[m] = mar[n];
                mar[n] = temp;
            }

    // 输出第 k - 1 位置的数,即为第 k 大数
    int k = 0;
    printf("输出这组数中的第几大数: ");
    scanf("%d",&k);
    printf("第 %d 大数为: %dn",k,mar[k-1]);

    return 0;
}

在以上程序中,输入的 10 个数为:22 13 25 32 11 68 72 33 42 90,要求输出这组数中的第 5 大数,则最后结果为

第 5 大数为: 33

与期望中一致。

算法二:

将一组数中的?前 k 个数存入数组?,以?递减?顺序将前 k 个数进行排序(冒泡排序或者其他排序方法),然后将余下的数逐个读入数组,如果读入的数小于数组中排序后的第 k 个数则忽略,否则将读入的数存入数组中的正确位置并从数组中挤出一个数,直到将这组数中的所有数都过一遍,结束算法,返回数组中位置 k - 1 的数,即为这组数中的第 k 大数,同样假设这组数中共有 10 个数:

#include <stdio.h>
#define MAX_SIZE 10
int main()
{
    int mar[MAX_SIZE];
    unsigned k = 0;
    printf("需要输出这组数中的第几大数: ");
    scanf("%d",&k);
    printf("输入这组数中的前 %d 个数: ",k);
    for (unsigned i = 0; i < k; ++i)  // 将前 k 个数输入到数组中
        scanf("%d",&mar[i]);

    // 将这 k 个数用冒泡排序法进行递减排序
    int temp = 0;
    for (unsigned m = 0; m < k - 1; ++m)
        for (unsigned n = m + 1; n < k; ++n)
            if (mar[m] < mar[n]) {
                temp = mar[m];
                mar[m] = mar[n];
                mar[n] = temp;
            }

    // 逐个读入这组数中余下的数
    int tmp = 0;
    int cnt = 0;
    printf("逐个读入这组数中余下的数:n");
    for (unsigned j = 0; j < MAX_SIZE - k; ++j) {
        scanf("%d",&tmp);
        cnt = k - 1;    // 将第 k 个数在数组中的下标赋给 cnt
        // 当读入的数大于第 k 个数时,将这个数插入数组中的正确位置并挤出一个数
        if (tmp > mar[cnt]) {
            while (cnt >= 0 && tmp > mar[cnt])   // cnt 大于等于 0 保证下标合理
                --cnt;
            if (cnt >= 0) {   // 如果读入的这个数不比数组中最大的数还大的话
                // 将数组中下标为 cnt + 1 到下标为 k - 2 的所有数均向后移动一个位置
                for (int p = k - 2; p > cnt; --p)
                    mar[p+1] = mar[p];
                mar[cnt+1] = tmp;  // 将读入的这个数插入数组中的正确位置
            }
            else  {      // 如果读入的这个数比数组中所有的数都大的话
                for (int p = k - 2; p >= 0; --p)  // 将数组中所有的数均向后移动一个位置
                    mar[p+1] = mar[p];
                mar[0] = tmp;  // 将读入的这个数放入数组中的第一个位置
            }
        }
    }
    printf("这组数中的第 %d 大数为: %dn",mar[k-1]);

    return 0;
}

在以上程序中,对于:22 13 25 32 11 68 72 33 42 90 这 10 个数,要求输出这组数中的第 5 大数,则最后结果为

这组数中的第 5 大数为: 33

正确,与期望中一致。

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读