本帖最后由 千秋夕月 于 2016-12-14 10:22 PM 编辑
此贴为C/C++学习入门导航的子贴,意在解决C语言初学者所遇到有关入门级题目的问题。提问的小伙伴请阅读以下注意事项。

所有的提问请参照以下格式进行编辑(不符合格式的回帖一律删除,评分区除外):

1.若此问题在此帖中为首次出现,请按照以下格式书写:
   提问:此处填写内容,请详细描述。

2.若此问题已经被解答过,请按照以下格式书写:
   追问#1:此处填写内容,请详细描述(若对某个回答有追问,其他格式不变,同时请按照对回答楼层的回复方式进行提问)。
   注意:#1代表对一楼所提问题的追问,依此类推。

回答格式:一律以对楼层回复的方式进行回答。

请按照格式进行提问,以便于后来提问的小伙伴们进行查阅。为保证回答质量,对于错误的答案及重复的问题管理组将予以删除,请谅解。

[NG]

 

                                                  

nextgod.com我是下一个神!
回复
【点击@我】

使用道具 举报

     
收藏
4 条回帖
大白编程小白2016-12-14 22:28:31
提问:程序员能20分钟徒手写出一个没bug的快速排序吗(可以调试)?
nextgod.com我是下一个神!
     
千秋夕月正式版主2016-12-14 22:35:07
大白 发表于 2016-12-14 10:28 PM
提问:程序员能20分钟徒手写出一个没bug的快速排序吗(可以调试)?

当然可以啊~
看过Jon Bently那个快排,一辈子都忘不了了,背下来就可以了。
[C++] 纯文本查看 复制代码
void quicksort(int l, int u){
    int i, m;
    if(l >= u) return;
    m = l;
    for(i = l+1; i<= u; i++)
        if(x[i] < x[l]) // buggy!
            swap(++m, i);

    swap(l, m);

    quicksort(l, m-1);
    quicksort(m+1, u);

}
nextgod.com我是下一个神!
     
大白编程小白2016-12-14 22:39:20
千秋夕月 发表于 2016-12-14 10:35 PM
当然可以啊~
看过Jon Bently那个快排,一辈子都忘不了了,背下来就可以了。
[mw_shl_code=cpp,true]voi ...

追问#2:谢谢!可以详细的解释下吗?
nextgod.com我是下一个神!
     
千秋夕月正式版主2016-12-14 22:48:03
大白 发表于 2016-12-14 10:39 PM
追问#2:谢谢!可以详细的解释下吗?

上面是他在 beautiful code 上的代码。
最核心的部分就是开始的那个for循环和swap了(paritition),这要怎么背呢?当然是用循环不变式了!
[l+1, m] 位置保存着当前已处理元素之中所有的小于pivot的元素
i指向的是下一个待处理的元素
第l个元素是pivot
循环开始时,[l+1, m]是空集,已处理元素也是空的,所以循环不变式成立。
for循环每轮把i加了1,这样就有可能破坏循环不变式,
怎么办呢,当然是:
在i加1之前,如果发现当前i指向的值小等于pivot,就将m自增1,并且和i指向的元素交换。
这样,循环不变式又成立啦。
在for循环结束后,循环不变式依然是成立的(根据数学归纳法~)
那么,它告诉了我们什么性质呢?
[l+1, m]之间包含了l 到 u 之间的小于 pivot 的元素,且第l个元素是pivot。
于是,我们只要将第l个元素和第m个元素交换,就完成了partition的操作,即:pivot在第m个元素上,m元素之前的值都小于pivot,之后的值都大等于pivot。

非常简洁,非常酷炫,但是有点bug(注意我注释的那一行)
这个partition在大量duplicate key的情况下,会把这些key全部放到左边或者右边。导致不公平的切分。

partition要保证在中间把数组分开,可以看这个代码:
代码中,数组不是被切成两份,而是三份,中间那份包含了所有和pivot相同的key。
左边和右边那份分别是比pivot小和比pivot大的key,递归调用仅在它们之上执行,中间那份在partition后就保留在原地不动了。
[C++] 纯文本查看 复制代码
public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
        assert isSorted(a);
    }

    // quicksort the subarray a[lo .. hi] using 3-way partitioning
    private static void sort(Comparable[] a, int lo, int hi) { 
        if (hi <= lo) return;
        int lt = lo, gt = hi;
        Comparable v = a[lo];
        int i = lo;
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if      (cmp < 0) exch(a, lt++, i++);
            else if (cmp > 0) exch(a, i, gt--);
            else              i++;
        }

        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 
        sort(a, lo, lt-1);
        sort(a, gt+1, hi);
        assert isSorted(a, lo, hi);
    }
nextgod.com我是下一个神!
     
您需要登录后才可以回帖 登录 | 加入NG 新浪微博登陆

本版积分规则

快速回复 返回列表 客服中心 搜索 官方QQ群
返回顶部
现在加入NG编程论坛!注册一个账号 账号登陆 QQ账号登陆