编程题实训-排序

发布时间:2024年01月08日

第1关:基于链表的简单选择排序

任务描述

试以单链表为存储结构,实现简单选择排序算法。

编程要求

输入

多组数据,每组数据两行。第一行为序列的长度n,第二行为序列的n个元素(元素之间用空格分隔,元素都为正整数)。当n等于0时,输入结束。

输出

每组数据输出一行,为从小到大排序后的序列。每两个元素之间用空格隔开。

#include<iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法创建单链表
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void PrintList(LinkList L)
{//打印依次输出链表中的数据
    LinkList p=L->next;
    while(p){
        if(p->next!=NULL) cout<<p->data<<" ";
        else cout<<p->data;
        p=p->next;
    }
    cout<<endl;
}
void SelectSort(LinkList &L)
{//基于单链表的简单选择排序
/**************begin************/
    LinkList p=L->next;          //p指向首元结点
    while(p!=NULL)            //顺链域向后扫描,直到p为空
    {
        LinkList q=p->next,r=p;    //r是指向关键字最小的结点的指针
        while(q!=NULL)
        {
            if(q->data<r->data) r=q;
            q=q->next;
        }
        if(r!=p)                //交换r和p的数据域
        {
            int temp=p->data;
            p->data=r->data;
            r->data=temp;
        }
        p=p->next;        //更新指针p,指向下一个结点
    }
    /**************end************/
}
int main()
{
	int n;
	while(cin>>n)
	{
		if(n==0) break;
		LinkList L;
		CreateList_R(L,n);        //后插法创建单链表
		SelectSort(L);           //基于单链表的简单选择排序
		PrintList(L);           //打印依次输出链表中的数据
	}
	return 0;
}

第2关:基于双向链表的双向冒泡排序法

任务描述

有n个记录存储在带头结点的双向链表中,利用双向冒泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向冒泡排序即相邻两趟排序向相反方向冒泡)。

编程要求

输入

多组数据,每组数据两行。第一行为序列的长度n,第二行为序列的n个元素(元素之间用空格分隔,元素都为正整数)。当n等于0时,输入结束。

输出

每组数据输出一行,为从小到大排序后的序列。每两个元素之间用空格隔开。

