c++

树状数组

树状数组,是一个用于在近似 $O(logn)$ 时间内动态修改以及查询前缀和的数据结构,以下我们先来看以下树关系表格 层 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 16 2 8 12 14 15 3 4 6 7 10 11 13 4 2 3 5 9 5 1 这里表达的是,16的子节点有8, 12, 14, 15 8的子节点有4, 6, 7 12的子节点有10, 11,即夹在12与它的同级节点8之间 我们把数值与它的二进制一起形象化画出下图 graph TD; 2,0010-->1,0001 4,0100-->3,0011 4,0100-->2,0010 6,0110-->5,0101 8,1000-->7,0111 8,1000-->6,0110 8,1000-->4,0100 10,1010-->9,1001 12,1100-->11,1011 12,1100-->10,1010 14,1110-->13,1101 16,10000-->8,1000 16,10000-->12,1100 16,10000-->14,1110 16,10000-->15,1111 这样构造的原理是运用到一个二进制运算技巧,假设一个节点x,那么它的父节点就是x + (x & -x),其中,x & -x是去掉右起第一个1的左边的1,例如x如果是6,二进制是110,只保留最右边的1结果就是10了,所以6的父节点就是6+2=8,更多的可以参考这篇二进制技巧。

Quick sort(快速排序)杂谈 3

在上一篇我们介绍了快排的各种优化,最后得到了一个超越VS的STL std::sort实现的版本,这回我们来讲讲怎么折磨gcc的std::sort。 GCC的实现 这个我直接给个github来源,链接里是gcc8分支的实现源码,我已经通过链接标记出第1896行,那里就是__unguarded_partition函数的实现,就是快排的划分函数,而在后面几个函数就是快排的本体了。为了避免它代码更新导致位置变化,我把相关代码复制过来。

Quick sort(快速排序)杂谈 2

在上一篇我们介绍了四种不同的划分算法,现在我们来针对Hoare partition scheme来讲解一些优化和注意的问题。 最坏时间复杂度的优化 在前一篇的示例代码里面,只是最简单地选择的最开头或最后面的元素作为划分,这对于乱序的数据还好,对于有序的数据这么做,时间复杂度就直接变成$O(n^2)$了,那么怎么解决?第一个要解决的反而不是划分元素的选择上,而是改成intro sort,记录递归深度或类似的办法,到达限制条件的时候改而使用堆排序,这属于混合排序,先让排序的最坏时间复杂度降下来是第一要务。所以可以改写出以下代码:

smooth sort与weakheap sort实现

本篇补充smooth sort和weakheap sort,不打算做太多介绍,因为自己太菜不会讲,只作为笔记来记录一下实现代码。smooth sort在接近排序完成的情况下的动态图

堆排序优化思路

堆排序其实是最不好优化的一个,在数据结构都确定的情况下,优化空间太小,除非优化数据结构本身,但那样就不叫做堆排序了。类似堆排序的还有smooth sort和weakheap sort,有兴趣可以自己查找相关资料。 堆排序原理 堆排序其实是选择排序的优化变种,选择排序是把最大或最小的元素放到最边上,然后不断重复以上过程,堆排序也是如此,只不过堆排序通过构建数据结构,让查找最大或最小元素并放到最边上的速度比选择排序快得多。 首先我们先来介绍什么是堆。堆只是个缩写,全名是二叉堆,是一种完全二叉树,它的特点是二叉堆的父节点元素不小于子节点的元素,以下为二叉堆例图 graph TD; 30-->29 30-->28 29-->24 29-->25 28-->26 28-->22 24-->21

素数判断和因子分解

