排序算法的应用

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

提示:

利用快速排序思想解决。由于要求“对每粒砾石的颜色只能看一次”,设3个指针i,j和k,若将j看作工作指针,将r[1..j-1]作为红色,r[j..k-1]为白色,r[k..n]为兰色。从j=1开始查看,若r[j]为白色,则j=j+1;若r[j]为红色,则交换r[j]与r[i],且j=j+1,i=i+1;若r[j]为兰色,则交换r[j]与r[k];k=k-1。算法进行到j>k为止。为方便处理,将三种砾石的颜色用整数1、2和3表示。

代码如下:

#include "assert.h"
#include <iostream>
using namespace std;

void Swap(int &a,int &b)
{
    int temp;
    temp=a;
    a=b;
    b=temp;
}
void Sort(int a[],int n)
{
    int i=0,j=0,k=n-1;
    while(j<=k)
    {
        if(a[j]==1)
        {
            if(i!=j)
        {
            Swap(a[i],a[j]);
            cout<<i<<"<—>"<<j<<endl;
        }
        i++;
        j++;
        }
        else if(a[j]==3)
        {
            if(j!=k)
            {
                Swap(a[j],a[k]);
                cout<<j<<"<—>"<<k<<endl;
            }
            k–;
        }
        else
            j++;
    }
    for(int i=0;i<n;i++)
    {
        cout<<a[i];
    }
    cout<<endl;
}

int main() {
    int n;
    cin >> n; 
    int * a= new int[n];
    for (int i=0;i<n;i++)
        cin>>a[i];
    Sort(a,n);
}


You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注