#include<iostream>
#include <iomanip>
#include <string>
#include<deque>
using namespace std;
const int MAXSIZE=20;
class node
{
public:
 void operator =(node b);
 int key;
 char info;
};
void node::operator=(node b)
{
 key=b.key;
 info=b.info;

}
struct Sqlist
{
 node data[MAXSIZE+1];
 int length;
};
class Sort
{
private:
 Sqlist L;
public:
 void CreateSqlist();
 void swap(int,int);
 void print();
 void InsertSort();//直接插入排序
 void BinInsert();//折半插入排序
 void ShellSort();//希尔排序
 void ShellInsert(int );
 void BubbleSort();//起泡排序
 int  partition1(int ,int );//快速排序的辅助函数
 int  partition2(int ,int );//快速排序的辅助函数
 void QSort(int ,int );//快速排序
 void QuickSort();
 void SelectSort();//简单选择排序
 void HeapSort();//堆排序
 void HeapAdjust(int ,int );
 void Merge(int ,int ,int );
 void MSort(int ,int );
 void MergeSort( );//归并排序
 void RadixSort();//基数排序
};
void Sort::CreateSqlist()
{
 int array[10]={9,54,87,65,1,5,65,48,8,23};
 for (int i=0;i<=9;i++)
  L.data[i].key=array[i];
 char ary[11]={'a','b','c','d','e','f','g','h','i','j','\0'};
 for (i=0;i<=9;i++)
  L.data[i].info=ary[i];
  L.length=9;

}
void Sort::swap(int a,int b)
{
 int key=L.data[a].key;
 char info=L.data[a].info;
 L.data[a].key=L.data[b].key;
 L.data[a].info=L.data[b].info;
 L.data[b].key=key;
 L.data[b].info=info;

}
void Sort::print()
{
 for(int m=1;m<=L.length;m++)
  cout<<setw(3)<<L.data[m].key<<"   ";
 cout<<endl;
 cout<<setw(15)<<"information:";
 for( m=1;m<=L.length;m++)
  cout<<setw(3)<<L.data[m].info<<"   ";
 cout<<endl;
 cout<<endl;

}
void Sort::InsertSort()
{
 for(int i=2;i<=L.length;i++)
 {
  if(L.data[i].key<L.data[i-1].key)
  {
   L.data[0].key=L.data[i].key;
   L.data[0].info=L.data[i].info;
   for(int j=i-1;L.data[0].key<L.data[j].key;j--)
   {
    L.data[j+1].key=L.data[j].key;
    L.data[j+1].info=L.data[j].info;
   }
   L.data[j+1].key=L.data[0].key;
   L.data[j+1].info=L.data[0].info;
  }
  
 }

 
}
void Sort::BinInsert()
{
 for(int i=2;i<=L.length;i++)
 {
  if(L.data[i].key<L.data[i-1].key)
  {
   int low=1;
   int high=i-1;
   while(low<high)
   {
    int mid=(low+high)/2;
    if(L.data[0].key>=L.data[mid].key)
     low=mid+1;
    else
     high=mid-1;
   }
   for (int j=i-1;j>high;j--)
   {
    L.data[j+1].key=L.data[j].key;
    L.data[j+1].info=L.data[j].info;
   }
   L.data[j+1].key=L.data[0].key;
   L.data[j+1].info=L.data[0].info;

  }
 }

}
void Sort::ShellInsert(int dk)
{
 for (int i=1;i<=dk;i++)
 {
  for (int j=dk+i;j<=L.length;j=j+dk)
  {
   if (L.data[j].key<L.data[j-dk].key)
   {
    L.data[0]=L.data[j];
    for (int m=j-dk;m>0&&L.data[0].key<L.data[m].key;m=m-dk)
     L.data[m+dk]=L.data[m];
    L.data[m+dk]=L.data[0];
    
   }
  }
 }
 
}
void Sort::ShellSort()
{
 for (int gap=L.length/2;gap>=1;gap=gap/2)
 {
  ShellInsert(gap);

 }

}
void Sort::BubbleSort()
{
 for (int i=1;i<L.length;i++)
 {
  for (int j=1;j<=L.length-i;j++)
  {
   if (L.data[j].key>L.data[j+1].key)
   swap(j,j+1);

  }
 }

}
int Sort::partition1(int low,int high)
{
 int pivot=low;
 int pivotvalue=L.data[low].key;
 while (low<high)
 {
  while(low<high&&L.data[high].key>=pivotvalue)
   high--;
  while(low<high&&L.data[low].key<=pivotvalue)
   low++;
  swap(low,high);
 }
 swap(low,pivot);
 return low;

}

