资源简介

用分治法求解众数问题,里头用到了快速排序算法

资源截图

代码片段和文件信息

#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;

评论

共有 条评论