设有顺序放置的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>a[i];
Sort(a,n);
}/* PRESET CODE END - NEVER TOUCH CODE ABOVE */ 前置代码
/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */#include "assert.h"#include using namespace std;
/* PRESET CODE END - NEVER TOUCH CODE ABOVE */ 例如:
| 输入 | Result |
|---|---|
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<"<"<
【数据结构与算法学习|数据结构与算法作业8（排序算法的应用）】
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- matlab机械臂工作空间代码|matlab机械臂工作空间代码_【ROS-Moveit!】机械臂控制探索（3）——基于python的API示例代码分析...
- opencv|opencv学习笔记（二） 图像腐蚀和膨胀
- opencv|opencv学习笔记（四） 绘制几何图形
- opencv|opencv 学习笔记（五） findContours（） 函数与drawContours（） 函数
- opencv|opencv 学习笔记（六） 一周总结
- opencv|opencv学习笔记（三）颜色转换 cvtColor
- opencv|opencv 图片上画一条线
- opencv|opencv 学习笔记（一） 矩阵构造之输出
- 《C++要笑着学》|【C++要笑着学】从零开始实现日期类 | 体会代码的复用 | 提供完整代码