資源簡介
用分治法求解眾數問題,里頭用到了快速排序算法
代碼片段和文件信息
#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?????{???
???????while(low?=?pivotkey)?hight--;
???num[low]?=?num[hight];
???while(low? ???num[hight]?=?num[low];
????}??
num[low]?=?pivotkey;
return?low;
}
void?QSort(int?num[]?int?low?int?hight)
{
if(low? {
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有限狀態(tài)機生成器
- 下一篇:三次樣條插值算法c語言
評論
共有 條評論