#include<iostream>
using namespace std;
typedef struct DuLNode
{
	int data;
	struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;
void CreateList(DuLinkList &L,int n)
{//建立双向循环链表

    L=new DuLNode;    //初始化链表L的头结点
	L->prior=L;
	L->next=L;
	DuLinkList r=L;     //工作指针r初始化指向头结点
	while(n--)
	{
		DuLinkList p=new DuLNode;
		cin>>p->data;
		p->next=r->next;
		r->next=p;
		p->prior=r;
		p->next->prior=p;
		r=p;
	}
}
void DuplexSort(DuLinkList L)
{//对存储在带头结点的双向链表L中的元素进行双向冒泡排序
/**************begin************/
    DuLinkList p=L->next;
    while(p->next&&p->next!=L)     //p指向双向链表的表尾结点
        p=p->next;
    DuLinkList last=p;           //初始化指针last指向表尾结点
    DuLinkList first=L->next;    //初始化指针first指向首元结点
    while(1)
    {
        if(first!=last)          //指针first和last没有指向同一结点时,正向冒泡排序
        {                       //每一趟使一最大元素沉底
            for(p=first;p!=last;p=p->next)
                if(p->data>p->next->data)    //交换数据域
                {
                    int t=p->data;
                    p->data=p->next->data;
                    p->next->data=t;
                }
            last=last->prior;                  //更新last指针,指向前一个结点
        }
        else
            break;
        if(first!=last)       //指针first和last没有指向同一结点时,反向冒泡排序
        {                     //每一趟使一最小元素冒出
            for(p=last;p!=first;p=p->prior)
                if(p->data<p->prior->data)      //交换数据域
                {
                    int t=p->data;
                    p->data=p->prior->data;
                    p->prior->data=t;
                }
            first=first->next;              //更新first指针,指向后一个结点
        }
        else
            break;
    }
    /**************end************/
}
void PrintList(DuLinkList L)
{//依次输出链表中的数据
    DuLinkList p=L->next;
	while(p->next&&p->next!=L)
	{
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<p->data<<endl;
}
int main()
{
	int n;
	while(cin>>n)
	{
		if(n==0) break;
		DuLinkList L;
		CreateList(L,n);
		DuplexSort(L);      //双向冒泡排序
		PrintList(L);
	}
	return 0;
}

第3关:砾石的交换排序

任务描述

设有顺序放置的n个桶,每个桶中装有一粒砾石,每粒砾石的颜色是红,白,蓝之一。要求重新安排这些砾石,使得所有红色砾石在前,所有白色砾石居中,所有蓝色砾石居后,重新安排时对每粒砾石的颜色只能看一次,并且只允许交换操作来调整砾石的位置。

编程要求

输入

多组数据,每组数据两行。第一行为砾石的数量n,第二行有n个字母,代表每个砾石的颜色(字母之间用空格分隔,R代表红色,W代表白色,B代表蓝色)。当n等于0时,输入结束。

输出

每组数据输出一行。为重新排序后的砾石序列。每两个字母之间用空格隔开。

#include<iostream>
using namespace std;
void Exchange(char &x,char &y)
{//交换操作
    char t;
    t=x;
    x=y;
    y=t;
}
void QkSort(char r[],int n)
{//砾石的交换排序。(红色在前,白色居中,蓝色最后)
/**************begin************/
    int i=0,j=0,k1=n-1,k2=n-1;//i指向第一块白石头,j指向红石头
                              //k1指向蓝石头,k2指向最后一块白石头
    while(j<k1)                //遍历所有石头
    {
        while(r[k1]=='B')    //从右向左找到第一块非蓝的石头
        {
            k1--;
            k2--;
        }
        while(r[i]=='R')    //从左向右找到第一块非红的石头
        {
            i++;
            j++;
        }
        if(r[j]=='B')  //如果从左向右第一块非红的石头是蓝色的
        {
            Exchange(r[i],r[k2]);    //把它与从右向左找到第一块非蓝的石头交换
            while(r[i]=='R')        //继续从左向右找到第一块非红的石头
            {
                i++;
                j++;
            }
            while(r[k1]=='B')  //继续从右向左找到第一块非蓝的石头
            {
                k1--;
                k2--;
            }
        }
        else if(r[k1]=='R')   //如果从右向左找到第一块非蓝的石头是红色的
        {
            Exchange(r[i],r[k2]); //把它与从左向右找到第一块非红的石头交换
            while(r[i]=='R')     //继续从左向右找到第一块非红的石头
            {
                i++;
                j++;
            }
            while(r[k1]=='B')   //继续从右向左找到第一块非蓝的石头
            {
                k1--;
                k2--;
            }
        }
        else                     //两块石头都是白色
        {
            while(r[j]=='W')     //找到从左向右第一块非白的石头
            {
                j++;
            }
            if(j>=k1)           //和从右向左遍历的会合,表示已找完,结束
                break;
            if(r[j]=='R')       //红色时,交换它和从左向右的第一块白色石头
            {
                Exchange(r[j],r[i]);
                i++;
            }
            else                //蓝色时,交换它和从右向左的第一块白色石头
            {
                Exchange(r[k2],r[j]);
                k2--;
            }
        }
    }
    /**************end************/
}
void PrintC(char c[],int n)
{//输出数据
    for(int i=0;i<n-1;i++)
        cout<<c[i]<<" ";
    cout<<c[n-1]<<endl;
}
int main()
{
    int n;                       //砾石的数量n
    while(cin>>n)
    {
        if(n==0) break;
        char c[n];
        for(int i=0;i<n;i++)
            cin>>c[i];      	   //输入砾石的编号
        QkSort(c,n);              //砾石的交换排序
        PrintC(c,n);
    }
    return 0;
}

第4关:数组的正负排序

任务描述

对n个关键字取整数值的记录序列进行整理,以使所有关键字为负值的记录排在关键字为非负值的记录之前,要求:

①采用顺序存储结构,至多使用一个记录的辅助存储空间;

②算法的时间复杂度为O(n)。

编程要求

输入

多组数据,每组数据两行。第一行为序列的长度n,第二行为序列的n个元素(元素之间用空格分隔,元素都为整数)。当n等于0时,输入结束。

输出

每组数据输出一行,为排序后的序列。每两个元素之间用空格隔开。

#include<iostream>
using namespace std;
void Exchange(int &x,int &y)
{//交换操作
    int z;
    z=x;
    x=y;
    y=z;
}
void Process(int a[],int n)
{//数组的正负排序,使所有关键字为负值的记录排在关键字为非负值的记录之前
/**************begin************/
    int low=0,high=n-1;
    while(low<high)
    {
        while(low<high&&a[low]<0) low++;    //找到从左到右的非负值
        while(low<high&&a[high]>=0) high--;  //找到从右到左的负值
        if(low<high)                      //当low<high时
        {
            Exchange(a[low],a[high]);    //交换记录
            low++;                     //继续寻找
            high--;
        }
    }
    /**************end************/
}
void PrintA(int a[],int n)
{//输出数据
    for(int i=0;i<n-1;i++)
        cout<<a[i]<<" ";
    cout<<a[n-1]<<endl;
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        int i,a[n];
        for(i=0;i<n;i++)   //输入数据
            cin>>a[i];
        Process(a,n);    //数组的正负排序
        PrintA(a,n);   //输出数据
    }
    return 0;
}

第5关:计数排序?

任务描述

有一种简单的排序算法,叫做计数排序。这种排序算法对一个待排序的表进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录,统计出的计数值为c,那么,这个记录在新的有序表中的合适的存放位置即为c。请编写算法实现计数排序。

编程要求

输入

多组数据,每组数据两行。第一行为序列的长度n,第二行为序列的n个元素(元素之间用空格分隔,元素都为正整数)。当n等于0时,输入结束。

输出

每组数据输出一行,为从小到大排序后的序列。每两个元素之间用空格隔开。

#include<iostream>
using namespace std;
void CountSort(int a[],int b[],int n)
{//计数排序,将包括n个数据的数组a中的记录排序存入到数组b中
/**************begin************/
    int i,j,c;
    for(i=0;i<n;i++)   //针对数组中的每个关键字
    {
        for(j=0,c=0;j<n;j++)       //统计关键字比当前关键字小的元素个数
            if(a[j]<a[i]) c++;
        b[c]=a[i];            //根据比当前关键字小的元素个数将当前关键字存放在数组b中
    }
    /**************end************/
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        int i,a[100],b[100];
        for(i=0;i<n;i++)
            cin>>a[i];
        CountSort(a,b,n);     //计数排序
        for(i=0;i<n-1;i++)
            cout<<b[i]<<" ";
        cout<<b[n-1]<<endl;
    }
}

