NG编程论坛_免费编程教程_零基础轻松学编程_做下一个技术大神!

 找回密码
 加入NG

QQ登录

只需一步,快速开始

新浪微博登陆

只需一步, 快速开始

查看: 292|回复: 4

[原创] 导航-入门级题目问答

[复制链接] [提交至百度]

  离线 

新浪微博达人勋


扫一扫,手机继续看本帖!
已在线8天5小时40分
发表于 2016-12-14 21:43:50 | 显示全部楼层 |阅读模式

立即注册NG,提升编程能力,成为下一个神!

您需要 登录 才可以下载或查看,没有帐号?加入NG 新浪微博登陆

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

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

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

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

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

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

[NG]

 

                                                  


楼主的其他热帖
[Java编程论坛] 零基础java入门
[NG休闲娱乐区] 来放个毒
[NG休闲娱乐区] Dota2完美圣典录播
[Java编程论坛] java基础知识总结
[C语言教程] 导航-C语言学习资料
[基础练习] 导航-入门级题目问答




上一篇:任意数组的转置
下一篇:经典c程序100例(1--10)
nextgod.com我是下一个神!
回复
【点击@我】

使用道具 举报

     

  离线 

新浪微博达人勋

已在线0天3小时40分
发表于 2016-12-14 22:28:31 | 显示全部楼层
提问:程序员能20分钟徒手写出一个没bug的快速排序吗(可以调试)?
nextgod.com我是下一个神!
     

  离线 

新浪微博达人勋

已在线8天5小时40分
 楼主| 发表于 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我是下一个神!
     

  离线 

新浪微博达人勋

已在线0天3小时40分
发表于 2016-12-14 22:39:20 | 显示全部楼层
千秋夕月 发表于 2016-12-14 10:35 PM
当然可以啊~
看过Jon Bently那个快排,一辈子都忘不了了,背下来就可以了。
[mw_shl_code=cpp,true]voi ...

追问#2:谢谢!可以详细的解释下吗?
nextgod.com我是下一个神!
     

  离线 

新浪微博达人勋

已在线8天5小时40分
 楼主| 发表于 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监狱|NG编程论坛 ( 豫ICP备15026783号-1 ) NG已运行| |

GMT+8, 2017-9-22 10:28 AM

Powered by Discuz!&NG编程论坛

© 2015-2017 NextGod

快速回复 返回顶部 返回列表