[發(fā)明專利]一種基于大數(shù)據(jù)快速排序算法和分布式排序處理系統(tǒng)

在審

• 申請?zhí)枺?/td>: 201710077531.4
• 申請日: 2017-02-14
• 公開（公告）號: CN108427680A
• 公開（公告）日: 2018-08-21
• 發(fā)明（設(shè)計）人: 張向利
• 申請（專利權(quán)）人: 張向利
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.分布式排序處理系統(tǒng)具有獨(dú)特的任務(wù)處理機(jī)制、任務(wù)分配方法和“計算節(jié)點(diǎn)”負(fù)載均衡規(guī)則，最大限度地減輕了網(wǎng)絡(luò)傳輸壓力，具體步驟分為：

步驟A：“主管理節(jié)點(diǎn)”向所有“計算節(jié)點(diǎn)”發(fā)出分割本地待排序數(shù)據(jù)的指令；

步驟B：“計算節(jié)點(diǎn)”按“數(shù)據(jù)元素”首字符分割排序數(shù)據(jù)；

步驟C：“計算節(jié)點(diǎn)”實(shí)時向“主管理節(jié)點(diǎn)”發(fā)送首字符唯一化列表及相應(yīng)排序數(shù)據(jù)量的增量信息；

步驟D：“主管理節(jié)點(diǎn)”接收各節(jié)點(diǎn)首字符唯一化列表及相應(yīng)排序數(shù)據(jù)量增量信息，并且進(jìn)行匯總，計算“節(jié)點(diǎn)負(fù)載均衡閥值”，生成“計算節(jié)點(diǎn)”任務(wù)分配表，向所有“計算節(jié)點(diǎn)”發(fā)送數(shù)據(jù)傳輸指令；

步驟E：各“計算節(jié)點(diǎn)”接收“主管理節(jié)點(diǎn)”發(fā)出的數(shù)據(jù)傳輸指令后，根據(jù)“計算節(jié)點(diǎn)”任務(wù)分配表向指定節(jié)點(diǎn)傳輸相應(yīng)的數(shù)據(jù)；

步驟F：“計算節(jié)點(diǎn)”對本節(jié)點(diǎn)需要處理的數(shù)據(jù)進(jìn)行完整性檢查；

步驟G：“計算節(jié)點(diǎn)”分割排序數(shù)據(jù)完成后，向“主管理節(jié)點(diǎn)”發(fā)送完成分割數(shù)據(jù)報告，并進(jìn)入排序處理階段；

步驟H：“主管理節(jié)點(diǎn)”等待所有“計算節(jié)點(diǎn)”完成分割數(shù)據(jù)任務(wù)后，重新匯總分割字符列表，進(jìn)行快速排序，生成“排序文件順序碼”，發(fā)送給所有“計算節(jié)點(diǎn)”；

步驟I：“計算節(jié)點(diǎn)”針對任務(wù)分配表中本節(jié)點(diǎn)負(fù)責(zé)的每個分割后數(shù)據(jù)塊進(jìn)行排序處理，排序處理完成后，以“sort”加上“排序文件順序碼”的文件命名方式，把完成排序的數(shù)據(jù)塊保存到磁盤上，并向“主管理節(jié)點(diǎn)”發(fā)送數(shù)據(jù)塊排序處理完成報告；

步驟J：“主管理節(jié)點(diǎn)”按照“排序文件順序碼”順序讀取保存在相應(yīng)節(jié)點(diǎn)上排序數(shù)據(jù)結(jié)果文件，完成全部數(shù)據(jù)的排序處理任務(wù)。

2.一種快速排序算法，其特征在于：采用迭代列處理方法進(jìn)行快速排序，與獨(dú)特的復(fù)合型數(shù)據(jù)結(jié)構(gòu)相結(jié)合，極大地提高了排序處理效率，具體步驟分為：

步驟A：定義復(fù)合數(shù)據(jù)結(jié)構(gòu)類型“MyStruct”；

步驟B：將排序數(shù)據(jù)轉(zhuǎn)換成以整數(shù)類型“排序順序碼SortID”(初始值為“0”)為關(guān)鍵字，以復(fù)合數(shù)據(jù)類型“MyStruct”為鍵值的“散列表HashSource”；

步驟C：執(zhí)行迭代列排序模式的排序算法；

步驟D：“散列表HashSource”鍵值——復(fù)合數(shù)據(jù)類型“MyStruct”中Hash散列表鍵值——字符串單鏈表呈現(xiàn)單一值，向“散列表HashSource”插入以“排序順序碼SortID”累加一為值，以Hash散列表鍵值——字符串單鏈表為鍵值的新數(shù)據(jù)項；

步驟E：“散列表HashSource”鍵值——復(fù)合數(shù)據(jù)類型“MyStruct”中Hash散列表鍵值——字符串單鏈表有字符串列數(shù)不足情況，向“散列表HashSource”插入以“排序順序碼SortID”累加一為值，以此字符串單鏈表為鍵值的新數(shù)據(jù)項；

步驟F：“散列表HashSource”鍵值——復(fù)合數(shù)據(jù)類型“MyStruct”中Hash散列表鍵值——字符串單鏈表全部呈現(xiàn)單一值，迭代列排序模式排序算法完成。