高效排序算法-梳排序

2019-11-13  本文已影响0人  async丶
梳排序

原理:
梳(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,因为编程语言乘法比除法快。

上一篇 下一篇

猜你喜欢

热点阅读