从快速排序法看好的算法需要的思维意识

** 人脑趋向于将问题扁平化,这样思考问题时的认知负荷小。这就是我们常说的清清楚楚。**
如果你习惯沿着让人脑舒适的路线来设计算法,你就无法最大限度的发挥电脑的特长,让电脑高效的解决问题。比如,递归。要把递归过程中的每个环节想清楚,对于人脑来说是存在巨大的认知负荷的。人脑的运行内存是很小的,偏偏递归是一种内存开销大的编程模式。

今天尝试用js来实现快速排序法(虽然js的Array已经自带有排序函数,但是为了训练思维,还是动手去体会了一下个中的各种坑)。网上有一篇文章,用漫画的形式非常清楚的解说了快速排序法的原理。看完原理之后,原本以为自己动手可以很轻松的写出这个算法来。然而现实并不是那么一回事。

坑一

从漫画看明白了,快速排序法通过递归的方式一遍遍将数组切割成左右两个部分,然后通过相同的方式进行换位操作。但是在写代码时,我却下意识的希望一开始就将排序过程中那些出现的“子数组”在一开始就计算出来。但是,实际上这是不可能的,“子数组”是在一遍遍递归过程中生成的。所以,还是扁平化思维在作祟,否则,这是显而易见的问题。

坑二

我没有接受过C语言编程的训练,所以对指针的理解很粗浅,更缺乏感性认识。在快速排序法中,一开始我试图用for循环来实现指针偏移,但是实际上这里的逻辑决定了一开始你并不知道循环的长度有多少。所以,合理的应该是使用while循环来实现。另外,循环语句执行的结果是什么?一开始,下意识会认为是确定要进行换位的数(元素)——即结果(这又是一种扁平化思维的影响),但是实际上更为合理的方法应该是确定指针的位置,有了指针无论如何你都可以根据它去得到你想要的东西。

代码

最后将实现代码记录一下:

var arr=[213, 35, 2, 700, 277, 21, 486, 17, 919, 615];
fsort(arr,0,arr.length-1);

function fsort(arr,left,right){
    var i,j,t,temp;
    if(left>right){
        /*console.log('complete');
        console.log(arr);*/
        return;
    }

    console.log(arr.slice(left,right+1))

    i=left;
    j=right;
    temp=arr[left];//基准数

    while(i!=j){
        while(arr[j]>=temp && i<j)j--;
        while(arr[i]<=temp && i<j)i++;
        if(i<j){
            t=arr[i];
            arr[i]=arr[j];
            arr[j]=t;
        }
    }

    arr[left]=arr[i];
    arr[i]=temp;

    fsort(arr,left,i-1);
    fsort(arr,i+1,right);

}

反思

就像前些天写将思维简图的录入数据结构化的算法一样,算法首要确定的是元素之间的关系。在这个例子中,“关系”即“指针”;在思维简图的例子中,“关系”则是那些自己创造的描述节点关系的字段值。先瞄准计算出这些内容,才能帮你更好的发挥电脑的能力,也让编程更加灵活。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 218,122评论 6 505
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,070评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 164,491评论 0 354
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,636评论 1 293
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,676评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,541评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,292评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,211评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,655评论 1 314
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,846评论 3 336
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,965评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,684评论 5 347
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,295评论 3 329
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,894评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,012评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,126评论 3 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,914评论 2 355

推荐阅读更多精彩内容