Quicksort

最近公司打算招一个新的程序,之前我们的策略一直是只面试并没有笔试题。我想了下笔试题最好不要过于偏重于哪一门语言或者哪一方面的知识,那么最好的就是大学学习的基本知识,包括算法和数据结构等,我也打算让面试者在面试过程中实际写一些代码。因为,通过聊天来判断一个人能力是否合格太虚了。基于此原因,我自己事先去复习了一下快速排序(Quicksort)的知识,并且实现了好几个快速排序的算法,这里会简单介绍 3 个重要的快速排序算法。

1 简介

Robert Sedgewick(《算法》的作者,书写的非常好,当然人肯定是大牛) 称快速排序是 20 世纪最重要的 10 个算法之一,快速排序几乎被用于任何重要的系统排序(system sorts)中,被许多语言标准库作为默认排序算法实现,比如 C 语言中 qsort 就是典型的例子。

快速排序最早由 Tony Hoare 于 1959 年发现的,后期经过了不断的发展、论证得到了许多别的优化方案。在恰当实现的情况下,其性能是归并排序(Mergesort)和堆排序(Heapsort)的 2~3 倍。

快速排序是一种比较排序算法,能够对任何支持 less then 关系的数据进行排序,它不是一种稳定排序(stable sort),意味着相等的元素的相对位置可能会发生改变。对于额外的内存需求很少,这种特定也叫就地排序(in-place sort)。计算机科学家对快速排序做了相当多的研究,在数学上的分析得到平均比较次数是 O(n log n) ,最坏的情况是 O(n^2) 次比较。

阅读全文 “Quicksort”

vimbook-OPL(11-13)

CH11 Dealing with Text Files(处理文本)

这一章主要讲将 Vim 用作类似字处理器时所提供的功能,包括自动文本回绕,文本格式化命令,自动文本格式化选项(formatoptions)以及处理不同操作系统下的换行符还有就是字处理器 Troff 相关的命令,最后介绍了 Vim 自带的 rot13 算法混淆功能。

11.1 自动文本回绕

自动文本回绕在处理注释或者写文档时十分有用,一般我们要求文档一行的长度不要超过 80 字符,如果每次都需要手动插入换行符是相当累的一件事。Vim 提供了自动换行的功能,通过选项 :set textwidth=80 当输入的文本长度超过 80 字符时将自动插入一个换行符。还有一种可以设置右边边距的选项 :set wrapmargin=10 当插入的字符距离屏幕右边 10 列时将自动插入一个换行符。这个选项只有在 textwidth 为 0 的情况下才会生效。书中原文是 The ‘textwidth’ option overrules ‘wrapmargin’.

gq{motion} 命令能够对选中的文本块进行自动排版,gq 在未配置的情况下使用内部排版机制,内部排版机制依据 textwidth 和 formatoptions 来进行排版。{motion} 可以是 4j 这样的表示下行 4 行,更为常见的是 } 表示从当前位置到段落尾部,或者 ip 表示当前段落。ip 这种 {motion} 是文本对对象在帮助文档 :h object-select 中可以找到完整的解释。

gqq 可以格式化当前行。

阅读全文 “vimbook-OPL(11-13)”

vimbook-OPL(8-10)

CH8 Basic Abbreviations, Keyboard Mapping, and Initialization Files(基本缩写,映射和初始化文件)

Vim 提供了重要的功能来帮助快捷完成重复任务,比如缩写、键盘映射以及初始化文件 .vimrc

8.1 缩写

通过缩写可以完成将很长而且特定的文本用很简单的几个按键就可以完成,比如:注释头尾、版权申明等,以下

:abbreviate #b /***************************
:abbreviate #e <Space>********************/

当你在文本中按下 #b 时,并且继续按下空格或者 <Esc> 时,缩写会自动展开,值得注意的是在扩展中空格的表示,这是 Vim 特有的字符转义码。:abbreviate 能够显示所有的现有缩写。

8.2 映射

:map 命令可以将多个 Vim 命令绑定到一个单独的键上,例如:

:map <F5> i{<Esc>ea}<Esc>

可以让你在按下 F5 时,就在单词的两边加上一个 {} ,但是首先你得到单词的左边边界—— b 命令就可以。:map 命令列举当前所有的映射。

阅读全文 “vimbook-OPL(8-10)”

vimbook-OPL(5-7)

Chapter 5 Windows

5.1 打开新窗口

分屏的命令有以下命令:

  1. :sp 上下分屏,:vs 左右分屏
  2. CTRL-W_CTRL-W在窗口之间切换
  3. CTRL-W_h CTRL-W_j CTRL-W_k CTRL-W_l 进行左右上下窗口切换,用 :h CTRL-W_h 可以查看对应的帮助文档。
  4. :sp file 可以在分屏的同时打开文件,在执行任何打开操作时可以用 +command 打开头执行的一条命令,如:
    :sp +/sprintf three.c
    

    在分屏打开文件后马上执行搜索 sprintf 的命令。

  5. CTRL-W_K 将当前窗口放在最顶部的位置,CTRL-W_L 将当前窗口放在最右边的位置,CTRL-W_H 将当前窗口放在最左边的位置,CTRL-W_J 将当前窗口放在最下边的位置;

5.2 控制窗口大小

在sp前面带上数字,会成为新打开的窗口的行数,形如: :10sp alpha.c 将在上下分屏,并且新打开的窗口大小是10行。用 [N]CTRL-W_+ [N]CTRL-W_- 分别增加或减小当前窗口的大小,[N] 指定增加减少的行数,不提供时默认为1行,用 CTRL-W_=将屏幕对半平分。

阅读全文 “vimbook-OPL(5-7)”

vimbook-OPL(1-4)

Chapter 2 Editing a Little Faster

  • ZZ 写回当前文件,并退出,与 :x功能相同
  • w b 向右或向左移动到单词的头部
  • W B 向右或向左移动到字串的头部
  • e ge 向右或向左移动到单词的尾部
  • E gE 向右或向左移动到字串的尾部
  • f{char} F{char} 向右或向左查找字符{char},光标停留在字符上,; 同方向继续搜索,, 反方向继续搜索;
  • t{char} T{char} 向右或向左查找字符{char},光标停留在字符之前,; 同方向继续搜索,, 反方向继续搜索;
  • CTRL-G 在状态栏显示目前光标在文件中的位置
  • CTRL-U 命令向上移动半屏
  • CTRL-D 命令向下移动半屏
  • [count]G 分别移动到count行
  • [count]J 将光标下的count行合并,空行会去掉,非空行用空格分隔
  • r{char} 把光标下的字符换成 {char}
  • ~ 切换光标下字符的大小写,并把光标右移
  • q{0-9a-zA-Z"} 在寄存器 {0-9a-zA-Z”} 里录制宏,并以q退出保存,用 @{0-9a-zA-Z”} 执行。如用 qa 开启记录,其后的所有命令直到再次遇到 q 之前的所有命令都放到录制的 a 宏中,通过 @a 在文件上执行里边的命令。
  • CTRL-K{char}{char} 显示digraphs字母,目前只在命令模式中实验成功,插入模式还没有成功,CTRL-K_S_E “§”

阅读全文 “vimbook-OPL(1-4)”