Qs&tree

快速排序与二叉树分析

复习快排的时候想到的,这里记录一下。

先看一下比较容易理解的快排算法(摘自维基):

 function quicksort(q)
 {
     var list less, pivotList, greater
     if length(q) ≤ 1 
         return q
     else 
     {
         select a pivot value pivot from q
         for each x in q except the pivot element
         {
             if x < pivot then add x to less
             if x ≥ pivot then add x to greater
         }
         add pivot to pivotList
         return concatenate(quicksort(less), pivotList, quicksort(greater))
     }
 }

稳定性

大家都说快排是不稳定的,想到个算法,发现和知乎这个问题一致(即选取pivot时总是选取第一个):https://www.zhihu.com/question/45929062

不难发现,对于上面这个简单的快排算法来说,这种优化使得其是稳定的。

高票的回答应该是指复杂版的in-place算法。

时间复杂度

我们可以模拟一下排序的过程,第一轮各元素与pivot比较时,总共需要n次比较操作。

第二轮比较时,左边的元素需要与左边的pivot比较,右边的元素需要与右边的pivot比较,总共也需要n次比较操作。

这样,做多少轮比较,时间复杂度就是多少乘以n。因快排将队列分成了左边和右边,也即是说可以将这个过程想像成一颗二叉树。在最好的情况下,就是树的深度最浅的情况,需要log n轮。在最坏的情况下,树退化成列表,需要n轮。所以最好和最坏的复杂度分别为n*log n和n^2。在平均情况下,这还是一颗二叉树,深度差不多也是log n(乘以一个系数)。

空间复杂度

同样与递归深度相关,原地+尾递归版的log n。

其他(ThreadLocal原理及Thread、ThreadLocalMap、Entry)

ThreadLocal原理

因为需要线程独享,所以底层实现是把线程独享的数据放在threadLocals(ThreadLocalMap类)成员变量里。

在ThreadLocal某一实例执行get时,内部通过Thread类静态方法currentThread获取当前线程,并返回独享的threadLocals。

然后ThreadLocal以自己为key,在ThreadLocalMap里找到value。

这样,为了在threadLocals里存放多个ThreadLocal实例,threadLocals设计为ThreadLocalMap,ThreadLocal为key,值为相应set的value。

ThreadLocalMap结构

ThreadLocalMap实现上是一个hash map,但并不继承HashMap。解决hash冲突的方法是线性探测线性探测再散列。

Entry

ThreadLocalMap自定义了一个Entry,key为弱引用(关于弱引用: Java 如何有效地避免OOM:善于利用软引用和弱引用 )。

考虑到普遍是用线程池来进行线程的操作,而线程池中的Thread不一定会被回收,为了使弱引用(Entry)对应的对象能够被回收,一般需要在ThreadLocal使用完后进行remove()将相应的强引用置为null。

ThreadLocal同样实现了get()、set()过程中的惰性清除。

B+树优点

VS 二叉平衡树

VS B树

VS HASH 在以下方面效率更高

AVL树与红黑树

跳表

跳表与B+树很像,在原始链表的基础上一级一级的增加索引实现。增删查的复杂度都为log n。

与红黑树相比,优点在于可以高效支持区间查找。

与B+树相比,优点在于算法简单。

Bitmap

用法: