选取序列的第i小元素又称为选择问题，第i小的元素又称为第i个顺序统计量。简单的，排序之后我们可以立即找到第i小的元素，这种方法的时间复杂度是排序的时间复杂度，下界是O(nlogn)。但是选取第i小元素显然和排序相比要更简单，所以我们有理由相
选取算法：中位数和第k小数
计数排序和基数排序
基于比较的排序的时间复杂度下界是O(nlogn)，但是当要排序的元素具有一些特殊性质的时候，可以使用非比较的方法突破这种限制。 计数排序 当待排序的元素a[]都是位于区间[0,k]中的整数时，可以使用计数排序。计数排序顾名思义就是统计元素的
基于比较的排序算法的下界
在排序的结果中，各个元素的次序依赖于他们之间的比较，这种排序算法叫做比较排序。基于比较的排序有O(n^2)的冒泡排序、插入排序等，也有O(nlogn)复杂度的归并排序、堆排序等。实际上，O(nlogn)在渐进意义上是最优的。 假设我们有n个
堆和堆排序
数据结构中的堆和程序语言中的堆的意义并不相同，这里的堆是一种数据结构。二叉堆可以分为最大堆和最小堆，这里介绍最大堆。在最大堆中，结点的值满足堆的性质：除了根节点外，所有结点都不会比它的父节点大。 可以看到，逻辑上的堆是二叉树，但堆的物理结构
向量叉积和应用：判断点是否在三角形内部
本文是学堂在线计算几何课程 凸包一章的部分学习笔记。如果要求编程判断一个点是否在三角形（三个点）内部。 可以看出，如果点在三角形的内部，沿着三边走一圈，这个点相对于行进路径始终保持相同方向（图中一直在左边）； 如果点在三角形的外部，沿着三条
用两个栈模拟队列，快速获得队列的最大值
队列是一种常用的数据结构。如果按照常规的想法，要获得队列中的最大值，必须遍历队列中的所有元素，时间复杂度为O(n)。怎么降低这个时间呢？求最大元素很容易想到堆。如果建立一个辅助的最大堆（里面存放队列中元素的指针以及值），入队或者出队的时候，
使用主定理求解递归式
算法导论中的4.5节介绍了一个用于求解递归式的主定理，可以用来求解部分形如下面形式的递归式： ，其中a>=1 , b >1 ，其中a>=1 , b >1 描述的算法 把规模为n的问题分为a个子问题，每个子问题规模是n
详解快速排序
快速排序通常是在实际应用中排序的最好算法，虽然在最坏情况下它的时间复杂度是O(n^2)，但是在平均情况下，它的时间复杂度是O(nlogn)，并且它的常数因子非常小，因此效率极高。 下面的描述中对数组a中的[lo,hi)进行排序。（[lo,h
最大子列和问题
给定K个整数组成的序列{ N1, N2, …, NK }，“连续子列”被定义为{ Ni, Ni+1, …, Nj }，其中 1 <= i <= j <= K。“最大子列和”则被定义为所有连续子列元素
数组中找两个数字之和为指定值
快速找出一个数组中的两个数字，让这两个数字之和等于一个给定的值. 数组a[n] ，要找出两个数字 和为x O(n^2)的算法 很容易我们可以写出这么一个粗暴的算法，那就是两两比较，看有没有符合要求的