データ構造の各種並べ替えのまとめ

#include <iostream>
#include <algorithm>
#define MAXSIZE 10000
#define OK 1
typedef int KeyType;
typedef char InfoType;
typedef int Status;
using namespace std;
typedef struct{
 KeyType key;
 InfoType otherinfo;
}RedType;
typedef struct{
 RedType r[MAXSIZE+1];
 int length;
}SqList;
Status InitList_Sq(SqList &L,int a[],int n)
{
 L.length=n;
 for(int i=1;i<=n;i++)
 L.r[i].key=a[i];
 return OK;
}
void ShowSqList(SqList L)
{
 for (int i=1;i<=L.length;i++)
  cout<<L.r[i].key<<" ";
 cout<<endl;
}
//----------------    -------------
int Partition(SqList &L ,int low,int high)                 
{
 int pivotkey=L.r[low].key;
 L.r[0]=L.r[low];
 while(low<high)
 {
  while(low<high&&L.r[high].key>=pivotkey)
  {
   --high;
  } 
  L.r[low]=L.r[high];
  while(low<high&&L.r[low].key<=pivotkey)
  {
   ++low;
  } 
  L.r[high]=L.r[low];
 }
 L.r[low]=L.r[0];
 for(int k=1;k<=L.length;k++)
  cout<<" "<<L.r[k].key<<" ";
 cout<<endl;
 return low;
}
void QSort(SqList &L,int low,int high)
{
 int pivotloc,j=0;
 if(low<high)
 {
  pivotloc=Partition(L,low,high);
  QSort(L,low,pivotloc-1);
  QSort(L,pivotloc+1,high);
 }
}
void Quicksort(SqList &L)
{
 QSort(L,1,L.length);
}
//------------------   -----------------
void HeapAdjust(SqList &L,int s,int m)           
{
 int j;
 RedType rc=L.r[s];
 for(j=2*s;j<=m;j*=2)
 {
  if(j<m&&L.r[j].key<L.r[j+1].key)
   j++;
  if(rc.key>=L.r[j].key)
   break;
  L.r[s]=L.r[j];
  s=j;
 }
 L.r[s]=rc;
}
void CreatHeap(SqList &L)
{
 for(int i=L.length/2;i>0;--i)
  HeapAdjust(L,i,L.length);
}
void Heapsort(SqList &L)
{
 CreatHeap(L);
 for (int i=L.length;i>1;--i)
 {
  swap(L.r[1],L.r[i]);
  HeapAdjust(L,1,i-1);
  cout<<" "<<L.length-i+1<<"       :";
  for(int k=1;k<=L.length;k++)
   cout<<" "<<L.r[k].key<<" ";
  cout<<endl;
 }
}
//---------------    ------------
void ShellInsert(SqList &L,int dk)            
{
 int i,j;
 for(i=dk+1;i<=L.length;i++)
  if (L.r[i].key<L.r[i-dk].key)
  {
   L.r[0]=L.r[i];
   for (j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)
    L.r[j+dk]=L.r[j];
   L.r[j+dk]=L.r[0];
  }
}
void Shellsort(SqList &L,int dt[],int t)
{
 for(int i=0;i<t;i++){
  ShellInsert(L,dt[i]);
  cout<<i+1<<"     ：";
  for(int k=1;k<=L.length;k++)
   cout<<" "<<L.r[k].key<<" ";
  cout<<endl;
 }
}
//------------    -----------
void Merge(RedType R[],RedType T[],int low,int mid,int high)
{
 //    R[low..mid] R[mid+1..high]      T[low..high]
 int i=low,j=mid+1,k=low;
 while(i<=mid&&j<=high){    // R          T 
  if(R[i].key<=R[j].key) T[k++]=R[i++];
  else T[k++]=R[j++];
 }
 while(i<=mid)   //    R[low..mid]   T 
  T[k++]=R[i++];
 while(j<=high)  //    R[j.high]   T 
  T[k++]=R[j++];
}          //Merge
int x=1;
void MSort(RedType R[],RedType T[],int low,int high) 
{
 //R[low..high]       T[low..high] 
 int mid;
 if(low==high) T[low]=R[low];
 else{
  RedType *S=new RedType[high];
  mid=(low+high)/2;
  MSort(R,S,low,mid);
  MSort(R,S,mid+1,high);
  Merge(S,T,low,mid,high);
  cout<<" "<<x++<<"     ：";
  for(int l=low;l<=high;l++)
  cout<<" "<<T[l].key<<" ";
     cout<<endl;
 }
}
void MergeSort(SqList &L) {
 //    L     
 MSort(L.r,L.r,1,L.length);
}

