计算机科学

首页 > 计算机科学

梳排序

2018-08-28 09:41:09     所属分类:排序算法
梳排序
Comb sort demo.gif
使用梳排序为一列数字进行排序的过程
分类 排序算法
数据结构 数组
最坏时间复杂度 [1]
最优时间复杂度
平均时间复杂度

其中p表示增量

(the number of increments)[1]
最坏空间复杂度

梳排序(Comb sort)是一种由Wlodzimierz Dobosiewicz于1980年所发明的不稳定排序算法,并由Stephen Lacey和Richard Box于1991年四月号的Byte杂志中推广。梳排序是改良自泡沫排序和快速排序,其要旨在于消除乌龟,亦即在数组尾部的小数值,这些数值是造成泡沫排序缓慢的主因。相对地,兔子,亦即在数组前端的大数值,不影响泡沫排序的性能。

在泡沫排序中,只比较数组中相邻的二项,即比较的二项的间距(Gap)是1,梳排序提出此间距其实可大于1,改自插入排序的希尔排序同样提出相同观点。梳排序中,开始时的间距设置为数组长度,并在循环中以固定比率递减,通常递减率设置为1.3。在一次循环中,梳排序如同泡沫排序一样把数组从首到尾扫描一次,比较及交换两项,不同的是两项的间距不固定于1。如果间距递减至1,梳排序假定输入数组大致排序好,并以泡沫排序作最后检查及修正。

目录

  • 1 递减率
  • 2 变异形式
    • 2.1 梳排序-11
    • 2.2 混合梳排序和其他排序算法
  • 3 伪代码
  • 4 实现示例
    • 4.1 C语言
    • 4.2 C++
    • 4.3 Java
    • 4.4 JavaScript
    • 4.5 PHP
  • 5 动作原理
  • 6 参考文献
  • 7 参看
  • 8 外部链接

递减率

递减率的设置影响着梳排序的效率,原作者以随机数作实验,得到最有效递减率为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 如果arrayi > arrayi+gap 把arrayi和arrayi+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 (arri > arri + gap) {
				temp = arri;
				arri = arri + gap;
				arri + 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 (arri > arri + gap) {
				swap(arri, arri + 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 (inputi.compareTo(inputi + gap) > 0) {
                E t = inputi;
                inputi = inputi + gap;
                inputi + 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 (thisi > thisi + gap) {
				temp = thisi;
				thisi = thisi + gap;
				thisi + 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;
			}
	}
}

动作原理

假设输入为

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

上例中,共作了六次交换以完成排序。

参考文献

  1. ^ 1.0 1.1 Brejová, Bronislava. "Analyzing variants of Shellsort"

参看

  • 泡沫排序,梳排序的基本,较慢的算法。
  • 鸡尾酒排序,或双向泡沫排序,一样解决了泡沫排序中的乌龟问题。

外部链接

Wikibooks-logo.svg
您可以在中查找此百科条目的相关电子教程:
Sorting/Comb sort
  • .NET Implementation of comb sort and several other algorithms
  • Combsort - Who ever knew that bubblesort could be so good?

上一篇:堆排序
下一篇:鎺掑簭绠楁硶
相关推荐