梳排序

痛定思痛。 2022-05-25 14:07 174阅读 0赞

##  ##

## 梳排序 ##

梳排序和希尔排序很类似。希尔排序是在直接插入排序的基础上做的优化，而梳排序是在冒泡排序的基础上做的优化，也就是将相距某个增量 d 的记录组成一个子序列，通过冒泡排序使得这个子序列基本有序，然后减少增量继续排序。

梳排序的时间复杂度是 O(nlogn)。

因为梳排序和希尔排序有点相似，所以不多说，直接上代码：

public class SortTest {
    
        public static void main(String[] args) {
            int[] arr = {14, 12, 4, 6, 9, 16, 11, 8, 3, 1};
            CombSort(arr);
            for (int x : arr){
                System.out.print(x+", ");
            }
        }
        /*
           梳排序，梳子排序(从小到大)
         */
        private static void CombSort(int[] arr){
    
            double shrink = 0.801711847137793d; //0.801711847137793 = 1 / 1.247330950103979
            int gap = (int) (shrink * arr.length) ;
            boolean sorted = false ;
            while (gap > 1 || !sorted){
                if (gap > 1){
                    gap = (int)(shrink * gap) ;
                }
                sorted = true ;
                for (int i =0 ; i + gap < arr.length ; i += gap){
                    if(arr[i] > arr[i+gap]){
                        swap(arr, i, i+gap);
                        sorted = false ;
                    }
                }
            }
        }
    
    
    
        /*
            交换角标为x,y在数组的位置
         */
        private static void swap(int[] arr, int x, int y){
            int temp;
            temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;
        }
    }

运行结果为：

1, 3, 4, 6, 8, 9, 11, 12, 14, 16,