张拓的博客

词语定序，或称定序（英语：Collation，目前没有公认的译名，但不少资讯领域者，如微软，根据其内涵而译作“定序”，或有译作“文字排序”），是指在计算机科学与图书馆学、词典编撰中书写信息的标准排序。如数值序或者字母序 。形式上说，定序方法对所有可能的标识符（即排序键）集合定义了一个全序，因此在信息项的集合上产生了一个全预序（因为具有相同的排序键的信息项没有预定次序）。 定序算法，如统一码定序算法，则定义如何比较两个字符串确定何者在先。 数值序或者编年序表示数值（或时间）的字符串按照其表示的数值，例如： “-4”, “2.5”, “10”, “89”, “30,000”. 注意可能会存在偏序情况，如”2”与”2.0”，”2e3”与”2000”。 字母序主条目：字母序字母序，也称词典序。常见问题有： 空白符（如空格符）如何处理； 附加符号。法语中把带附加符号的字符都当作基本字符来排序。德语的“电话簿序”中，Ä, Ö, Ü应当作为 “ae”, “oe”, “ue” 来排序。因此，姓Müller/Mueller具有相同的排序位置。西班牙语的Ñ作为一个单独字母排在N之后. 姓名排序时，不论书 ...

基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在列表机（Tabulation Machine）上的贡献[1]。 它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。 基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。 效率基数排序的时间复杂度是{\displaystyle O(k\cdot n)}，其中{\displaystyle n}是排序元素个数，{\displaystyle k}是数字位数。注意这不是说这个时间复杂度一定优于{\displaystyle O\l ...

外排序（External sorting）是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器（通常是硬盘）上。外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。而后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。 外归并排序外排序的一个例子是外归并排序（External merge sort），它读入一些能放在内存内的数据量，在内存中排序后输出为一个顺串（即是内部数据有序的临时文件），处理完所有的数据后再进行归并。比如，要对900 MB的数据进行排序，但机器上只有100 MB的可用内存时，外归并排序按如下方法操作： 1.读入100 MB的数据至内存中，用某种常规方式（如快速排序、堆排序、归并排序等方法）在内存中完成排序。 2.将排序完成的数据写入磁盘。 3.读入每个临时文件（顺串）的前10 MB（ = 100 MB / (9块 + 1)）的数据放入内存中的输入缓冲区，最后的10 MB作为输出缓冲区。（实践中， ...

奇偶排序，或奇偶换位排序，或砖排序，是一种相对简单的排序算法，最初发明用于有本地互连的并行计算。这是与冒泡排序特点类似的一种比较排序。 该算法中，通过比较数组中相邻的（奇-偶）位置数字对，如果该奇偶对是错误的顺序（第一个大于第二个），则交换。下一步重复该操作，但针对所有的（偶-奇）位置数字对。如此交替进行下去。 处理器数组的排序在并行计算排序中，每个处理器对应处理一个值，并仅有与左右邻居的本地互连。所有处理器可同时与邻居进行比较、交换操作，交替以奇-偶、偶-奇的顺序。该算法由Habermann在1972年最初发表并展现了在并行处理上的效率。 该算法可以有效地延伸到每个处理器拥有多个值的情况。在Baudet–Stevenson奇偶合并分割算法中，每个处理器在每一步对自己所拥有的子数组进行排序，然后与邻居执行合并分割或换位合并 Batcher奇偶归并排序Batcher奇偶归并排序是一种相关但更有效率的排序算法，采用比较-交换和完美-洗牌操作。 Batcher的方法在拥有广泛互连的并行计算处理器上效率不错。 程序代码C语言12345678910111213141516void odd_eve ...

希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位 历史希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。一些老版本教科书和参考手册把该算法命名为Shell-Metzner，即包含Marlene Metzner Norton的名字，但是根据Metzner本人的说法，“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。” 算法实现原始的算法实现在最坏的情况下需要进行O(n2)的比较和交换。 V. Pratt的书[1]对算法进行了少量修改，可以使得性能提升至O(n log2 n)。这比最好的比较算法的O(n log n)要差一些。 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最 ...

并行排序算法是计算机并行计算能力大大发展之后，为了提高排序效率而提出的算法。 划分的设计方法 PSRS算法 Viliant归并算法 对数划分 串行算法直接并行化 模拟快速排序 二叉树上模拟快速排序 串行算法简介：快速排序是一种较为高效的排序算法，它通过不断的划分待排序列为两段，使得前一段总小于或等于某个数，而后一段总大于某个数，这样每次划分就能确定一个数的最终位置。一般情况下，如果每次划分的两个子列大致等长，那么它的时间复杂度是{\displaystyle O\left(n\log n\right)}。 在PRAM-CRCW计算模型上利用二叉树网络模拟快速排序 由快速排序的过程，我们可以看到，快速排序实际上就是在构造一棵二叉树，让划分主元位于根节点，使得左子节点小于或等于根而右子节点大于根，最后对整棵二叉树进行一次中序遍历，便可以得到最后排好序的数列。 我们可以选n个处理器分别保存待排序数组A的n个元素，处理器{\displaystyle P_{i}}对应一个变量{\displaystyle X_{i}}用于存放主元元素的处理器号，以及两个变量L,R分别存放其左右儿子。开始时，每一个 ...

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为{\displaystyle O(n\log n)}（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。 概述采用分治法: 分割：递归地把当前序列平均分割成两半。 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。 归并操作归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。 递归法（Top-down） 1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 4.重复步骤3直到某一指针到达序列尾 5.将另一序列剩下的所有元素直接复制到合并序列尾 迭代法（Bottom-up）原理如下（假设序列共有{\displaystyle n}个元素 ...

慢速排序是一种排序算法。其基于合并排序的分而治之及递回的思想，并故意设计使排序过程非常缓慢。慢速排序由Andrei Broder及Jorge Stolfi在1986年发表的论文Pessimal Algorithms and Simplexity Analysis[1]（论文名称是渐进最优算法及计算复杂性理论的戏仿）中提出。 算法慢速排序是一种原地算法的递回算法。 在简单的虚拟码中，此算法可以被表示为：123456789procedure slowsort(A, i, j) // 排序一個整數或浮點數數列 A[i],...,A[j] ，若要使用其他的資料類型則必須重載大於或小於運算符 if i ≥ j then return m := ⌊(i+j) / 2⌋ slowsort(A, i, m) // (1.1) slowsort(A, m+1, j) ...

在计算机科学领域，有向图的拓扑排序或拓扑测序是对其顶点的一种线性排序，使得对于从顶点{\displaystyle u} 到顶点{\displaystyle v}的每个有向边{\displaystyle uv}，{\displaystyle u} 在排序中都在{\displaystyle v}之前。 例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。 当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。 任何有向无环图至少有一个拓扑排序。已知有算法可以在线性时间内，构建任何有向无环图的拓扑排序。 在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，才能称为该图的一个拓扑排序（英语：Topological sorting）： 1.序列中包含每个顶点，且每个顶点只出现一次； 2.若A在序列中排在B的前面，则在图中不存在从B到A的路径。 算法卡恩算法卡恩于1962年提出了该算法。简单来说，假设L是存放结果的列表，先找到那些入度为零的节点，把这些节点放到L中，因为这些节点没有任 ...

插值排序（interpolation sort）或称为直方图排序（histogram sort）。 是一种使用插值公式分散资料分而治之的排序算法。插值排序也是桶排序算法的一种变型。 插值排序递归算法插值排序也是一种桶排序，排序算法与桶排序相同，插值公式是把被排序的数字化为介于零到壹的数值，再乘以桶子的数量，得出被排序数字对应的桶子号码，以此号码分桶来实现桶排序。一个通用的插值公式是： 插值 = 取整数(((设算数 -­ 最小数) / (最大数 -­ 最小数)) * (桶子数量 - 1)) 插值排序递归算法流程 1.寻访序列，找出最大值与最小值，如果相等排序完成。 2.设置一个定量的阵列当作空桶子。 3.寻访序列，把项目一个一个放到插值对应的桶子去。 4.对每个不是空的桶子再次进行桶排序。 5.从不是空的桶子里把项目再放回原来的序列中。 插值排序递归算法实作JavaScript code: 123456789101112131415161718192021222324Array.prototype.bucketSort = function(){//--edit date: ...