张拓的博客

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。 概述若以升序排序说明，把数组转换成最大堆（Max-Heap Heap），这是一种满足最大堆性质（Max-Heap Property）的二叉树：对于除了根之外的每个节点i, A[parent(i)] ≥ A[i]。 重复从最大堆取出数值最大的结点（把根结点和最后一个结点交换，把交换后的最后一个结点移出堆），并让残余的堆维持最大堆性质。 堆节点的访问通常堆是通过一维数组来实现的。在数组起始位置为0的情形中： 父节点i的左子节点在位置{\displaystyle (2i+1)}; 父节点i的右子节点在位置{\displaystyle (2i+2)}; 子节点i的父节点在位置{\displaystyle \lfloor (i-1)/2\rfloor }; 堆的操作在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作： 最大堆调整（Max Heapif ...

在计算机科学与数学中，一个排序算法（英语：Sorting algorithm）是一种能将一串资料依照特定排序方式排列的算法。最常用到的排序方式是数值顺序以及字典顺序。有效的排序算法在一些算法（例如搜索算法与合并算法）中是重要的，如此这些算法才能得到正确解答。排序算法也用在处理文字资料以及产生人类可读的输出结果。基本上，排序算法的输出必须遵守下列两个原则： 输出结果为递增序列（递增是针对所需的排序顺序而言） 输出结果是原输入的一种排列、或是重组虽然排序算法是一个简单的问题，但是从计算机科学发展以来，在此问题上已经有大量的研究。举例而言，冒泡排序在1956年就已经被研究。虽然大部分人认为这是一个已经被解决的问题，有用的新算法仍在不断的被发明。（例子：图书馆排序在2004年被发表） 分类在计算机科学所使用的排序算法通常依以下标准分类： 计算的时间复杂度（最差、平均、和最好性能），依据列表（list）的大小({\displaystyle n})。一般而言，好的性能是{\displaystyle O(n\log n)}（大O符号），坏的性能是{\displaystyle O(n^{2})} ...

