梳排序
 | 此条目需要补充更多来源。 (2018年9月30日) |
| 梳排序 | |
|---|---|
 使用梳排序为一列数字进行排序的过程 | |
| 概况 | |
| 类别 | 排序算法 |
| 数据结构 | 数组 |
| 复杂度 | |
| 平均时间复杂度 |
其中p表示增量 (the number of increments)[1] |
| 最坏时间复杂度 | [1] |
| 最优时间复杂度 | |
| 空间复杂度 | |
| 相关变量的定义 | |
梳排序（英语：Comb sort）是一种由弗拉基米尔·多博舍维奇（Wlodzimierz Dobosiewicz）于1980年所发明的不稳定排序算法，并由史蒂芬·莱西（Stephen Lacey）和理查德·博克斯（Richard Box）于1991年四月号的Byte杂志中推广。梳排序是改良自冒泡排序和快速排序，其要旨在于消除“乌龟”，亦即在数组尾部的小数值，这些数值是造成冒泡排序缓慢的主因。相对地，“兔子”，亦即在数组前端的大数值，不影响冒泡排序的性能。
在冒泡排序中，只比较数组中相邻的二项，即比较的二项的间距（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
上例中，共作了六次交换以完成排序。
参考文献
参看
外部链接
