多級排序

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。多級排序是指按照一個屬性或關鍵字進行排序後，查詢結果仍然較多或查詢結果不符合預期，指定多個屬性或關鍵字進行排序。多級排序中關鍵字權重是一個重要因素。

基本介紹

• 中文名：多級排序
• 外文名：Multi-level sorting
• 學科：計算機
• 定義：多個屬性或關鍵字進行排序
• 有關術語：排序
• 套用：資料庫查詢、檢索

簡介

排序(Sorting) 是電腦程式設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。

在資料庫查詢中，按照一列進行排序後，如果查詢到的記錄比較多，那么查詢結果可能仍然不易於閱讀，這時可以使用多級排序。在SQL中可以指定多列進行排序：初級排序對查詢結果進行分類並排序，第二級對初級排序好的類中的數據在相同的數據中進行再次排序。多級排序主要是因為是一次排序的結果不理想，因此多級排序主要功能是對排序結果進行最佳化和改善。

排序算法

穩定的排序

冒泡排序（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.資源逐級查找。一個結點將首先在本地查找所需資源，當沒有找到時，則查找本 地資源路由表，從表的第一行開始，把查詢訊息傳送到屬於同一類型的資源地址，跳過其中的空項或不可到達地址，再從新找到的資源路由表中的下一行重複上述查找，逐步確定資源，至找到所需資源。當找到唯一的資源時則返回之，有多個選項則取最近的結點，當所需 資源不存在時，則取與所需資源類型最接近的資源。