数据结构排序

来源：百度文库编辑：神马文学网时间：2024/04/29 03:02:30

#include
#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[0]=L.r[i];       //复制为哨兵
        L.r[i]=L.r[i-1];
        for(int j=i-2;(L.r[0].key        {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        {    count++;
            int m=(low+high)/2;
            if(L.r[0].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[0]=L.r[i];
            for(int j=i-dk;(j>0) && (L.r[0].key{     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    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            {
                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    {
        while(low < high && pivotkey          --high;
          L.r[low] = L.r[high];
        while(low            ++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    {
        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);
}

数据结构排序排序（数据结构）排序（数据结构） TIN数据结构数据结构课程设计《数据结构》课程教学大纲数据结构---顺序表怎么学习数据结构数据结构查找sc 简明 Python 教程 / 数据结构 / 列表标准BT.656并行数据结构有关数据结构方面的基本概念有关数据结构方面的基本概念堆——数据结构学习希尔排序饮食排序堆排序随机排序快速排序随机排序钙质排序饮食排序 sort排序强势排序