数据结构与算法作业8：排序算法的应用

设有顺序放置的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表示。

预设代码

后置代码

/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */



int main() {

int n;

cin >> n; 

int * a= new int[n];

for (int i=0;i<n;i++)

cin>>a[i];

Sort(a,n);

}



/* PRESET CODE END - NEVER TOUCH CODE ABOVE */

前置代码

/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */



#include "assert.h"

#include <iostream>

using namespace std;





/* PRESET CODE END - NEVER TOUCH CODE ABOVE */

例如:

6 1 2 3 3 2 1

2<--->5
1<--->2
3<--->4
112233

答案： 

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

文章来源: blog.csdn.net，作者：渣渣ye，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/yyfloveqcw/article/details/123760759