菜学C++ Day42

菜学C++ Day42

分治法求众数和重数（众数的数量）

• 排序：数组为有序数列（以升序为例）
• 将众数初始化为中间数
• 寻找该众数出现的位置，从左向右第一次出现位置为L，从右向左第一次出现位置为r，重数为r-L+1
• 判断：倘若左边数的数目<上述重数，则左边不可能有比当前中间数更大的重数，不满足条件，不搜索；右边同理。
• 当判断上述数量满足条件时，将上一次中间数左边的整个作为一个新数组进行递归；右边同理

缺点：通过全局变量存储的众数和重数，重点是求出了重数，然后存储了该重数的众数，但有可能有其他重数相同的众数被遗漏了，最后只有一个众数的结果 

如果要求所有的众数，可以再遍历一次数组求出

代码由于是最近的作业就先不放啦，以后补上。

还有就是排序：冒泡排序、快速排序、选择排序我其实还比较模糊，明天就分析一下它们吧