排序高级之交换排序_梳排序-阿里云开发者社区

排序高级之交换排序_梳排序

2016-05-19 1484

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

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

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

递减率

递减率的设定影响着梳排序的效率，原作者以随机数作实验，得到最有效递减率为1.3的。如果此比率太小，则导致一循环中有过多的比较，如果比率太大，则未能有效消除阵列中的乌龟。

亦有人提议用 $1/\left(1-\frac{1}{e^\varphi}\right) \approx 1.247330950103979$ 作递减率，同时增加换算表协助于每一循环开始时计算新间距。

变异形式

梳排序-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)，改用诸如插入排序或鸡尾酒排序等算法，则可提升整体效能。

此方法的最大好处是不再需要检查有否进行过交换程序以将排序循环提早结束。

最差空间复杂度
最差时间复杂度	$\Omega(n^2)$ ^[1]
最优时间复杂度	$O(n)$
平均时间复杂度	$\Omega(n^2/2^p)$ 其中 $p$ 表示增量 (the number of increments)^[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

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

实现代码：

 
   [html] 
   view plain
   copy

    print
   ? 
  
package com.baobaotao.test;  
/**  
 * 排序研究  
 * @author benjamin(吴海旭)  
 * @email benjaminwhx@sina.com / 449261417@qq.com  
 *  
 */  
public class Sort {  
      
    /**  
     **梳排序  
     * @param array  
     */  
    public static void combSort(int[] array) {  
        int gap = array.length ;  
        boolean swapped = true ;  
        while(gap > 1 || swapped) {  
            if(gap > 1) {  
                gap = (int)(gap/1.3) ;  
            }  
            int i = 0;  
            swapped = false ;  
            while(i + gap < array.length) {  
                if(array[i] > array[i+gap]) {  
                    swap(array, i, i+gap) ;  
                    printArr(array) ;  
                    swapped = true ;  
                }  
                i++ ;  
            }  
        }  
    }  
    /**  
     * 按从小到大的顺序交换数组  
     * @param a 传入的数组  
     * @param b 传入的要交换的数b  
     * @param c 传入的要交换的数c  
     */  
    public static void swap(int[] a, int b, int c) {  
        if(b == c) return ;  
        int temp = a[b] ;  
        a[b] = a[c] ;  
        a[c] = temp ;   
    }  
      
    /**  
     * 打印数组  
     * @param array  
     */  
    public static void printArr(int[] array) {  
        for(int c : array) {  
            System.out.print(c + " ");  
        }  
        System.out.println();  
    }  
      
    public static void main(String[] args) {  
        int[] number={11,95,45,15,78,84,51,24,12} ;  
        combSort(number) ;  
    }  
}  

输出分析：

 
   [html] 
   view plain
   copy

    print
   ? 
  
11 24 45 15 78 84 51 95 12 <span style="white-space:pre"> </span>可以看出11和51比较没变、95和24比较  
11 24 12 15 78 84 51 95 45 <span style="white-space:pre"> </span>45和12比较  
11 24 12 15 45 84 51 95 78   
11 24 12 15 45 78 51 95 84   
11 15 12 24 45 78 51 95 84   
11 12 15 24 45 78 51 95 84   
11 12 15 24 45 51 78 95 84   
11 12 15 24 45 51 78 84 95   

转载请标注：http://blog.csdn.net/benjamin_whx/article/details/42461761

排序高级之交换排序_梳排序

递减率

变异形式

梳排序-11

混合梳排序和其他排序算法

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

排序高级之交换排序_梳排序

递减率

变异形式

梳排序-11

混合梳排序和其他排序算法

热门文章

最新文章

相关电子书