响应firetoucher (风焱)版主号召，先来献丑啦。【计算中位数】

Question

前两天要计算中位数，搜了一通，只有算法，没有程序，没办法偷懒啦，于是自己写了一个，响应风焱斑竹的号召，贡献出来，希望下次有兄弟需要的时候拿来用就是啦。中位数的定义和计算方法网上到处都是。
另外问一下，这些有固定算法的代码大家都是去哪里找，我怎么就找不到呢？
希望风焱斑竹多搜集一些做成chm的东东，看着方便：）

Answer 1

{*********************************************************}
{                                                         }
{                      计算中位数                         }
{                                                         }
{             Copyright (c) 2003 eastphoenix              }
{                  [email protected]                    }
{*********************************************************}unit DL_Class_Median;interfaceuses Classes, SysUtils;type{ 组的结构体 }  PGroup = ^Group;
  Group = record
    Max:Extended;   //所在组的上限
    Min:Extended;   //所在组的下限
    f:integer;      //所在组的频数
    //Next:PGroup;   //下一个结点的地址
  end;{ 数据的结构体 }  PNumber = ^Number;
  Number = record
    Num:Extended;
  end;{ 整个中位数的类 }  TMedian = class
  private
    Nums:TList;         //用于统计中位数的数据
    Groups:TList;       //组链表
    GroupCount:integer; //组数（想分多少组）
    LittleCount:integer;//小样本的标准（多少样本算小样本）
    GroupInterval:Extended;     //组距
    LocalGroupIndex:integer;    //本组的索引值
    procedure Sort;     //给要统计的数据排序
    procedure QuickSort(iLo,iHi:integer);//快速排序，基本数据是私有变量Nums
    procedure SelectSort; //选择排序
    procedure SetGroupInterval;       //设置组距
    procedure MakeGroup;//划分组
    procedure SetLocalGroupIndex;    //设置本组的索引值
    function GetTotalFLessThan(const GroupIndex:integer):integer;        //取得小于本组的各组累计频数
  public
    procedure Add(const Num:Extended);      //添加数据
    function GetMedian:Extended;  //取得中位数
    constructor Create(const newGroupCount,newLittleCount:integer);
    destructor Destroy;override;
  end;implementation{ TMedian }procedure TMedian.Add(const Num: Extended);
var
  Number:PNumber;
begin
  New(Number);
  Number.Num := Num;
  self.Nums.Add(Number);
end;constructor TMedian.Create(const newGroupCount,newLittleCount: integer);
begin
  inherited Create;
  self.Nums := TList.Create;
  self.Groups := TList.Create;
  self.GroupCount := newGroupCount;
  self.LittleCount := newLittleCount;
end;destructor TMedian.Destroy;
var
  Group:PGroup;
  Number:PNumber;
  i:integer;
begin
  for i := 0 to self.Groups.Count - 1 do
  begin
    Group := self.Groups.Items[i];
    Dispose(Group);
  end;
  self.Groups.Free;
  for i := 0 to self.Nums.Count - 1 do
  begin
    Number := self.Nums.Items[i];
    Dispose(Number);
  end;
  self.Nums.Free;
  inherited;
end;//设置组距
procedure TMedian.SetGroupInterval;
var
  i,j:Extended;
  Number:PNumber;
begin
  Number := self.Nums.First;
  i := Number^.Num;
  Number := self.Nums.Last;
  j := Number^.Num;
  self.GroupInterval := (j - i)/self.GroupCount;
end;//设置本组的索引值，组内频数大于N/2，或累计频数大于N/2即为本组
procedure TMedian.SetLocalGroupIndex;
var
  Group:PGroup;
  i:integer;
  HafeN:integer;
begin
  HafeN := self.Nums.Count div 2;
  for i := 0 to self.GroupCount - 1 do
  begin
    Group := self.Groups.Items[i];
    if Group^.f >= HafeN then
    begin
      self.LocalGroupIndex := i;
      exit;
    end;
  end;
  for i := 0 to self.GroupCount - 1 do
  begin
    if self.GetTotalFLessThan(i) >= HafeN then
    begin
      self.LocalGroupIndex := i;
      exit;
    end;
  end;
end;function TMedian.GetMedian: Extended;
var
  HalfN:integer;
  X1,X2:PNumber;
  Group:PGroup;
begin
  //先给输入的数据排序
  self.Sort;
  //样本数量少时，直接取中位数
  if self.Nums.Count <= self.LittleCount then
  begin
    //样本数量为偶数时的算法
    if (self.Nums.Count mod 2) = 0 then
    begin
      HalfN := (self.Nums.Count div 2) - 1;
      X1 := self.Nums.Items[HalfN];
      X2 := self.Nums.Items[HalfN + 1];
      result := (X1^.Num + X2^.Num)/2;
    end
    //样本数量为奇数时的算法
    else
    begin
      HalfN := ((self.Nums.Count + 1) div 2) - 1;
      X1 := self.Nums.Items[HalfN];
      result := X1^.Num;
    end;
  end
  //样本数量多时，另外计算中位数
  else
  begin
    //划分组距
    self.SetGroupInterval;
    //设置组
    self.MakeGroup;
    //设置本组索引值
    self.SetLocalGroupIndex;
    HalfN := self.LocalGroupIndex;
    Group := self.Groups.Items[HalfN];
    result := Group^.Min + (self.GroupInterval / Group^.f) *
              (self.Nums.Count / 2 - self.GetTotalFLessThan(HalfN - 1));
  end;
end;//取某组的累计频数
function TMedian.GetTotalFLessThan(const GroupIndex:integer): integer;
var
  Group:PGroup;
  i:integer;
begin
  result := 0;
  for i := 0 to GroupIndex do
  begin
    Group := self.Groups.Items[i];
    result := result + Group^.f;
  end;
end;//划分组
procedure TMedian.MakeGroup;
var
  Group:PGroup;
  Number:PNumber;
  i,j:integer;
  Limit:Extended;
begin
  //取最小值
  Number := self.Nums.First;
  Limit := Number^.Num;
  //设置每组的上下限
  for i := 0 to self.GroupCount - 1 do
  begin
    new(Group);
    Group^.Min := Limit;
    Limit := Limit + self.GroupInterval;
    Group^.Max := Limit;
    Group^.f := 0;
    self.Groups.Add(Group);
  end;
  //设置组频数，i为组的记数，j为数据的记数
  i := 0;
  j := 0;
  while (i < self.GroupCount) and (j < self.Nums.Count) do
  begin
    Group := self.Groups.Items[i];
    Number := self.Nums.Items[j];
    //如果数据在当前组内，当前组的频数增一，否则当前组向后移一位
    if (Number^.Num >= Group^.Min) and (Number^.Num < Group^.Max) then
    begin
      Group^.f := Group^.f + 1;
      j := j + 1;
    end
    else
      i := i + 1;
  end; 
end;//快速排序有问题，所以用了选择排序法
procedure TMedian.Sort;
begin
  self.SelectSort;
end;//快速排序法，不过有问题，排的不对
procedure TMedian.QuickSort(iLo, iHi: integer);
var
  Lo, Hi:Integer;
  LoNumber,HiNumber,MidNumber:PNumber;
  T:Extended;
begin
  Lo := iLo;
  Hi := iHi;
  MidNumber := self.Nums.Items[(Lo + Hi) div 2];
  repeat
    LoNumber := self.Nums.Items[Lo];
    HiNumber := self.Nums.Items[Hi];
    while LoNumber^.Num < MidNumber^.Num do
    begin
      Inc(Lo);
      LoNumber := self.Nums.Items[Lo];
    end;
    while HiNumber^.Num > MidNumber^.Num do
    begin
      Dec(Hi);
      HiNumber := self.Nums.Items[Hi];
    end;
    if Lo <= Hi then
    begin
      T := LoNumber^.Num;
      LoNumber^.Num := HiNumber^.Num;
      HiNumber^.Num := T;
      Inc(Lo);
      Dec(Hi);
    end;
  until Lo > Hi;
  if Hi > iLo then self.QuickSort(iLo,Hi);
  if Lo < iHi then self.QuickSort(Lo,iHi);
end;//选择法排序
procedure TMedian.SelectSort;
var
  INumber,JNumber:PNumber;
  T:Extended;
  i,j:integer;
begin
  for i := 0 to self.Nums.Count - 2 do
    for j := self.Nums.Count - 1 downto i + 1 do
    begin
      INumber := self.Nums.Items[i];
      JNumber := self.Nums.Items[j];
      if INumber^.Num > JNumber^.Num then
      begin
        T := INumber^.Num;
        INumber^.Num := JNumber^.Num;
        JNumber^.Num := T;
      end;
    end;
end;end.

Answer 2

快速排序法有问题，我可是照着Delphi的Demo排的，哪位给改一下：）

Answer 3

555555……没看懂，好伤心啊：）中位数是一个统计学上的概念（其实我也是赶鸭子上架，上学时数理统计差点挂了，不知大家是不是和我差不多，呵呵），有现成的公式和计算方法，这种东东没有什么变化，一次写到处用，肯定有人写过，可是不知到哪里找现成的，抛块砖，看能不能把玉引出来，还有很多统计方法，没有用到的时候我是懒得写啊。下面是一个介绍的网址，有检测数据的，不过那个测试样本有157个，够写测试数据的啦：）
http://www.windrug.com/pic/30/11/23/011.htm

Answer 4

用法还用说吗？
说说吧，创建类时设置两个参数，一个是想分多少组统计，一个是小样本数量的界定（样本数量太少时计算方法不一样，多少算少呢？你自己定），然后把数据一个一个add进去，调用GetMedian就算出来啦。

Answer 5

谢谢支持,不过现在没有时间上网,只能up一下:)
关于算法的详细讨论,强烈建议楼主看kruith的the art of computer programming书店有卖,好像第三卷就是讲排序了,几十年了,没有比那个更经典更权威的了!

Answer 6

谢谢斑竹，排序么，数据结构我有学。
刚发现个问题
Number.Num := 1和Number^.Num := 1有什么区别，是不是都可以啊，Delphi基础不好，见笑啦。
天才弟弟：苹果换名字，姓不换啊，青苹果三个字可是打死也不换，你看小小换的一塌糊涂。