梳排序
維基百科,自由的 encyclopedia
梳排序(英語:Comb sort)是一種由弗拉基米爾·多博舍維奇(Wlodzimierz Dobosiewicz)於1980年所發明的不穩定排序算法,並由史蒂芬·萊西(Stephen Lacey)和理查德·博克斯(Richard Box)於1991年四月號的Byte雜誌(英语:Byte Magazine)中推廣。梳排序是改良自泡沫排序和快速排序,其要旨在於消除「烏龜」,亦即在陣列尾部的小數值,這些數值是造成泡沫排序緩慢的主因。相對地,「兔子」,亦即在陣列前端的大數值,不影響泡沫排序的效能。
此條目需要补充更多来源。 (2018年9月30日) |
事实速览 梳排序, 概况 ...
梳排序 | |
---|---|
使用梳排序為一列数字进行排序的过程 | |
概况 | |
類別 | 排序算法 |
資料結構 | 陣列 |
复杂度 | |
平均時間複雜度 |
其中p表示增量 (the number of increments)[1] |
最坏时间复杂度 | [1] |
最优时间复杂度 | |
空間複雜度 | |
相关变量的定义 |
关闭
在泡沫排序中,只比較陣列中相鄰的二項,即比較的二項的間距(Gap)是1,梳排序提出此間距其實可大於1,改自插入排序的希爾排序同樣提出相同觀點。梳排序中,開始時的間距設定為陣列長度,並在迴圈中以固定比率遞減,通常遞減率設定為1.3。在一次迴圈中,梳排序如同泡沫排序一樣把陣列從首到尾掃描一次,比較及交換兩項,不同的是兩項的間距不固定於1。如果間距遞減至1,梳排序假定輸入陣列大致排序好,並以泡沫排序作最後檢查及修正。