首页 > 代码库 > 各种排序算法的一个类

各种排序算法的一个类

2024-07-05 04:59:34   226人阅读

#include<iostream>
#define MAX 100
using namespace std;
class Sample
{
     int a[MAX];
      int b[MAX];
     int n;
     friend class Process;
   public:
         Sample(){n=0;}
};
class Process
{
   private:
     int s_psort(Sample &s,int first,int end);
     void sift(int k,int m,Sample &s);
   public:
       void getdata(Sample &s);
       void s_isort(Sample &s);
      void s_ssort(Sample &s);
      void s_bsort(Sample &s);
      void s_qsort(Sample &s,int first,int end);
      void s_selsort(Sample &s);
      void s_hsort(Sample &s);
       void disp(Sample &s);
};
void Process::s_isort(Sample &s)
{
int temp;
for(int i=1;i<s.n;i++)
{
temp=s.a[i];
for(int j=i-1;j>=0&&temp<s.a[j];j--)
   s.a[j+1]=s.a[j];
s.a[j+1]=temp;
}
}
void Process::s_ssort(Sample &s)
{
    int temp;
    for(int d=s.n/2;d>0;d=d/2)
    {
       for(int i=d;i<s.n;i++)
       {
         temp=s.a[i];
         for(int j=i-d;j>=0&&temp<s.a[j];j=j-d)
         s.a[j+d]=s.a[j];
         s.a[j+d]=temp;
       }
    }
}
void Process::s_bsort(Sample &s)
{
 
    int temp;
for(int i=0;i<s.n-1;i++)
for(int j=i+1;j<s.n;j++)
if(s.a[i]>s.a[j])
{
temp=s.a[i];
s.a[i]=s.a[j];
s.a[j]=temp;
}
}
int Process::s_psort(Sample &s,int first,int end)
{
    int i=first,j=end,temp;
    while(i<j)
    {
       while(i<j&&s.a[i]<=s.a[j])
           j--;
       if(i<j)
       {
           temp=s.a[i];
           s.a[i]=s.a[j];
           s.a[j]=temp;
           i++;
       }
       while(i<j&&s.a[i]<=s.a[j])
           i++;
       if(i<j)
       {
          temp=s.a[i];
          s.a[i]=s.a[j];
          s.a[j]=temp;
          j--;
       }
    }
return i;
}
void Process::s_qsort(Sample &s,int first,int end)
{
    int p;
    if(first<end)
    {
    p=s_psort(s,first,end);
    s_qsort(s,first,p-1);
    s_qsort(s,p+1,end);
    }
}
void Process::s_selsort(Sample &s)
{
      int temp,temp2;
      for(int i=0;i<s.n-1;i++)
      {
         temp=i;
         for(int j=i+1;j<s.n;j++)
         if(s.a[temp]>s.a[j])
             temp=j;
         temp2=s.a[i];
         s.a[i]=s.a[temp];
         s.a[temp]=temp2;
      }
}
void Process::sift(int k,int m,Sample &s)
{
     int i=k,j=2*i+1,temp;
     while(j<m)
     {
       if(j<m-2&&s.a[j]<s.a[j+1])// 体会j<m
           j++;
        if(s.a[i]>=s.a[j]) break;
       else {
        temp=s.a[i];
        s.a[i]=s.a[j];
        s.a[j]=temp;
        i=j;
        j=2*j+1;
       }
     }
}
void Process::s_hsort(Sample &s)
{
    int temp;
    for(int i=(s.n-1)/2;i>=0;i--)
        sift(i,s.n,s);
    for(int j=0;j<s.n-1;j++)
    {
       temp=s.a[0];
       s.a[0]=s.a[s.n-j-1];
       s.a[s.n-j-1]=temp;
       sift(0,s.n-j-1,s);
    }
}
void Process::getdata(Sample &s)
{
     cout<<"元素个数：";
    cin>>s.n;
    for(int i=0;i<s.n;i++)
    {
    cout<<"输入第"<<i+1<<"个数据：";
    cin>>s.a[i];
    }
}
void Process::disp(Sample &s)
{
for(int i=0;i<s.n;i++)
cout<<s.a[i]<<" ";
cout<<endl;
}
int main()
{   
    int sel;
    Sample s;
    Process p;
    p.getdata(s);
    cout<<"原来序列:";
    p.disp(s);
cout<<"1:插入排序 2：希尔排序 3：冒泡排序 4：快速排序 5：选择排序 6：堆排序 "<<endl;
cout<<"选择排序方法：";
cin>>sel;
switch(sel)
{
case 1:
    p.s_isort(s);
    cout<<"插入排序:";
    break;
case 2:
    p.s_ssort(s);
    cout<<"希尔排序:";
    break;
case 3:
    p.s_bsort(s);
    cout<<"冒泡排序:";
    break;
case 4:
    p.s_qsort(s,0,sel-1);
    cout<<"快速排序:";
    break;
case 5:
    p.s_selsort(s);
    cout<<"选择排序:";
    break;
case 6:
    p.s_hsort(s);
    cout<<"堆排序:";
    break;
}
p.disp(s);
    return 0;
}


联系
我们