void Sort::QSort(int low=1,int high=9)
{
 if (low<high)
 {
  int pivotloc=partition1(low,high);//寻找中间点
  QSort(low,pivotloc-1);//对左子序列进行排序
  QSort(pivotloc+1,high);//对右子序列进行排序
 }

}
void Sort::QuickSort()
{
 QSort(1,L.length);

}
void Sort::SelectSort()
{
 for (int i=1;i<L.length;i++)
 {
  int min=i;
  for (int j=i+1;j<=L.length;j++)
  {
   if (L.data[j].key<L.data[min].key)
    min=j;
  }
  swap(min,i);
 }

}
void Sort::HeapAdjust(int i,int n)
{
 L.data[0]=L.data[i];
 int j=2*i;
 while (j<=n)
 {
  if (j<n&&L.data[j].key<L.data[j+1].key)
   j++;
  if (L.data[0].key>=L.data[j].key)
   break;
  L.data[i]=L.data[j];
  i=j;
  j=2*i;
  
 }
   L.data[i]=L.data[0];
}
void Sort::HeapSort()
{
 for (int i=L.length/2;i>0;i--)
 HeapAdjust(i,L.length);
 for (i=L.length;i>0;i--)
 {
  swap(i,1);
  HeapAdjust(1,i-1);
 }

}
void Sort::Merge(int low,int m,int high)
{
 node *p=new node[high-low+1];
 int i=low;
 int j=m+1;
 int k=0;
 while (i<=m&&j<=high)
 {
  if(L.data[i].key<=L.data[j].key)
   p[k++]=L.data[i++];
  else
   p[k++]=L.data[j++];
 }
 while (i<=m)
   p[k++]=L.data[i++];
 while (j<=high)
     p[k++]=L.data[j++];
  for (i=low,k=0;i<=high;i++,k++)
   L.data[i]=p[k];
  
  delete []p;
}
void Sort::MSort(int low,int high)
{
 if (low<high)
 {
  int center=(low+high)/2;
  MSort(low,center);
  MSort(center+1,high);
  Merge(low,center,high);
 }
}

