编程(3)

与归并排序一样,快速排序也使用了分治思想。下面是对一个典型的子数组A[p..r] 进行快速排序的三步分治过程:

分解:数组A[p..r]被划分为两个(可能为空)子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每一个元素都小于等于A[q],而A[q]也小于等于A[q+1..r]中的每个元素。其中,计算下标q也是划分过程的一部分。

解决:通过递归调用快速排序,对子数组A[p..q-1]和A[q+1..r]进行排序。

合并:因为子数组都是原址排序的,所以不需要合并操作:数组A[p..r]已经有序。

golang 中的  poolDequeue 是 ring buffer 的一种实现. ring buffer 是一种无锁循环队列。这里的 poolDequeue 仅支持1个生产者，但可以有多个消费者（通过 CAS 实现），因为无锁，所以性能非常好。ring buffer 这里不展开，网上很多资料。

这里重点通过 eface 和 dequeueNil 来阐明golang 中的 interface{} 是由 type 和 value 2个机器字组成。当 type 和 value 都为nil(即null ) 时, 才为 nil 的interface；当 type!=nil，value==nil 时，不是 nil 的interface.

B树的定义

B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树，如下图。B树是Bayer 和 McCreight在1972年提出来的，但是他们并没有解释为什么取名为B树。B树类似于红黑树, 但它们在降低磁盘I/O操作数方面要更好一些。许多数据库系统使用B树或者B树的变种如B+树来存储信息。B树与红黑树的不同之处在于B树的结点可以有很多孩子,从数个到数千个。也就是说,一个B树的“分支因子”可以相当大,尽管它通常依赖于所使用的磁盘单元的特性。B树类似于红黑树,就是每棵含有n个结点的B树的高度为O(log[n])。然而,一棵B树的严格高度可能比一棵红黑树的高度要小许多,这是因为它的分支因子,也就是表示高度的对数的底数可以非常大。因此,我们也可以使用B树在时间O(log[n])内完成一些动态集合的操作。