高效排序算法-梳排序

梳排序

原理：
梳(comb)排序基于冒泡排序。每个梳都有自己的gap（间隙）,或大或小。

目前我们已知的冒泡排序是相邻两个元素进行比较，也就是说他们的gap为1。然而梳排序提出了不同的观点，它将gap设置为一定的大小。

梳排序有这样一个1.3的比率值，每趟比较完后，都会用这个1.3去递减gap，直到gap=1时变成冒泡排序，这种算法比冒泡排序的效率要高效的多，时间复杂度为O(N2/2p) 这里的p为增量。

public static int[] combSort(int[] a) {
    int N = a.length;
    int step = N;
    int k;
    //将数组长度/1.3得到本次的gap;   当step=1时，相当于最后进行了一次冒泡排序
    while((step /= 1.3) >= 1) {
        for (int i = N-1; i >= step; i--) {
            k = i -step;
            //如果前者大于后者，则进行交换
            if(a[k]>a[i]){
                // 交换位置
                exc(a, k, i);
            }
        }
    }
    return a;
}

在梳排序中，原作者用随机数做实验，得到了最有效的递减效率是1.3。也就是step/=1.3,同样也可以写成step *= 0.8,因为编程语言乘法比除法快。