文档章节

利用快排思想排红绿蓝小球

曾劲松
 曾劲松
发布于 2016/04/14 10:26
字数 314
阅读 16
收藏 0

        对于红绿蓝三种小球这个问题,类似快排中 partition 过程。不过,要用三个指针,一前 begin,一中 current,一后 end,俩俩交换。

    while(current<=end){

        1、 current 指 1 ,current++

        2、 current 指 0,与 begin 交换,而后 current++, begin++,

        3、 current 指 2,与 end 交换,而后, current 不动, end--。

     }

    具体代码:

inline void swap(int &a,int &b){
    int tmp=a;
    int a=b;
    int b=tmp;
}

void Sort_RGB(int a[],int start,int last){
    if(start>=last) return;
    
    int begin=start;
    int current=start;
    int end=last;
    while( current<=end )
    {
        if( array[current] ==0 )
        {
            swap(array[current],array[begin]);
            ++current;
            ++begin;
        }
        else if( array[current] == 1 )
        {
            ++current;
        }
        else //When array[current] =2
        {
            swap(array[current],array[end]);
            --end;
        }
    }
    //最终begin指向第一个绿球,current指向第一个蓝求
    return;
}

优化写法(其实也不优化,但是能够减少交换次数):

inline void swap(int &a,int &b){
    int tmp=a;
    int a=b;
    int b=tmp;
}

void Sort_RGB(int a[],int start,int last){
    if(start>=last) return;
    
    int begin=start;
    int current=start;
    int end=last;
    while( current<=end )
    {
        if( array[current] ==0 )
        {
            swap(array[current],array[begin]);
            while(array[++current]==1){};//找到非绿球
            begin++;
        }
        else if( array[current] == 1 )
        {
            while(array[++current]==1){};//找到非绿球为止
        }
        else //When array[current] =2
        {
            swap(array[current],array[end]);
            while(array[--end]==2){};//找到非蓝球为止
        }
    }
    //最终begin指向第一个绿球,current指向第一个蓝求
    return;
}


© 著作权归作者所有

曾劲松
粉丝 5
博文 200
码字总数 141434
作品 0
武汉
私信 提问
被忽视的 partition 算法

如果你学习过算法,那么肯定听说过快速排序的大名,但是对于快速排序中用到的 partition 算法,你了解的够多吗?或许是快速排序太过于光芒四射,使得我们往往会忽视掉同样重要的 partition ...

selfboot
2016/08/31
0
0
算法学习笔记(一)-----彩色小球排序

“有红黄蓝三色小球若干排成一列,这些小球进行排序,请使用尽量少的空间和时间”---来自微信号"九章算法" 思想:同色小球之间应该没有差别,所以用1,2,3分别表示红黄蓝,使用数组ordered_b...

夏尘安
2014/03/24
72
0
快速排序,找中位

陆小凤原创 小白:快速排序算法,这么上古的东西,而且每一种语言都有相应的实现,还需要学吗? 陆小凤:如果目标是解决常规的业务开发,那就没有理由去做这样的事情,有时间还不如去理解业务...

奇哥十年程序
2017/12/08
0
0
快排以及基于快排思想的topk 一锅端demo

算法不好,补补基本的排序算法,弄懂了快排,发现topK问题中也能用快排的思想所以写了一个demo 填坑解释法解释快排很形象,我是看这篇看懂快排的,这里推荐一下 http://blog.csdn.net/chengqi...

霁雪清虹
2017/11/10
0
0
合并排序,合为重

陆小凤原创 小白:陆大侠,从快排到合排,算法思想有变化吗? 陆小凤:在设计思想上,它们是一样的,都是“分而治之”的思想。 小白:“分而治之”,就是我老板常说的话啦:“没有什么是搞不...

奇哥十年程序
2017/12/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【在 Nervos CKB 上做开发】Nervos CKB 脚本编程简介[3]:自定义代币

原文作者:Xuejie 原文链接:https://xuejie.space/2019_09_06_introduction_to_ckb_script_programming_udt/ Nervos CKB 脚本编程简介[3]:自定义代币 CKB 的 Cell 模型和 VM 支持许多新的用...

NervosCommunity
54分钟前
5
0
通过OAuth2.0 获取授权访问SF 用户数据

通过OAuth2.0 获取授权访问SF 用户数据 OAuth2.0 相关知识 深入了解 Salesforce 中的 OAuth 2.0(SF官方) OAuth 2.0 的一个简单解释(阮一峰大神) OAuth 2.0 的四种方式(阮一峰大神) GitHub OA...

在山的那边
59分钟前
7
0
编写程序:从键盘上接受一个三位数(首先要确保是三位数),计算出各位之和输出。

#include<stdio.h> int main() { int a,sum=0; printf("请输入一个三位数:\n"); scanf("%d",&a); sum=a/100+a%100/10+a%10; printf("这三个数的和:%d",sum); return 0; }......

201905021729吴建森
今天
7
0
如何离开/退出/停用Python virtualenv

我正在使用virtualenv和virtualenvwrapper。 我可以使用workon命令在virtualenv之间切换。 me@mymachine:~$ workon env1(env1)me@mymachine:~$ workon env2(env2)me@mymachine:~$ workon e......

技术盛宴
今天
7
0
成长之路 万事坚持难

任何事情开了头,想要更好的发展下去,不忘初心,就一定要坚持下去。 以前自己坚持了一些事情,比如早睡不吃东西,由于中途断了,没有及时止损,导致又接着恶习断了几天。所以 及时的反省和调...

T型人才追梦者
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部