void Sort::MergeSort()
{
 MSort(1,L.length);

}
void Sort::RadixSort()
{
 int i,j;
 deque<node> bin[10];
 
 for ( i=1;i<=L.length;i++)
 {
  int m=L.data[i].key%10;
  bin[m].push_back(L.data[i]);

 }
 for( j=0,i=1;j<10;j++)
 {
  while(!bin[j].empty())
  {
   L.data[i++]=bin[j].front();
   bin[j].pop_front();
  }
 }
 for ( i=1;i<=L.length;i++)
 {
  int  m=L.data[i].key/10;
  bin[m].push_back(L.data[i]);
  
 }
 for( j=0,i=1;j<10;j++)
 {
  while(!bin[j].empty())
  {
   L.data[i++]=bin[j].front();
   bin[j].pop_front();
  }
 }

 

}
int main()
{
 Sort s;
 s.CreateSqlist();
    int menu;
 int type;
 while (1)
 {
  cout<<"    〓〓〓〓〓〓〓〓〓〓〓〓〓★〓〓〓〓〓〓〓〓〓〓〓〓〓"<<endl;
  cout<<"    〓※※※※※※※※※※※※★※※※※※※※※※※※※〓"<<endl;
  cout<<"    〓※                   菜单选顶                   ※〓"<<endl;
  cout<<"    〓※==============================================※〓"<<endl;
  cout<<"    〓※                                              ※〓"<<endl;
  cout<<"    〓※     1.插入排序               2.交换排序      ※〓"<<endl;
  cout<<"    〓※     3.选择排序               4.归并排序      ※〓"<<endl;
  cout<<"    〓※     5.基数排序               0.退出系统      ※〓"<<endl;
  cout<<"    〓※                                              ※〓"<<endl;
  cout<<"    〓※                                              ※〓"<<endl;
  cout<<"    〓※※※※※※※※※※※※★※※※※※※※※※※※※〓"<<endl;
  cout<<"    〓〓〓〓〓〓〓〓〓〓〓〓〓★〓〓〓〓〓〓〓〓〓〓〓〓〓"<<endl;
  cout<<endl<<"请选择相应操作菜单项：";
  cin>>menu;
  switch(menu)
  {
    case 0:
     return 0;
    case 1:
     cout<<"          ★★★★★★★★★★★★★★★★★★★★"<<endl;
     cout<<"          ★    1.直接插入     2. 希尔排序      ★"<<endl;
     cout<<"          ★                                    ★"<<endl;
     cout<<"          ★    3.折半插入     0. 返回上级      ★"<<endl;
     cout<<"          ★★★★★★★★★★★★★★★★★★★★"<<endl;
     cin>>type;
     switch (type)
     {
         case 1:
       cout<<setw(15)<<"initial data:";
       s.print();
       s.InsertSort();
       cout<<setw(15)<<"InsertSort:";
       s.print();
       break;
         case 2:
       cout<<setw(15)<<"initial data:";
       s.print();
       s.ShellSort();
       cout<<setw(15)<<"ShellSort:";
       s.print();
       break;
      case 3:
       cout<<setw(15)<<"initial data:";
       s.print();
       s.BinInsert();
       cout<<setw(15)<<"BinInsert:";
       s.print();
       break;
      case 0:
       break;
      default:
       cout<<"输入有误！"<<endl;
       break;

     }
     break;
     case 2:
      cout<<"          ★★★★★★★★★★★★★★★★★★★★"<<endl;
      cout<<"          ★    1.起泡排序     2. 快速排序      ★"<<endl;
      cout<<"          ★                                    ★"<<endl;
      cout<<"          ★    0.返回上级                      ★"<<endl;
      cout<<"          ★★★★★★★★★★★★★★★★★★★★"<<endl;
      cin>>type;
      switch (type)
      {
      case 1:
       cout<<setw(15)<<"initial data:";
       s.print();
       s.BubbleSort();
       cout<<setw(15)<<"BubbleSort:";
       s.print();
       break;
      case 2:
       cout<<setw(15)<<"initial data:";
       s.print();
       s.QuickSort();
       cout<<setw(15)<<"QuickSort:";
       s.print();
       break;
      case 0:
       break;
      default:
       cout<<"输入有误！"<<endl;
       break;
      
      }
     break;
      case 3:
       cout<<"          ★★★★★★★★★★★★★★★★★★★★"<<endl;
       cout<<"          ★    1.直接选择     2. 堆排序        ★"<<endl;
       cout<<"          ★                                    ★"<<endl;
       cout<<"          ★    0.返回上级                      ★"<<endl;
       cout<<"          ★★★★★★★★★★★★★★★★★★★★"<<endl;
       cin>>type;
       switch (type)
       {
       case 1:
        cout<<setw(15)<<"initial data:";
           s.print();
        s.SelectSort();
        cout<<setw(15)<<"SelectSort:";
            s.print();
        break;
       case 2:
        cout<<setw(15)<<"initial data:";
       s.print();
        s.HeapSort();
        cout<<setw(15)<<"HeapSort:";
       s.print();
        break;
       case 0:
        break;
       default:
        cout<<"输入有误！"<<endl;
        break;
       
       }
       break;
       case 4:
        cout<<setw(15)<<"initial data:";
        s.print();
        s.MergeSort();
        cout<<setw(15)<<"MergeSort:";
           s.print();
        break;
       case 5:
        cout<<setw(15)<<"initial data:";
        s.print();
        s.MergeSort();
        cout<<setw(15)<<"RadixSort:";
        s.print();
        break;
        default:
         cout<<"输入有误！！！"<<endl;

 

  }
  
 }
 return 0;
   

}