排序算法对结果的唯一要求就是操作数满足全序关系:
-
如果 a≤b 并且 b≤c 那么 a≤c(传递性)。
-
对于 a 或 b,要不 a≤b,要不 b≤a(完全性)。
这个问题可以用信息论来回答。
我从 1 到 5 中挑一个数字出来让你来猜,每回合你都可以问我一个问题,我的回答“是”或“不是”(1 或 0),那么你至少需要几个回合才能保证猜出这个数字?
比较符合这个游戏精神的玩法是从自己的幸运数字(比如我的是7)开始猜起,一个一个地问我“是不是X?”, 可能你的运气足够好,一个回合就能够猜对,但是在最坏的情况下可能就需要5个回合,所以你的答案应该是“至少需要5个回合” (事实上你至少只需要一次就“有可能”猜出来,但为了“保证能”猜出来,你只好委曲求全地说 5), 换句话说这种猜法的最优下界是 5。 (平均性能是 1×1/5+2×1/5+…+5×1/5=(1+…+5)/5 = 3)
但因为你会二分,所以会这样问“是不是比3大?”……而且无论我挑出的数字是几,都只用3个回合。二分显然是一种更佳的策略,那么它好在什么地方呢? 用信息论理解:最大的熵。
英文版维基百科词条有个大致的解释:Comparison_sort, 最少次数为 log(5!) = 6.91,取整的话,就是 7。
决策树如下:
如果我们用归并排序的话,比较次数是O(nlogn),因为归并排序是全局最优解,但是在局部,归并并不都保证是最优的。
附一张快速排序的 gif 图:
相关阅读:
面试算法有必要吗?
分享到:
相关推荐
自己编写的基于java的快速排序和归并算法
基于比较的排序算法: 下界是 nlgn 1.1 SelectionSort:每次选出最下的元素,放在当前循环最左边的位置。 1.2 BubbleSort:每次比较相邻的两个数,使得最大的数像气泡一样冒到最右边。 1. 3 InsertionSort:每次拿起...
/************合并排序算法的实现******************/ int main() { int p,q,r; printf("合并排序算法的实现:\n"); printf("请输入p、q、r的值(输入格式1,12,13):"); scanf("%d,%d,%d",&p,&q,&r); printf("p=%...
基于C语言实现的若干排序算法和分析: 讨论 了几种常见的内部排序算法及其时间复杂度: 插入排序、 起泡排序、 选择排序、 快速排 序、 希尔排序、 堆排序, 并且对这几种排序算法进行 了分析比较。着重提供 了希尔...
python 归并排序算法 归并排序是一种基于分治思想的排序算法,它将待排序的序列分成若干个子序列,每个子序列都是有序的,然后再将这些有序的子序列合并成一个有序的序列。归并排序的时间复杂度为O(nlogn),是一种...
基于预排序算法、堆排序算法和计数排序算法分别编写一个排序算法。 【预排序函数原型及功能说明】 检验数组中元素的唯一性: 先对数组排序,然后只检查它的连续元素:如果该数组有相等的元素,则一定有一对元素是相互...
* 基于列表实现的元素迭代器 */ package dsa; public class IteratorElement implements Iterator { private List list;//列表 private Position nextPosition;//当前(下一个)元素的位置 //默认构造方法 ...
算法,我可以为您详细解释Java中快速排序算法的实现,并提供一个代码示例。快速排序是一种高效的排序算法,基于分治策略。其基本步骤如下: 1. 选择一个基准元素(pivot),通常选择数组的第一个元素或者最后一个...
从模糊判断矩阵的定义角度出发, 构建了基于粒子群算法的模糊层次分析模型PSO-FAHP, 提出了包含模糊判断矩阵一致性修正及各元素排序过程的非线性带约束优化问题, 引入粒子群算法实现了问题的求解, 并分析了模型的...
前面的文章已经介绍了几种排序算法,如插入排序(直接插入排序,折半插入...“定理:对于含n个元素的一个输入序列,任何比较排序算法在最坏情况下,都需要做Ω(nlgn)次比较。” 也就是说,比较排序算法的运行速度不会
⾮⽐较类排序:不通过⽐较来决定元素间的相对次序,它可以突破基于⽐较排序的时间下界,以线性时间运⾏,因此也称为线性时间⾮⽐较类排序。 冒泡排序 快速排序 简单插入排序 希尔排序 简单选择排序 堆排序 二路归并...
当然,我可以为您详细解释Java中快速排序算法的实现,并提供一个代码示例。快速排序是一种高效的排序算法,基于分治策略。其基本步骤如下: 1. 选择一个基准元素(pivot),通常选择数组的第一个元素或者最后一个...
大数据在不论在研究还是工程领域都是热点之一,算法是大数据管理与计算的核心主题。本课程试图简要介绍大数据计算中涉及到的基本算法设计方法。适用于大数据研究与开发人员,也适用于数据科学爱好者。 大数据算法这...
python冒泡排序冒泡排序是一种简单直观的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成...
目录插入排序直接插入排序基本原理代码实现性能分析折半插入排序代码实现希尔排序基本原理代码实现性能分析选择排序单向选择排序基本原理代码...分析归并排序基本原理代码实现性能分析排序总结各种排序算法之间的比较...
堆排序是一种非常有效的排序算法,基于完全二叉树的特性。它首先将数组转化为一个最大堆,然后将最大的元素移除并放在数组的末尾,重复这个过程直到所有元素都被排序。
本文实例讲述了基于JavaScript实现的插入排序算法。分享给大家供大家参考,具体如下: 根据排序过程中使用的存储器不同,可以将排序方法分为两大类:内部排序和外部排序。 内部排序是指待排序记录存放在计算机随机...
## 数组* 实现一个支持动态扩容的数组* 实现一个大小固定的有序数组,支持动态增删改操作* 实现两个有序数组合并为一个有序数组 ## 链表* 实现单链表、循环链表、双向链表,支持增删操作* 实现单链表反转* 实现两个...
第5章 基于归纳的算法设计 5.1 引言 5.2 多项式求值 5.3 最大导出子图 5.4 寻找一对一映射 5.5 社会名流问题 5.6 分治算法:轮廓问题 5.7 在二叉树中计算平衡因子 5.8 寻找最大连续子序列 5.9 增强归纳假设...