C++代写网：利用插入排序、起泡排序、快速排序

//只有计算交换和比较次数的程序
//利用随机函数产生1000个随机整数，
//利用插入排序、起泡排序、快速排序、选择排序、堆排序、

#include <iostream.h>
#include <malloc.h>
#include <stdlib.h>
#define LS(a,b) ((a)<(b))
#define LL(a,b) ((a)>(b))
#define MAXSIZE 1000
typedef int KeyType;
typedef struct
{
    int key;
}RedType;
typedef struct
{
    RedType r[MAXSIZE+1];
    int length;
}SqList;
typedef SqList HeapType;
int compare=0;
int change=0;
int Create_Sq(SqList &L)
{
    int i,k;
    cout<<"请输入产生随机数的个数:";
    cin>>k;
    L.length=k;
    for(i=1;i<=k;++i)
    {
       
        L.r[i].key=rand();
    }
    return 1;
}
void Bubble_sort(SqList &L)
{//冒泡排序
    int i,j,l,k=L.length;
    for(i=1;i<=L.length-1;++i)
    {
          for(j=1;j<=k-1;++j)
          {
               ++compare;
               if(LL(L.r[j].key,L.r[j+1].key))
               {
                    l=L.r[j].key;
                    L.r[j].key=L.r[j+1].key;
                    L.r[j+1].key=l;
                    ++change;
                }
          }
          –k;
    }
    cout<<endl<<"—–冒泡排序后的序列—–"<<endl;
    for(i=1;i<=L.length;i++)
      cout<<" "<<L.r[i].key;
    cout<<endl;
    cout<<"冒泡排序的比较次数:";
    cout<<compare<<endl;
    cout<<"冒泡排序的交换次数:";
    cout<<change<<endl;
        compare=0;
    change=0;
}
void InsertSort(SqList &L)
{//直接插入排序
    int i,j;
    cout<<endl;
    for(i=2;i<=L.length;++i)
      if(LS(L.r[i].key,L.r[i-1].key))
      {
           ++compare;
           ++change;
           L.r[0]=L.r[i];
           L.r[i]=L.r[i-1];
           for(j=i-2;LS(L.r[0].key,L.r[j].key);–j)
           {
                ++compare;
                L.r[j+1]=L.r[j];
           }
           L.r[j+1]=L.r[0];
      }
    cout<<"—–直接插入排序后的序列—–"<<endl;
    for(i=1;i<=L.length;i++)
      cout<<" "<<L.r[i].key;
    cout<<endl;
    cout<<"直接插入排序的比较次数:";
    cout<<compare<<endl;
    cout<<"直接插入排序的交换次数:";
    cout<<change<<endl;
    compare=0;
    change=0;
}
void SelectSort(SqList &L)
{//简单选择排序
    int l,i,j;
    cout<<endl;
    for(i=1;i<L.length;++i)
    {
          L.r[0]=L.r[i];
          j=i+1;
          l=i;
          for(j;j<=L.length;++j)
          {
               ++compare;
               if(LL(L.r[0].key,L.r[j].key))
               {
                    l=j;
                    L.r[0]=L.r[j];
               }
          }
           if(l!=i)
          {
                ++change;
                L.r[l]=L.r[i];
                L.r[i]=L.r[0];
          }
    }
cout<<"—–简单选择排序后的序列—–"<<endl;
    for(i=1;i<=L.length;i++)
    cout<<" "<<L.r[i].key;
    cout<<endl;
    cout<<"简单选择排序的比较次数:";
    cout<<compare<<endl;
    cout<<"简单选择排序的交换次数:";
    cout<<change<<endl;
    compare=0;
    change=0;
}
int Partition(SqList &L,int low,int high)
{
    int pivotkey;
    L.r[0]=L.r[low];
    pivotkey=L.r[low].key;
    while(low<high)
    {
          while(low<high&&L.r[high].key>=pivotkey)
          {
               ++compare;
               –high;
          }
          ++change;
          L.r[low]=L.r[high];
          while(low<high&&L.r[low].key<=pivotkey)
          {
               ++compare;
               ++low;
          }
          ++change;
          L.r[high]=L.r[low];
    }
    L.r[low]=L.r[0];
    return low;
}
void QSort(SqList &L,int low,int high)
{//递归形式的快速排序算法
    int pivotloc;
    if(low<high)
    {
          pivotloc=Partition(L,low,high);
          QSort(L,low,pivotloc-1);
          QSort(L,pivotloc+1,high);
    }
}
void QuickSort(SqList &L)
{
    int i;
    QSort(L,1,L.length);
    cout<<"—–快速排序后的序列为—–"<<endl;
    for(i=1;i<=L.length;i++)
    cout<<" "<<L.r[i].key;
    cout<<endl;
    cout<<"快速排序的比较次数:";
    cout<<compare<<endl;
    cout<<"快速排序的交换次数:";
    cout<<change<<endl;
    compare=0;
    change=0;
}

void HeapAdjust(HeapType &H,int s,int m)
{//堆排序
    int j;
    RedType rc;
    rc=H.r[s];
    for(j=2*s;j<=m;j*=2)
    {
        if(j<m&&LS(H.r[j].key,H.r[j+1].key))
        {
            ++compare;
            ++j;
        }
        if(!LS(rc.key,H.r[j].key))
        {
            ++compare;
            break;
        }
        H.r[s]=H.r[j];
        s=j;
    }
    H.r[s]=rc;
}
void HeapSort(HeapType &H)
{
    int i;
    for(i=H.length/2;i>0;–i)
        HeapAdjust(H,i,H.length);
    for(i=H.length;i>1;–i)
    {
        ++change;
        H.r[0]=H.r[1];
        H.r[1]=H.r[i];
        H.r[i]=H.r[0];
        HeapAdjust(H,1,i-1);
    }
    cout<<"—–堆排序后的序列为—–"<<endl;
    for(i=1;i<=H.length;i++)
        cout<<" "<<H.r[i].key;
    cout<<endl;
    cout<<"堆排序的比较次数:";
    cout<<compare<<endl;
    cout<<"堆排序的交换次数:";
    cout<<change<<endl;
    compare=0;
    change=0;
} 
 
void main()
{
    int i;
    int dlta[MAXSIZE];
    SqList L;
    Create_Sq(L);

    cout<<"—–待排序序列为—–"<<endl;
    for(i=1;i<=L.length;i++)
    cout<<" "<<L.r[i].key;
   
   
       
//冒泡排v序
    SqList L1=L;
    Bubble_sort(L1);
//直接插入排序
    SqList L2=L;
    InsertSort(L2);
//简单选择排序
    SqList L3=L;
    SelectSort(L3);
//快速排序
    SqList L4=L;
    QuickSort(L4);

//堆排序
    SqList L6=L;
    HeapSort(L6);
}