[科普中国]-多级排序

简介

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。

在数据库查询中，按照一列进行排序后，如果查询到的记录比较多，那么查询结果可能仍然不易于阅读，这时可以使用多级排序。在SQL中可以指定多列进行排序：初级排序对查询结果进行分类并排序，第二级对初级排序好的类中的数据在相同的数据中进行再次排序1。多级排序主要是因为是一次排序的结果不理想，因此多级排序主要功能是对排序结果进行优化和改善。

排序算法稳定的排序冒泡排序（bubble sort）— O(n2)

插入排序（insertion sort）—O(n2)

鸡尾酒排序（cocktail sort）—O(n2)

桶排序（bucket sort）—O(n)；需要O(k)额外空间

计数排序（counting sort）—O(n+k)；需要O(n+k)额外空间

归并排序（merge sort）—O(n log n)；需要O(n)额外空间

原地归并排序— O(n log2 n)如果使用最佳的现在版本

二叉排序树排序（binary tree sort）— O(n log n)期望时间；O(n2)最坏时间；需要O(n)额外空间

鸽巢排序（pigeonhole sort）—O(n+k)；需要O(k)额外空间

基数排序（radix sort）—O(n·k)；需要O(n)额外空间

侏儒排序（gnome sort）— O(n2)

图书馆排序（library sort）— O(n log n)期望时间；O(n2)最坏时间；需要(1+ε)n额外空间

块排序（block sort）— O(n log n)

不稳定的排序选择排序（selection sort）—O(n2)

希尔排序（shell sort）—O(n log2 n)如果使用最佳的现在版本

Clover排序算法（Clover sort）—O(n)期望时间，O(n2)最坏情况

梳排序— O(n log n)

堆排序（heap sort）—O(n log n)

平滑排序（smooth sort）— O(n log n)

快速排序（quick sort）—O(n log n)期望时间，O(n2)最坏情况；对于大的、随机数列表一般相信是最快的已知排序

内省排序（introsort）—O(n log n)

耐心排序（patience sort）—O(n log n + k)最坏情况时间，需要额外的O(n + k)空间，也需要找到最长的递增子序列（longest increasing subsequence）

不实用的排序Bogo排序— O(n × n!)，最坏的情况下期望时间为无穷。

Stupid排序—O(n3);递归版本需要O(n2)额外内存

珠排序（bead sort）— O(n) or O(√n),但需要特别的硬件

煎饼排序—O(n),但需要特别的硬件

可扩充的多级排序资源快速发现技术背景技术资源发现是资源管理的重要组成部分，是实现网络资源按需调度的重要保障，是P2P应用和网格技术所面临的最核心问题之一，资源发现方法的优劣严重影响着系统的性能。

资源的定位一般采用的是“地址查询”的方法。按照实现系统的体系结构，主要可 以分为三类基本形式：集中目录式、非结构化系统中的泛洪请求式（Flooding)以及结构化 系统中的分布式哈希表（DHT)，也有一些属于这三类基本形式的混合实现。其中，集中目录 式系统通常需要一台或者若干台服务器，该服务器上存储了系统中各资源或文件的目录信 息，当有结点需要某种资源时，可直接通过该目录进行资源的发行与查找。

泛洪请求式适用于非结构化系统，依赖相邻结点之间的消息广播来查找所需 的资源。资源请求结点向邻居结点广播查询消息，收到消息的结点如果没有所要的资 源则继续广播，最后将查询结果原路返回。其中的消息传递策略有：随机（random)、 基于经验的（learning-based)、最好邻居（best-neihbor)、基于经验的+最好邻 居（learning-based+best-neighbor)。基于泛洪的P2P系统搜索效率低，且由于泛 洪占用大量网络带宽，会有可伸缩性方面的问题，改进的策略是为查询消息合理设置 TTL(Time-To-Live)以节省带宽。

在结构化系统中，通过哈希函数，把结点和文件映射到同一个关键字空间，构建 DHT(分布式哈希表）实现资源的分布式索引服务，试图实现资源按标识或键值（key)的有 效存取，如Chord、CAN等。DHT系统需要在结点间维护逻辑上具有某种特定结构的拓扑空 间，利用结点间结构化的拓扑关系，实现结点间高效的查找与路由。

上述方法中，第一类方法资源发现速度快、效率高，但扩充性受制于特点结点；后 两类方法资源发现速度和效率虽有不如，但扩充性好。本发明中提出一种兼顾性能和扩充 性的多级排序资源发现方法。

发明内容基于资源的分类，把系统中的资源用抽象的树状结构进行描述，并把该结构以资 源路由表的形式存储于系统中的各结点。由资源的类别归属形成树中的父子关系，同类资 源则以兄弟节点的形式出现。资源发现由根节点向叶节点方向进行。

1.资源多级分类。定义相应的资源分类标准，可按功能、性能、内容等从属关系把资源按层级进行组织，内部节点是由分类引出的逻辑结点，叶节点表示具体资源。为控制树的高度，可在每个节点下设置多个子节点，并扩大各节点属性的覆盖范围；

2.资源前缀编码。对树中的每个内部节点赋予一个编号，资源类型和编号组成资 源编码查找表，该表可采用集中处理方式周期更新，以保证新类型资源出现后能准确分类和编号，则每个资源可由其前缀码确定其资源类型；

3.构建多级排序的资源路由表。系统中的每个结点为其资源维护对应资源树的资 源路由表，资源表的行列数对应了资源各级分类中的最大类别数和树的高度-1，其具体内容为树中自根节点以下当前资源有相同前缀但属不同资源子类的资源地址，为控制结点中各资源路由表的规模以提高查找效率，资源多级分类时应控制分类的个数；

4.创建初始结点。按照需要创建若干个结点保存构建的资源路由表，并对外提供 资源类型查询服务，一个结点中维护的资源信息；

5.资源逐级查找。一个结点将首先在本地查找所需资源，当没有找到时，则查找本 地资源路由表，从表的第一行开始，把查询消息发送到属于同一类型的资源地址，跳过其中的空项或不可到达地址，再从新找到的资源路由表中的下一行重复上述查找，逐步确定资源，至找到所需资源。当找到唯一的资源时则返回之，有多个选项则取最近的结点，当所需 资源不存在时，则取与所需资源类型最接近的资源。2