雅乐网

计算机技术博客

算法

选取算法:中位数和第k小数

选取算法:中位数和第k小数

选取序列的第i小元素又称为选择问题,第i小的元素又称为第i个顺序统计量。简单的,排序之后我们可以立即找到第i小的元素,这种方法的时间复杂度是排序的时间复杂度,下界是O(nlogn)。但是选取第i小元素显然和排序相比要更简单,所以我们有理由相

计数排序和基数排序

计数排序和基数排序

基于比较的排序的时间复杂度下界是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。“最大子列和”则被定义为所有连续子列元素

归并排序

归并排序

归并排序是分治思想的典型应用。它的基本步骤有3步: 1. 划分。将要排序的数组分为两部分。 2. 递归求解。分别递归使用归并排序将两部分排序。 3. 合并。将两个有序的序列合并为一个有序的序列。 将序列分为两部分用时O(1),而对子序列进行

冒泡排序:思路、详解、C语言实现

冒泡排序:思路、详解、C语言实现

冒泡排序是一种很常见的简单排序。它依次扫描要排序的序列,比较两个相邻的元素,如果逆序就交换位置。 每次经过扫描一趟后,未排序部分最大的元素就“冒泡”到了最上面。 函数接口 void bubble_sort1(int *a, int low,

详解二分查找算法

详解二分查找算法

二分查找是一个用于有序数组查找的常用算法。它的基本思想非常简单,以至于我们都会自认为已经掌握。但是,纸上得来终觉浅,当实际动手的时候,还是会发现许多问题。下面雅乐网整理了一下二分查找算法的实现。 思想 先看看维基百科的说法: 二分查找的搜索

希尔排序

希尔排序

希尔排序(Shellsort),是插入排序的一种更高效的改进版本,它是使排序算法冲破O(n^2)的第一批算法。它对插入排序的改进之处在于改变了插入排序一次只能移动一位的缺点。 希尔排序通过比较相距一定间隔的元素进行排序,通过对相隔一定步长的

插入排序

插入排序

插入排序是一种简单排序。对于少量元素的排序它很有效。 插入排序的工作方式类似于玩扑克牌抓牌时的排序 开始的时候左手为空,每次从桌子上拿走一张牌并把它插入到左手中正确的位置。可以从右到左依次比较。拿在左手上的牌总是有序的。 c++实现

c语言数据结构算法演示(Windows版)

c语言数据结构算法演示(Windows版)

本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行过程中栈的变化状况。整个系统使用菜单驱