资源简介
用分治法求解众数问题,里头用到了快速排序算法
代码片段和文件信息
#include
#include
using namespace std;
struct nInfo//记录可能为众数的值
{
int num;//元素
int sum;//重数
};
struct midNum//记录中点值
{
int num;//中点值
int lPos;//排序后与中点值相同的值的最小坐标
int hPos;//排序后与中点值相同的值的最大坐标
};
struct nInfo num_info;
//快速排序
int Partition(int num[] int low int hight)
{
int pivotkey = num[low];//记下枢轴关键字
while(low < hight)
{
while(low < hight && num[hight] >= pivotkey) hight--;
num[low] = num[hight];
while(low < hight && num[low] <= pivotkey) ++low;
num[hight] = num[low];
}
num[low] = pivotkey;
return low;
}
void QSort(int num[] int low int hight)
{
if(low < hight)
{
int pivotloc = Partition(num low hight);
QSort(num low pivotloc - 1);
QSort(num pivotloc + 1 hight);
}
}
void QSort(int num[] int len)
{
QSort(num 0 len);
}
//取中点值信息
midNum MedianPos(int a[] int low int hight)
{
struct midNum median;
int mid = a[(low + hight + 1) / 2];
int i = low j = hight;
- 上一篇:FSME有限状态机生成器
- 下一篇:三次样条插值算法c语言
评论
共有 条评论