title: 梳排序
date: 2024-7-30 14:46:27 +0800
categories:
- 排序算法
tags:
- 排序
- 算法
- 梳排序
description: 梳排序（Comb Sort）是一种由弗拉基米尔·多博舍维奇（Wlodzimierz Dobosiewicz）于1980年所发明的不稳固排序算法，并由史蒂芬·莱西（Stephen Lacey）和理查德·博克斯（Richard Box）于1991年四月号的Byte杂志中推广。梳排序是改良自冒泡排序和快速排序，其要旨在于消除“乌龟”，亦即在数组尾部的小数值，这些数值是造成冒泡排序迟钝的主因。相对地，“兔子”，亦即在数组前端的大数值，不影响冒泡排序的性能。
math: true
梳排序
梳排序（Comb Sort）是一种改进的冒泡排序算法。它通过消除“乌龟”（即数组中的小值）和“兔子”（即数组中的大值）来提高排序效率。梳排序的核心思想是先使用较大的间隙（gap）进行比较和交换，然后徐徐减小间隙，终极进行常规的冒泡排序。
梳排序的原理
梳排序的关键在于间隙的选择和徐徐缩小。初始间隙通常设置为数组长度，然后在每次迭代中将间隙除以一个因子（通常为1.3），直到间隙缩小到1，此时进行末了的冒泡排序。
图示
梳排序的步骤
- 设置初始间隙：初始间隙为数组长度。
- 调解间隙：在每次迭代中，将间隙除以因子（通常为1.3）。
- 比较和交换：在当前间隙下比较并交换元素。
- 重复步骤2和3：直到间隙缩小到1，进行末了的冒泡排序。
梳排序示例
假设待数组[10 4 3 9 6 5 2 1 7 8]
第一次循环
待排数组长度为10,而10÷1.3=8,则比较10和7,4和8,并做交换
交换后的结果为[7 4 3 9 6 5 2 1 10 8]
第二次循环
更新间距为8÷1.3=6,比较7和2,4和1,3和10,9和8,7和2,4和1,9和8，需要交换
交换后的结果为[2 1 3 8 6 5 7 4 10 9]
第三次循环
更新间隔为4,比较2和6,1和5,3和7,8和4,6和10,5和9,8和4，需要交换
[2 1 3 4 6 5 7 8 10 9]
第四次循环
更新间隔为3,比较2和4,1和6,3和5,4和7,6和8,5和10,7和9，不需要交换
第五次循环
更新间隔为2,比较2和3,1和4,3和6,4和5,6和7,5和8,7和10,8和9，不需要交换
第六次循环
更新间隔为1，为冒泡排序。
[1 2 3 4 5 6 7 8 9 10]
交换后排序竣事,顺序输出即可得到[1 2 3 4 5 6 7 8 9 10]
复杂度分析
递减率的设置影响着梳排序的效率，原作者以随机数作实验，得到最有效递减率为1.3的。假如此比率太小，则导致一循环中有过多的比较，假如比率太大，则未能有效消除数组中的乌龟。
亦有人提议用 1 / ( 1 − 1 e φ ) ≈ 1.247330950103979 1/\left(1-{\frac {1}{e^{\varphi }}}\right)\approx 1.247330950103979 1/(1−eφ1)≈1.247330950103979作递减率，同时增长换算表协助于每一循环开始时盘算新间距。
因为编程语言中乘法比除法快，故会取递减率倒数与间距相乘， 1 1.247330950103979 = 0.801711847137793 ≈ 0.8 \frac{1}{1.247330950103979}=0.801711847137793\approx 0.8 1.2473309501039791=0.801711847137793≈0.8
时间复杂度
- 最佳情况： O ( n log n ) O(n\log n) O(nlogn)。
- 最坏情况： Ω ( n 2 ) \Omega(n^2) Ω(n2)。
- 均匀情况： Ω ( n 2 2 p ) \Omega (\frac{n^2}{2^p}) Ω(2pn2)。
空间复杂度
- 空间复杂度： O ( 1 ) O(1) O(1)。
Java代码实现
- import java.util.Arrays;
- public class CombSort {
- public static void combSort(int[] arr) {
- int n = arr.length;
- int gap = n;
- boolean swapped = true;
- while (gap != 1 || swapped) {
- // 调整间隙
- gap = getNextGap(gap);
- swapped = false;
- // 比较和交换
- for (int i = 0; i < n - gap; i++) {
- if (arr[i] > arr[i + 1]) {
- int temp = arr[i];
- arr[i] = arr[i + gap];
- arr[i + gap] = temp;
- swapped = true;
- }
- }
- }
- }
- // 计算下一个间隙
- private static int getNextGap(int gap) {
- gap = (gap * 10) / 13;
- if (gap < 1) {
- return 1;
- }
- return gap;
- }
- public static void main(String[] args) {
- int[] arr = {6, 4, 3, 7, 1, 9, 8, 2, 5};
- System.out.println("Given Array:");
- System.out.println(Arrays.toString(arr));
- // 调用梳排序函数
- combSort(arr);
- System.out.println("Sorted Array:");
- System.out.println(Arrays.toString(arr));
- }
- }
梳排序-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)，改用插入排序或希尔排序等算法，可提拔整体性能。
此方法最大利益是不需要查抄是否进行过交换程序以将排序循环提早竣事。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