?第6关:数组的分割

任务描述

已知由n(n≥2)个正整数构成的集合A={ak}(0≤k<n),将其划分为两个不相交的子集A1和A2,元素个数分别是n1和n2,A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法,满足|n1-n2|最小且|S1-S2|最大。

编程要求

输入

多组数据,每组数据两行。第一行为一个整数n,代表数组中有n个元素。第二行为数组中的n个元素(元素之间用空格分隔)。当n等于0时,输入结束。

输出

每组数据输出两行。第一行为子集A1,第二行为子集A2,每两个元素用空格分隔。

#include <iostream>
using namespace std;
void PrintA(int R[],int n)
{//输出数组
    for(int i=0;i<n;i++)
    {
        cout<<R[i];
        if(i==n-1)
            cout<<endl;
        else
            cout<<" ";
    }
}
void Partition(int a[],int n)
{//将正整数构成的集合划分为两个不相交的子集A1和A2
/**************begin************/
    int low=0,high=n-1;        //分别指向表的下界和上界
    int low0=0,high0=n-1;      //分别指向新的子表的下界和上界
    int flag=1;               //标记划分是否成功
    int k=n/2,i;             //记录表的中间位置
    while(flag)             //循环进行划分
    {
        int pivotkey=a[low];      //选择枢轴
        while(low<high)              //从两端交替地向中间扫描
        {
            while(low<high&&a[high]>=pivotkey) --high;    //从最右侧位置依次向左搜索
            if(low!=high) a[low]=a[high];                 //将比枢轴记录小的记录移到低端
            while(low<high&&a[low]<=pivotkey) ++low;      //从最左侧位置依次向右搜索
            if(low!=high) a[high]=a[low];                 //将比枢轴记录大的位置移到高端
        }
        a[low]=pivotkey;                        //枢轴记录到位
        if(low==k-1)                          //满足条件①,枢轴的位置是n/2的前一位置
            flag=0;                          //划分成功,下次循环将退出划分
        else
        {
            if(low<k-1)          //满足条件②,枢轴low及之前的所有元素均属于A1
            {
                low0=++low;           //继续对low之后的元素进行划分
                high=high0;
            }
            else           //满足条件③,枢轴low及之后的所有元素均属于A2
            {
                high0=--high;     //继续对low之前的元素进行划分
                low=low0;
            }
        }
    }
    for(i=0;i<k;i++)         //输出子集A1
    {
        if(i==k-1)
            cout<<a[i]<<endl;
        else cout<<a[i]<<" ";
    }
    for(i=k;i<n;i++)        //输出子集A2
    {
        if(i==n-1)
            cout<<a[i]<<endl;
        else cout<<a[i]<<" ";
    }
    return ;
    /**************end************/
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        int *a=new int[n];
        for(int i=0;i<n;i++)  //输入数据
        {
            cin>>a[i];
        }
        Partition(a,n);
    }
    return 0;
}

?

?

?

?

文章来源:https://blog.csdn.net/a61233/article/details/135446391
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。