//-----------------    RadixSorting-------------------------
#define MAX_NUM_OF_KEY 8        //         
#define RADIX    10            //     ，           
#define MAX_SPACE 10000
typedef int DataType ;
typedef struct 
{
    int data;        //  
    DataType keys[MAX_NUM_OF_KEY];        //          
    int  next;        
}SLCell;    //         

typedef struct    Sllist
{
    SLCell *R;     //          ，r[0]    
    int recnum;        //         
    int keynum;        //          
}Sllist, * SLList;    //      

typedef int ArrType[RADIX];        //      ，        ，     ，     
void creatList(SLList &SLL)
{

    int key, i=1,j,n,t;
 cout<<"═════       ：";
 cin>>n;
    cout<<"═════          :";
    for(int k=0;k<n;k++)
    {
  cin>>key;
  t=1;
        SLL->R[i].data = key;
        for(j = 1;j<10; j++)
        {
            SLL->R[i].keys[j] = key % 10;
            key /= 10;
   if(key!=0) t++;
        }
        SLL->R[i-1].next=i++;
  if(SLL->keynum<t) SLL->keynum=t;

    }
    SLL->recnum = i-1;
    SLL->R[SLL->recnum].next=0;
}

void print(SLList &SLL)
{
    for(int p=SLL->R[0].next; p; p=SLL->R[p].next)
    {
        cout<<SLL->R[p].data<<"  ";
    }
    cout<<endl;
}

void distribute(SLCell *R, int i, ArrType front, ArrType end)
{
    //    L R      (keys[0]...keys[i-1]  )。
    //     i    keys[i]  RADIX   ，         keys[i]  。
    //front[0...RADIX-1] end[0...RADIX-1]                  。
    for(int j=0; j<RADIX; ++j)
        front[j] = 0;        //         
    for(int p=R[0].next; p; p=R[p].next)
    {
  int j;
         j=R[p].keys[i];            //   i    
        if(!front[j])
            front[j] = p;        // front[j]  ，       front[j]     
        else
            R[end[j]].next = p;    // front[j]          ，   j           ，
                                //       j               ，    p   
        end[j] = p;        //               
    }
}//distribute

void collect(SLCell *R, int i, ArrType front, ArrType end)
{
 int j;
    //    keys[i]      f[0...RADIX-1]               
    for( j=0; !front[j]; j++);     //           
    R[0].next=front[j];            //      
    int k=end[j];                    //k         
    while(j<RADIX)
    {
        for(++j; j<RADIX; j++)
            if(front[j])        //        
            {
                R[k].next=front[j];        //  
                k=end[j];      
            }
    }
    R[k].next=0;                    //k              
}//collect
void RadixSort(SLList &SLL){
 ArrType front,end;
    for(int i = 1; i <= SLL->keynum; i++)    //            
    {
        distribute(SLL->R, i,front,end);    // i   
        collect(SLL->R, i,front,end);        // i   
        cout<<"═════ "<<i<<"     :";
        print(SLL);
    }
}
/*---------------------------------------------------------------------------------*/
void ShellSort()
{
 cout<<"   ╔═════════════════════════════╗"<<endl;
 cout<<"   ║                        ShellSort                 ║"<<endl;
 cout<<"   ╚═════════════════════════════╝"<<endl;
 int d[3]={5,3,1},R[MAXSIZE+1],n;
 cout<<"═════          :";
 cin>>n;
 cout<<"═════   "<<n<<"  :";
 for(int i=1;i<=n;i++) cin>>R[i];
 cout<<"═════            :";
 for(int j=1;j<=n;j++){
  cout<<R[j]<<" ";
 }
 cout<<endl;
 SqList L;
 cout<<"═════        ："<<endl;
 InitList_Sq(L,R,n);
 Shellsort(L,d,3);
}

