排序算法 - 梳排序

基本思想

梳排序和希尔排序很类似。希尔排序是在直接插入排序的基础上做的优化，而梳排序是在冒泡排序的基础上做的优化。也是像希尔排序一样，将待排序序列通过增量分为若干个子序列，然后对子序列进行一趟冒泡排序，一步步减小增量，直至增量为1。所以梳排序的最后一次排序是冒泡排序。
梳排序增量是根据递减率减小的，递减率的设定影响着梳排序的效率，原作者以随机数作实验，得到最有效递减率为1.3的。因为编程中乘法比除法快，所以会取递减率的倒数与间距相乘，即0.8。其实当间距为1的时候，梳排序就是冒泡排序，而间距大于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]。

代码

package main.java.com.study.sortingAalgorithm;

import main.java.com.study.utils.CommonUtils;

/**
 * @author: whb
 * @description: 梳排序
 */
public class CombSort {
    /**
     * 梳排序
     *
     * @param unsorted 待排序列
     */
    public static void combSort(int[] unsorted) {
        int gap = unsorted.length;
        boolean swapped = true;
        while (gap > 1 || swapped) {
            if (gap > 1) {
                gap = (int) (gap / 1.3);
            }
            int i = 0;
            swapped = false;
            while (i + gap < unsorted.length) {
                if (unsorted[i] > unsorted[i + gap]) {
                    swap(unsorted, i, i + gap);
                    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;
    }


    public static void main(String[] args) {
        int[] unsorted = {11, 95, 45, 15, 78, 84, 51, 24, 12};
        System.out.println("**************梳排序******************");
        System.out.println("排序前：");
        CommonUtils.display(unsorted);
        System.out.println("排序后：");
        combSort(unsorted);
        CommonUtils.display(unsorted);
    }
}

测试结果