这里记录的是素数判断 Miller Rabbin 的快速判定算法,而分解使用的算法是 Pollard Rho 的玄学分解算法,这个算法的理论依据是生日悖论,这里不具体讨论这个数学问题,具体讨论看前面链接就可以了。 以下我们分别简要介绍这两个算法的原理 首先这是Miller Rabbin的维基百科介绍页,由于页面是中文,这里不做重复介绍。 下面简要解释一下Pollard’s Rho算法的原理,这是它的维基百科页面 首先我们来定义这样一个函数 $$f(x)=(x*x+c)%n$$ 其中n是需要被分解的数,c是一个任意小于n的正整数常数。那么我们给一个初始值x1,通过计算 $f(x1)$ 得到x2,然后去求 $|x1-x2|$ 与 n 的最大公约数,只要结果大于1就找到了分解结果。那如果最大公约数仍然是1,那么就通过刚才的x2求出 $x3=f(x2)$ 并计算 $|x1-x3|$ 与 n 的最大公约数。也就是说,我们可以通过这个公式得到一个数列

二进制技巧

二进制位运算的技巧特别多,这里就做一份cheat sheet,希望能帮助到大家。不过过于简单的就不列举了 单行表达式 作用 表达式 把右边连续的1变成0 n & ( n + 1 ) 把右边第一个1变成0 n & ( n - 1 ) 把右起第一个0变成1 n | ( n + 1 ) 把右起连续的0变成1 n | ( n - 1 ) 取右边连续的1 n ^ ( n + 1 ) 去掉右起第一个1的左边 n & -n 或 n & ( n ^ ( n - 1 ) ) 高低位交换,前x位 ( n << x ) | ( x >> ( 32 - x ) ) 有符号整数计算绝对值 ( n ^ (n >> 31) ) - (n >> 31)

插入排序与希尔排序优化思路

本篇针对插入排序和希尔排序来讲优化思路,有部分内容因为前一篇文章已经有交代,这里不重复,如果你还没有看,请先看前一篇。我们来看插入排序的动图演示 插入排序保证前面一块是有序的情况下,新增的一个元素通过向前交换到合适的位置,所以叫做插入排序。 插入排序基本实现 我们先来看插入排序的基本实现 void insert_sort(sort_element_t * beg, sort_element_t * end) { for (sort_element_t* i = beg + 1; i < end; ++i) { sort_element_t val = *i; sort_element_t* j = i; for (; j > beg && val < j[-1]; --j) { *j = j[-1]; } *j = val; } } 插入排序即使不做任何优化,效率也明显高于上篇所说的冒泡排序和选择排序。那么按照惯例,先上双向看看效果

选择和冒泡排序优化思路

本篇针对两种最基本的排序(冒泡、选择)来讲优化思路。越是简单的东西反而可能存在你越想不到的优化点。但是在开始之前,先给不了解的人讲一个设计原则的问题,我们在设计排序接口的时候,最为常见的有 void sort(type arr[], int len) 也许你也见过 void sort(iter beg, iter end) 这时候问题就来了,很多人会错误地把end认为是最后一个元素,其实不然,这两接口可以相互转换,例如我们可以写 sort(arr, arr + len) ,这样写很自然对不对,但如果你认为end是最后一个元素,那你就不得不改成 sort(arr, arr + len - 1) 。事实上,这类的接口我们需要一个统一的原则,就是左闭右开区间原则,即beg就是首个元素,而end是最后一个元素+1,即end是作为结束标志,不应该把end算在范围内。接下来下面所有的接口写法,都是以 void sort(iter beg, iter end) 这种方式写的,至于这样写有什么好处,接下来我们就看示例。 选择排序

Quick sort(快速排序)杂谈 1

我们现在使用的排序,很大比例在使用quick sort,因为它是平均速度最快的排序,但与此同时它可能也是坑最深的排序,现在我们就来讨论讨论它,因为内容较多,我计划写多篇,本篇是第一篇。 快排的思路 我们先来介绍一下快排的思路。快排的思路其实很简单,在数组中选一个元素,我们就称呼这个元素为pivot,通过与这个元素的比较,把数组划分成不比pivot大的在一边,不比pivot小的在另一边,于是就分成了两个更小的数据,对它们分别再排序就行了。但是,这个描述特别的含糊,首先是怎么选中间元素,这里面有很多不同的做法。然后就是划分了,这个划分方法非常的多,水也特别深,这里主要介绍最为常见的划分方法。