臭皮匠排序（英语：Stooge Sort）是一种采用分治法的低效排序算法，甚至慢于冒泡排序。在《算法导论》第二版第7章（快速排序）的思考题中被提到，是由Howard、Fine等教授提出的所谓“漂亮的”排序算法。 该算法得名于三个臭皮匠，每个臭皮匠都能暴打其他两个，其他两个也会卯起来扁其中一个。 实现 如果最后一个值小于第一个值，则交换这两个数 如果当前集合元素数量大于等于3： 使用臭皮匠排序法排序前2/3的元素 使用臭皮匠排序法排序后2/3的元素 再次使用臭皮匠排序法排序前2/3的元素123456789algorithm stoogesort(array L, i = 0, j = length(L)-1) if L[j] < L[i] then L[i] ↔ L[j] if (j - i + 1) >= 3 then t = (j - i + 1) / 3 stoogesort(L, i , j-t) stoogesort(L, i+t, j ) stoogesort(L, i , j ...

耐心排序（Patience Sort）是将数组的元素分类成很多堆再串接回数组的一种排序算法。 操作解说 创建一个堆数组 比较目前指向的元素和每个堆的第一个元素，计算出比目前元素小的堆数量 若目前元素比所有堆的第一个元素大，创建新的堆并加入到堆数组中，否则将目前元素加入到第“比目前元素小的堆数量”个堆 分类完后将每个堆反序然后对每个堆再做耐心排序 最后将每个堆串接并存储回原本的数组 演示操作一次耐心排序分堆过程假设目前欲排序的数列为: 3, 5, 7, 1, 4 Step 1: 取出数字 3, 由于目前没有任何堆所以产生一号堆并把 3 放入 堆 一 内容: 3 Step 2: 取出数字 5, 5 比一号堆的第一个数字 3 大, 故产生二号堆并把 5 放入 堆 一 内容: 3 堆 二 内容: 5 Step 3: 取出数字 7, 7 比一号堆和二号堆的第一个数字大, 故产生三号堆并把 7 放入 堆 一 内容: 3 堆 二 内容: 5 堆 三 内容: 7 Step 4: 取出数字 1, 所有堆的第一个数字都比 1 大, 故放入一号堆 堆 一 内容: 3, ...

煎饼排序（英语：Pancake sorting）指的是将大小不同的一摞煎饼按大小排序的数学问题，其中煎饼铲子每次只能从任意位置铲起上方全部煎饼并翻面。“煎饼数”（英语：pancake number）是指给定煎饼的张数时，最坏情况下需要的最少翻面次数。这个问题最早由美国几何学家雅可比·古德曼提出。它属于排序问题的变种。煎饼排序的目标和传统排序算法最小化比较次数不同，因为它每次操作只允许反转序列的前缀，所以需要最小化反转前缀次数。焦煎饼排序是煎饼排序的变种问题，每张煎饼都有一面是烤焦的，最终除了按照大小排序以外还要让所有焦面向下。 煎饼问题最初的煎饼问题对于任意一叠n张煎饼，人们已经证明最小翻转次数在 {\frac {15}{14}} n 到 {\frac {18} {11} }n 之间（约为1.07n到1.64n之间），但精确值仍未知。 最简单的算法在最坏情况下需要2n − 3次翻转。这种算法是选择排序的变体，每轮用一次翻转把未排序的煎饼中最大者翻到顶上，再用一次翻转把它翻到最终所在处（目前未排序煎饼和已排序煎饼的交界处），然后对剩余未排序煎饼重复此过程。剩下两个煎饼时只需一次翻转即完成 ...

珠排序是一种自然排序算法，由Joshua J. Arulanandham、Cristian S. Calude和Michael J. Dinneen于2002年发展而来，并且在欧洲理论计算机协会（简称EATCS）的新闻简报上发表了该算法。无论是电子还是实物上的实现，珠排序都能在O(n)时间内完成；然而，该算法在电子上的实现明显比实物要慢很多，并且只能用于对正整数序列进行排序。并且，即使在最好的情况，该算法也需要O(n^2)的空间。 算法概述在珠排序中，一行（row）表示一个数字。如果一行里有2颗珠子，该行代表数字2；如果一行里有4颗珠子，该行代表数字4。当给定一个数组，数组里有多少个数字，就要有多少行；数组里最大的数字是几，就要准备多少根杆子。 准备就绪后，释放珠子，珠子按重力下落，就完成了排序。 珠排序可以类比于珠子在平行的竖直杆上滑动，就像算盘一样。然而，每一竖直杆都有珠子数目的限制。因此，初始化就相当于在竖直的杆上悬挂珠子，在第一步中，排列就被显示为n=5行的珠子在m=4列队竖直杆上。每一行右边的数字意味着该行在问题中被表示的数；第1，2行表示正整数3（因为它们都有3个珠子）而顶 ...

图书馆排序，或空位插入排序是一种排序算法 ，它基于插入排序，但在每两个元素之间存在空位，以便于加速随后的插入。这个名字来自一个比喻： 假设一名图书管理员在一个长架上按字母顺序来整理书，从左边A开头的书，一直到右边Z开头的书，书本之间没有空格。如果图书管理员有一本开头为B的新书，当他找到了这本书在B区中的正确位置，他将不得不把从该位置后一直到Z的每一本书向右移动，就只是为了腾出空位放置这本新书。这就是插入排序的原理。但是，如果他在每一字母区后留有额外的空间，只要在B区之后还有空间，他插入书时就只需要移动少数几本书，而不会移动后面所有的书，这是图书馆排序的原理。 此算法由 Michael A. Bender、Martín Farach-Colton和Miguel Mosteiro 于2004年提出，并于2006年出版。 图书馆排序像插入排序一样，是稳定的排序算法，并且它是在线排序；然而，它被证明在大部分情况下具有O(n log n)的运行速度（相当于快速排序），而不是插入排序的O(n^2)。用于此改进的机制与跳过列表非常相似。本文没有给出完整的实现，也没有重要部分的确切算法，如插入和重新平 ...

比较排序（英语：Comparison sort）是排序算法的一种，通过一个抽象的内容比较操作（通常是“小于或等于”操作）来确定两个元素中哪个应该放在序列前面。该算法的唯一要求就是操作数满足全序关系： 如果{\displaystyle a\leq b}并且{\displaystyle b\leq c}那么{\displaystyle a\leq c}（传递性）。对于{\displaystyle a}或{\displaystyle b}，要不{\displaystyle a\leq b}，要不{\displaystyle b\leq a}（完全性）。对于{\displaystyle a\leq b}并且{\displaystyle b\leq a}这种情况，{\displaystyle a}和{\displaystyle b}都有可能被排在前面。这时输入的顺序就会决定最后的顺序。 比较排序类似于将未贴标签的砝码用天平将按质量大小进行排序，并且除了用天平测量两个砝码的质量之外不能用其他方法。 算法特例比较排序包括： 快速排序 堆排序 归并排序 插入排序 选择排序 冒泡排序 非比较排序包括 ...

比较计数排序（Comparison Counting Sort）是一种稳定的线性时间排序算法，此种算法时间复杂度虽然是平方时间，但它是拥有较强抗干扰能力和稳固性的排序算法。 比较计数排序的特征此种算法把每个项目与其它项目作比较，计数出每个项目大于(或小于)它的项目个数，此数字及可当作各个项目排序的基准值。此种算法与冒泡排序一样时间复杂度都是平方时间，不受传统计算机科学青睐，但容错率超群。 Python 2.7 实现1234567891011121314151617def compare_counter_sort(l): C = [] for i in l: count = 0 for j in l: if j < i: count += 1 while(count in C): count += 1 C.append(count) return [l[C.index(i)] fo ...

竞争排序是一种排序算法。它优化了传统的选择排序，不是按顺序选择下一个排序的元素，而是选择优先队列。在传统选择排序中，从n个元素中选取下一个要排序的元素花费的时间复杂度为O(n)，而在竞争排序中，在花费O(n)的时间初始化优先队列之后，每次选取一个元素只要O(log n)。 原文地址：https://zh.wikipedia.org/wiki/%E7%AB%9E%E4%BA%89%E6%8E%92%E5%BA%8F 在知识共享 署名-相同方式共享 3.0协议之条款下提供