void QuickSort()
{
 cout<<"   ╔═════════════════════════════╗"<<endl;
 cout<<"   ║                        QuickSort                 ║"<<endl;
 cout<<"   ╚═════════════════════════════╝"<<endl;
 cout<<"═════    ：49 38 65 97 76 13 27 49"<<endl;
 cout<<"═════   ：27 38 13 49 76 97 65 49"<<endl;
 cout<<"═════   ：13 27 38 49 76 97 65 49"<<endl;
 cout<<"═════   ：13 27 38 49 49 65 76 97"<<endl;
 cout<<"═════   ：13 27 38 49 49 65 76 97"<<endl;
 int d[3]={5,3,1},R[MAXSIZE+1],n;
 cout<<"          :";
 cin>>n;
 cout<<"═════   "<<n<<"  :";
 for(int i=1;i<=n;i++) cin>>R[i];
 cout<<"═════            :";
 for(int j=1;j<=n;j++){
  cout<<R[j]<<" ";
 }
 cout<<endl;
 SqList L;
 cout<<"═════        ："<<endl;
 InitList_Sq(L,R,n);
    Quicksort(L);
}

void HeapSort()
{
 cout<<"   ╔═════════════════════════════╗"<<endl;
 cout<<"   ║                       HeapSort                    ║"<<endl;
 cout<<"   ╚═════════════════════════════╝"<<endl;
 cout<<"═════    ：49 38 65 97 76 13 27 49"<<endl;
 cout<<"═════   ：76 49 65 38 49 13 27 97"<<endl;
 cout<<"═════   ：65 49 27 38 49 13 27 97"<<endl;
 cout<<"═════   ：49 49 27 38 13 65 76 97"<<endl;
 cout<<"═════   ：49 38 27 13 49 65 76 97"<<endl;
 cout<<"═════   ：38 13 27 49 49 65 76 97"<<endl;
 cout<<"═════   ：27 13 38 49 49 65 76 97"<<endl;
 cout<<"═════   ：13 27 38 49 49 65 76 97"<<endl;
 int d[3]={5,3,1},R[MAXSIZE+1],n;
 cout<<"═════          :";
 cin>>n;
 cout<<"═════   "<<n<<"  :";
 for(int i=1;i<=n;i++) cin>>R[i];
 cout<<"═════            :";
 for(int j=1;j<=n;j++){
  cout<<R[j]<<" ";
 }
 cout<<endl;
 SqList L;
 cout<<"═════       ："<<endl;
 InitList_Sq(L,R,n);
 Heapsort(L);
}

void MergingSort()
{
 cout<<"   ╔═════════════════════════════╗"<<endl;
 cout<<"   ║                      MergingSort                 ║"<<endl;
 cout<<"   ╚═════════════════════════════╝"<<endl;
 cout<<"═════    ：49 38 65 97 76 13 27"<<endl;
 cout<<"═════   ：38 49"<<endl;
 cout<<"═════   ：65 97"<<endl;
 cout<<"═════   ：38 49 65 97"<<endl;
 cout<<"═════   ：13 76"<<endl;
 cout<<"═════   ：13 27 76"<<endl;
 cout<<"═════   ：13 27 38 49 65 76 97"<<endl;
 int d[3]={5,3,1},R[MAXSIZE+1],n;
 cout<<"═════          :";
 cin>>n;
 cout<<"═════   "<<n<<"  :";
 for(int i=1;i<=n;i++) cin>>R[i];
 cout<<"═════            :";
 for(int j=1;j<=n;j++){
  cout<<R[j]<<" ";
 }
 cout<<endl;
 SqList L;
 cout<<"═════        ："<<endl;
 InitList_Sq(L,R,n);
 MergeSort(L);
}

int RadixSorting()
{
 cout<<"   ╔═════════════════════════════╗"<<endl;
 cout<<"   ║                    RadixSorting                ║"<<endl;
 cout<<"   ╚═════════════════════════════╝"<<endl;
 cout<<"═════    ：278 109 63 930 589 184 505 269 008 083"<<endl;
 cout<<"═════   ：930 063 083 184 505 278 008 109 589 269"<<endl;
 cout<<"═════   ：505 008 109 930 063 269 278 083 184 589"<<endl;
 cout<<"═════   ：008 063 083 109 184 269 278 505 589 930"<<endl;
    SLList SLL;
    SLL=(SLList)malloc(MAX_SPACE*sizeof(Sllist));
    SLL->R=(SLCell *)malloc(MAX_SPACE*sizeof(SLCell));
    SLL->recnum=0;
    creatList(SLL);
    cout<<"═════   :";
    print(SLL);
 RadixSort(SLL);
    return 0;
}