数据结构排序

#include<stdio.h>
#define MAXSIZE  10
typedef int KeyType;
typedef  char InfoType;

typedef  struct{
    KeyType key;
    InfoType otherinfo;
}RcdType;  //记录类型

typedef struct{
    RcdType r[MAXSIZE+1];
    int length;
}SqList;

void InsertSort(SqList &L)//直接插入排序
{  int count=0;
    for(int i=2;i<=L.length;i++)
    if(L.r[i].key<L.r[i-1].key)
    {
        L.r[0]=L.r[i];       //复制为哨兵
        L.r[i]=L.r[i-1];
        for(int j=i-2;(L.r[0].key<L.r[j].key);j--)
        {L.r[j+1]=L.r[j];count++;}       //记录后移
        L.r[j+1]=L.r[0];     //插入到正确位置
    }
    printf("直接排序后的结果是:\n ");
    for(i=1;i<=L.length;i++)
    printf("%d ",L.r[i].key);
    printf("执行了%d步\n",count);
printf("\n");
}

void BInsertSort(SqList &L)//折半插入排序
{    int count=0;
    for(int i=2;i<=L.length;i++)
    {
        L.r[0]=L.r[i];
        L.r[i]=L.r[i-1];
        int low=1,high=i-1;
        while(low<high) //寻找插入位置
        {    count++;
            int m=(low+high)/2;
            if(L.r[0].key<L.r[m].key)
            high=m-1;
            else low=m+1;
        }
        for(int j=i-1;j>=high+1;j--)
        L.r[j+1]=L.r[j];       //记录后移
        L.r[high+1]=L.r[0];       //插入记录
    }
    printf("折半插入排序: \n");
    for(i=1;i<=L.length;i++)
    printf("%d ",L.r[i].key);
    printf("执行了%d步\n",count);
printf("\n");
}

void ShellInsert(SqList &L ,int dk )  //一趟希尔插入排序
 {   
    for(int i=dk+1;i<=L.length;i++)
        if(L.r[i].key<L.r[i-dk].key)
        {
            L.r[0]=L.r[i];
            for(int 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 dlta[],int t )//希尔排序
{
    for(int k=0;k<t;k++)
    ShellInsert(L,dlta[k]);
    printf("希尔排序后的结果是:\n ");
    for(int i=1;i<=L.length;i++)
    printf("%d ",L.r[i].key);
printf("\n");
}

void BubbleSort(SqList &L)//冒泡排序
{
    int flag=1;
    for(int i=1;i<=L.length && flag!=0;i++)
    {
        flag=0;
        for(int j=1;j<=(L.length-i);j++)
            if(L.r[j].key<L.r[j+1].key)
            {
                RcdType temp = L.r[j];
                L.r[j] = L.r[j+1];
                L.r[j+1] = temp;
                flag=1;
            }
    }
    printf("冒泡排序后的结果是:\n ");
    for(i=1;i<=L.length;i++)
    printf("%d ",L.r[i].key);
printf("\n");
}

 

int Partition(SqList &L,int low ,int high)  //快速排序一次划分
{
    L.r[0] = L.r[low];
    KeyType pivotkey = L.r[low].key;  //第一个记录作为枢轴记录
    while(low<high)
    {
        while(low < high && pivotkey<L.r[high].key)
          --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];       //枢轴记录到位
    return low;           //返回枢轴位置
}
void Qsort(SqList &L,int low,int high)//快速排序
{
    if(low<high)
    {
        int pivotkey = Partition(L,low,high);
        Qsort(L,pivotkey+1 ,high);
        Qsort(L,low,pivotkey-1);
    }

}
void QuickSort(SqList &L)//快速排序
{
    Qsort( L, 1, L.length);
    printf("快速排序后的结果是:\n ");
    for(int i=1;i<=L.length;i++)
    printf("%d ",L.r[i].key);
printf("\n");
}

void main()
{
    SqList L;
printf("输入%d个要排序的数字，空格隔开\n",MAXSIZE);
    for(int i=1;i<=MAXSIZE;i++)
    scanf("%d",&L.r[i].key);
    L.length=MAXSIZE;
             InsertSort(L); 
             BInsertSort(L);
             int dlta[]={8,4,2,1};
             ShellSort( L,dlta,4);
             BubbleSort(L);
             QuickSort(L);         
}