两种求一组数中的第 k 大数的算法
我的主力博客:半亩方塘算法一:将这组数存入数组,用冒泡排序(或者其他排序方法)将这组数以?递减?顺序进行排序,然后返回位于第 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 正确,与期望中一致。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |