all_sort.~h

数据结构作业。 排序和数据检索比较演示程序。 图形界面。

//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Unit5_sort.h"

//---------------------------------------------------------------------------
#define MaxAuto 40000
//---------------------------------------------------------------------------
  inline void swap(int &a,int &b)
  {
    int t=a;a=b;b=t;
  }

struct toget
{
  int dat,loc;
} Sdata[MaxAuto];


void __fastcall TForm1::StraightInsertSort(int data[],int range)
{
  int x,i,j,k;
  for (i=1;i<range;i++)
  {
    x=data[i];
    for (j=0;j<i;j++)
      if (data[j]>x)
        break;
    for (k=i;k>j;k--)
      data[k]=data[k-1];
    data[k]=x;
  }
}
//---------------------------------------------------------------------------
void __fastcall TForm1::BinaryInsertSort(int data[],int range)
{
  int x,i,j,k,low,high,mid;
  for (i=1;i<range;i++)
  {
    x=data[i];
    low=0;
    high=i-1;
    while (low<high)
    {
      mid=(low+high)/2;
      if (x>data[mid])
        low=mid+1;
      else
        high=mid;
    }
    for (k=i;k>high;k--)
      data[k]=data[k-1];
    data[k]=x;
  }
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ShellSort(int data[],int range)
{

}
//---------------------------------------------------------------------------
void __fastcall TForm1::BubbleSort(int data[],int range)
{
  int i,j;
  for (i=0;i<range;i++)
    for (j=range-1;j>i;j--)
      if (data[j]<data[j-1])
        swap(data[j],data[j-1]);
}
//---------------------------------------------------------------------------

  int cmp(const void *a,const void *b)
  {
    int p=*(int *)a,q=*(int *)b;
    if (p<q)
      return -1;
    if (p>q)
      return 1;
    return 0;
  }

void __fastcall TForm1::QuickSort(int data[],int range)
{
  qsort(data,range,sizeof(int),cmp);
}
//---------------------------------------------------------------------------

  int qslist(int a[],int l,int h)
  {
    int i,x,j,t;
    i=l;
    x=a[l];

    for (j=l+1;j<h;j++)
      if (a[j]<x)
      {
        i++;
        if (i!=j)
        {
          swap(a[i],a[j]);
        }
      }

    swap(a[i],a[l]);
    return i;
  }
  void qst(int data[],int l,int h)
  {
    if (l<h-1)
    {
      int p=qslist(data,l,h);
      qst(data,l,p);
      qst(data,p+1,h);
    }
  }

void __fastcall TForm1::Quick2Sort(int data[],int range)
{
  qst(data,0,range);
}
//---------------------------------------------------------------------------

void __fastcall TForm1::StraightElectSort(int data[],int range)
{
  int i,j;
  for (i=0;i<range;i++)
    for (j=i+1;j<range;j++)
      if (data[i]>data[j])
        swap(data[i],data[j]);
}
//---------------------------------------------------------------------------

  void slpdown(int rp[],int r,int range)
  {
    while (r<range/2)
    {
      if (r*2+2==range)
      {
        if (rp[r]<=rp[r*2+1])
          swap(rp[r],rp[r*2+1]);
        r*=2; r++;
      }
      else
      {
        if (rp[r]<rp[r*2+1] &&
            rp[r*2+1]>=rp[r*2+2])
        {
          swap(rp[r],rp[r*2+1]);
          r*=2; r+=1;
        }
        else
        if (rp[r]<rp[r*2+2] &&
            rp[r*2+2]>=rp[r*2+1])
        {
          swap(rp[r],rp[r*2+2]);
          r*=2; r+=2;
        }
        else
          if (rp[r]>=rp[r*2+2] &&
              rp[r]>=rp[r*2+1])
            return;
      }
    }
  }

void __fastcall TForm1::HeapSort(int data[],int range)
{
  int i;
  for (i=range/2-1;i>=0;i--)
    slpdown(data,i,range);


  for (i=range-1;i>0;i--)
  {
    swap(data[i],data[0]);
    slpdown(data,0,i);
  }
}
//---------------------------------------------------------------------------

  void merge(int a[],int l, int w, int h)
  {
    int z,v,u,i,b[MaxAuto+1];
    z=h;
    v=w+1;
    u=h-l+1;
    while (u)
    {
      if ((a[w]>a[h] || h==v-1) && w>=l)
      {
        b[u]=a[w];
        u--;
        w--;
      }
      else
      {
        b[u]=a[h];
        u--;
        h--;
      }
    }
    memcpy(a+l,b+1,sizeof(int)*(z-l+1));
  }
  void mst(int data[],int l, int h)
  {
    if (l<h)
    {
      int w=(l+h)/2;
      mst(data,l,w);
      mst(data,w+1,h);
      merge(data,l,w,h);
    }
  }
//---------------------------------------------------------------------------

void __fastcall TForm1::MergeSort(int data[],int range)
{
  mst(data,0,range);
}
//---------------------------------------------------------------------------

int  __fastcall TForm1::StrtSearch(AnsiString s,int data[],int range)
{
  int i;
  for (i=0;i<range;i++)
    if (AnsiString(data[i])==s)
      break;
  if (i<range)
    return i;
  else
    return -1;
}
//---------------------------------------------------------------------------

  int cmp1(void const *a,void const *b)
  {
    toget p1=*(toget *)a,p2=*(toget *)b;
    if (p1.dat>p2.dat)
      return 1;
    if (p1.dat<p2.dat)
      return -1;
    return 0;
  }

  int trans(char s[])
  {
    unsigned int i;
    int x=0;
    for (i=0;i<strlen(s);i++)
    {
      x=x*10+s[i]-'0';
    }
    return x;
  }
int  __fastcall TForm1::BinaSearch(AnsiString s,int data[],int range)
{

  int i;
  for (i=0;i<range;i++)
  {
    Sdata[i].dat=data[i];
    Sdata[i].loc=i;
  }
  int x=trans(s.c_str());

  qsort(Sdata,range,sizeof(toget),cmp1);

  int low,high,mid;
  low=0;
  high=range-1;

  while (low<=high)
  {
    mid=(low+high)/2;
    if (x==Sdata[mid].dat)
      break;
    if (x>Sdata[mid].dat)
      low=mid+1;
    else
      high=mid-1;
  }
  if (low<=high)
    return Sdata[mid].loc;
  return -1;


}
//---------------------------------------------------------------------------

int  __fastcall TForm1::PartSearch(AnsiString s,int data[],int range)
{
  return -1;
}
//---------------------------------------------------------------------------