查找、排序的应用实验 .cpp

查找、排序的应用实验.有简单的直接排序 冒泡排序等排序内容.

#include <iostream.h>
#include <malloc.h>
#include <stdlib.h>
#define LS(a,b) ((a)<(b))
#define LL(a,b) ((a)>(b))
#define MAXSIZE 2000
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();    //随机产生k个数
    }
    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))//若“<”，则将 L.r[i] 插入有序子表
      {
           ++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; 
} 
int Partition(SqList &L,int low,int high)
{// 交换顺序表 L 中子表 r[low . . high] 的记录，“枢轴”记录到位并返回其所在位置
// 此时，在它之前（后）的记录均不大（小）于它。
    int pivotkey;
    L.r[0]=L.r[low];     // 用子表第一个记录作“枢轴”记录
    pivotkey=L.r[low].key;   // pivotkey是“枢轴”记录关键字
    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)
    {// 长度大于 1
          pivotloc=Partition(L,low,high);    // 将 L.r[low . . high] 一分为二
          QSort(L,low,pivotloc-1);           // 对低子表递归排序
          QSort(L,pivotloc+1,high);         // 对高子表递归排序
    }
} 
void QuickSort(SqList &L)
{// 对顺序表 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)
    {// 沿着 key 较大的孩子结点向下筛选
        if(j<m&&LS(H.r[j].key,H.r[j+1].key))
        {
            ++compare;
            ++j;// j 为 key 较大的记录的下标
        }
        if(!LS(rc.key,H.r[j].key))
        {
            ++compare;
            break;// rc应该插入在位置 s 上
        }
        H.r[s]=H.r[j];
        s=j;
    }
    H.r[s]=rc;
} 
void HeapSort(HeapType &H)
{// 对顺序表 H 进行堆排序
    int i;
    for(i=H.length/2;i>0;--i)
        HeapAdjust(H,i,H.length);    // 把 H.r[1 . . 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];// 将堆顶记录和当前未经排序的子序列 H.r[1 . . i] 中的最后一个记录相互交换
        HeapAdjust(H,1,i-1);// 将 H.r[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; 
}  
 
main()
{
    int i,m;
    int dlta[MAXSIZE];
    SqList L;
    Create_Sq(L);

    cout<<"-----待排序序列为-----"<<endl;
    for(i=1;i<=L.length;i++)
    cout<<" "<<L.r[i].key;                           
	do {
	cout<<endl<<"1.冒泡排序  2.直接插入排序  3.快速排序  4.堆排序  0.退出"<<endl;
	cout<<"请选择要进行的操作:"<<endl;
    cin>>m;
	switch(m)
	{
	case 1:SqList L1=L;            //冒泡排序
    Bubble_sort(L1);break;

    case 2:SqList L2=L;            //直接插入排序
    InsertSort(L2);break;

    case 3:SqList L3=L;            //快速排序
    QuickSort(L3);break;

	case 4:SqList L4=L;            //堆排序
    HeapSort(L4);break;

	case 0:break;                //退出
	default:
		cout<<"输入信息错误,请重新输入!"<<endl;
		break;
	}
	}while(m!=0);
	return 0;
}