梳排序
此条目需要补充更多来源。 (2018年9月30日) |
梳排序(英语:Comb sort)是一种由弗拉基米尔·多博舍维奇(Wlodzimierz Dobosiewicz)于1980年所发明的不稳定排序算法,并由史蒂芬·莱西(Stephen Lacey)和理查德·博克斯(Richard Box)于1991年四月号的Byte杂志中推广。梳排序是改良自泡沫排序和快速排序,其要旨在于消除“乌龟”,亦即在阵列尾部的小数值,这些数值是造成泡沫排序缓慢的主因。相对地,“兔子”,亦即在阵列前端的大数值,不影响泡沫排序的效能。
梳排序 | |
---|---|
![]() 使用梳排序为一列数字进行排序的过程 | |
概况 | |
类别 | 排序算法 |
资料结构 | 阵列 |
复杂度 | |
平均时间复杂度 |
其中p表示增量 (the number of increments)[1] |
最坏时间复杂度 | [1] |
最优时间复杂度 | |
空间复杂度 | |
相关变量的定义 |
在泡沫排序中,只比较阵列中相邻的二项,即比较的二项的间距(Gap)是1,梳排序提出此间距其实可大于1,改自插入排序的希尔排序同样提出相同观点。梳排序中,开始时的间距设定为阵列长度,并在回圈中以固定比率递减,通常递减率设定为1.3。在一次回圈中,梳排序如同泡沫排序一样把阵列从首到尾扫描一次,比较及交换两项,不同的是两项的间距不固定于1。如果间距递减至1,梳排序假定输入阵列大致排序好,并以泡沫排序作最后检查及修正。
递减率
编辑递减率的设定影响著梳排序的效率,原作者以随机数作实验,得到最有效递减率为1.3的。如果此比率太小,则导致一回圈中有过多的比较,如果比率太大,则未能有效消除阵列中的乌龟。
亦有人提议用 作递减率,同时增加换算表协助于每一回圈开始时计算新间距。
因为程式语言中乘法比除法快,故会取递减率倒数与间距相乘,
变异形式
编辑梳排序-11
编辑设定递减率为1.3时,最后只会有三种不同的间距组合:(9, 6, 4, 3, 2, 1)、(10, 7, 5, 3, 2, 1)、或 (11, 8, 6, 4, 3, 2, 1)。实验证明,如果间距变成9或10时一律改作11,则对效率有明显改善,原因是如果间距曾经是9或10,则到间距变成1时,数值通常不是递增序列,故此要进行几次泡沫排序回圈修正。加入此指定间距的变异形式称为梳排序-11(Combsort11)。
混合梳排序和其他排序算法
编辑如同快速排序和合并排序,梳排序的效率在开始时最佳,接近结束时最差。如果间距变得太小时(例如小于10),改用插入排序或希尔排序等算法,可提升整体效能。
此方法最大好处是不需要检查是否进行过交换程序以将排序回圈提早结束。
虚拟码
编辑梳排序程序(以array作输入) gap = array的长度 //设定开始时的间距
当gap > 1或swaps = 1时执行回圈 //代表未完成排序 gap = 取“gap除以递减率”的整数值 //更新间距
swaps = 0 //用以检查阵列是否已在递增形式,只限gap=1时有效
//把输入阵列“梳”一次 i = 0 到 (array的长度 - 1 - gap)来执行回圈 //从首到尾扫描一次;因为阵列元素的编号从0开始,所以最后一个元素编号为长度-1 如果array[i] > array[i+gap] 把array[i]和array[i+gap]的数值交换 swaps = 1 //曾作交换,故此阵列未必排序好 如果结束 回圈结束 回圈结束 程序结束
实作范例
编辑C语言
编辑void comb_sort(int arr[], int len) {
double shrink_factor = 0.8;
int gap = len, swapped = 1, i;
int temp;
while (gap > 1 || swapped) {
if (gap > 1)
gap *= shrink_factor;
swapped = 0;
for (i = 0; gap + i < len; i++)
if (arr[i] > arr[i + gap]) {
temp = arr[i];
arr[i] = arr[i + gap];
arr[i + gap] = temp;
swapped = 1;
}
}
}
C++
编辑template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能
void comb_sort(T arr[], int len) {
double shrink_factor = 0.8;
int gap = len, swapped = 1, i;
while (gap > 1 || swapped) {
if (gap > 1)
gap = (int) ((double) gap * shrink_factor);
swapped = 0;
for (i = 0; gap + i < len; i++)
if (arr[i] > arr[i + gap]) {
swap(arr[i], arr[i + gap]);
swapped = 1;
}
}
}
Java
编辑public static <E extends Comparable<? super E>> void sort(E[] input) {
int gap = input.length;
boolean swapped = true;
while (gap > 1 || swapped) {
if (gap > 1) {
gap = (int) (gap * 0.8);
}
int i = 0;
swapped = false;
while (i + gap < input.length) {
if (input[i].compareTo(input[i + gap]) > 0) {
E t = input[i];
input[i] = input[i + gap];
input[i + gap] = t;
swapped = true;
}
i++;
}
}
}
JavaScript
编辑Array.prototype.comb_sort = function() {
var shrink_factor = 0.8;
var gap = this.length, swapped = 1, i;
var temp;
while (gap > 1 || swapped) {
if (gap > 1)
gap = Math.floor(gap * shrink_factor);
swapped = 0;
for (i = 0; gap + i < this.length; i++)
if (this[i] > this[i + gap]) {
temp = this[i];
this[i] = this[i + gap];
this[i + gap] = temp;
swapped = 1;
}
}
return this;
};
PHP
编辑function swap(&$x, &$y) {
$t = $x;
$x = $y;
$y = $t;
}
function comb_sort(&$arr) {//php的陣列視為基本型別,所以必須用傳參考才能修改原陣列
$shrink_factor = 0.8;
$gap = count($arr);
$swapped = 1;
while ($gap > 1 || $swapped) {
if ($gap > 1)
$gap = floor($gap * $shrink_factor);
$swapped = 0;
for ($i = 0; $gap + $i < count($arr); $i++)
if ($arr[$i] > $arr[$i + $gap]) {
swap($arr[$i], $arr[$i + $gap]);
$swapped = 1;
}
}
}
Go
编辑func comb_sort(data sort.Interface) {
n := data.Len()
shrinkFactor := 0.8
gap := n
swapped := true
for gap > 1 || swapped {
if gap > 1 {
gap = int(float64(gap) * shrinkFactor)
}
// 冒泡排序
swapped = false
for i := 0; i < n - gap; i++ {
if data.Less(i + gap, i) {
data.Swap(i + gap, i)
swapped = true
}
}
}
}
# Julia Sample : CombSort
function CombSort(A)
gap,swapped = length(A),1
while (gap>1) || (swapped==1)
gap = floor(Int,gap/1.25)
swapped=0
for i=1:(length(A)-gap)
if A[i]>A[i+gap]
A[i],A[i+gap] = A[i+gap],A[i]
swapped=1
end
end
end
return A
end
# Main Code
A = [16,586,1,31,354,43,3]
println(A) # Original Array
println(CombSort(A)) # Comb Sort Array
动作原理
编辑假设输入为
- 8 4 3 7 6 5 2 1
目标为将之变成递增排序。因为输入长度=8,开始时设定间距为8/1.3≒6,则比较8和2、4和1,并作交换两次。
- 8 4 3 7 6 5 2 1
- 2 4 3 7 6 5 8 1
- 2 1 3 7 6 5 8 4
第二次回圈,更新间距为6/1.3≒4。比较2和6、1和5,直至7和4,此回圈中只须交换一次。
- 2 1 3 7 6 5 8 4
- 2 1 3 4 6 5 8 7
接下来的每次回圈,间距依次递减为3 → 2 → 1,
间距=3时,不须交换
- 2 1 3 4 6 5 8 7
间距=2时,不须交换
- 2 1 3 4 6 5 8 7
间距h=1时,交换三次
- 2 1 3 4 6 5 8 7
- 1 2 3 4 6 5 8 7
- 1 2 3 4 5 6 8 7
- 1 2 3 4 5 6 7 8
上例中,共作了六次交换以完成排序。