排序算法梳排序

递减率：

基本思想：梳排序和希尔排序很类似。希尔排序是在直接插入排序的基础上做的优化，而梳排序是在冒泡排序的基础上做的优化。也是想希尔排序一样，将待排序序列通过增量分为若干个子序列，然后对子序列进行一趟冒泡排序，一步步减小增量，直至增量为1。所以梳排序的最后一次排序是冒泡排序。

example：数组[8 7 6 5 4 3 2 1]

                 数组.length/1.3 = 6 , 比较8和2，7和1，然后较小的数放在前边。

                 得数组[2 1 6 5 4 3 8 7]

                 6/1.3 = 4 , 比较2和4，1和3，6和8，5和7，然后较小的数放在前边。

                 得数组[2 1 6 5 4 3 8 7]

               4/1.3 = 3 , 比较2和5，1和4，6和3，5和8，4和7，然后较小的数放在前边。

                 得数组[2 1 3 5 4 6 8 7]

                 3/1.3 = 2，……

                 2/1.3 = 1，……

                 得数组[1 2 3 4 5 6 7 8]

注：当距离为1时，和冒泡排序一样。

import java.util.Arrays;

public class CombSort {

	private static int[] combSort(int[] nums){
		float cofficient = 1.3f;
		int group = nums.length;
		boolean flag = false;
		while(group>1||flag){
			group = (int)((group/cofficient)>1?(group/cofficient):1);
			flag = false;
			for (int i = 0; i+group< nums.length; i++) {
				if(nums[i]>nums[i+group]){
					int temp = nums[i];
					nums[i] = nums[i+group];
					nums[i+group] = temp;
					flag = true;
				}
			}
		}
		return nums;
	}
	
	public static void main(String[] args) {
		int[] nums = {9,8,7,6,5,4,3,2,1};
		nums = combSort(nums);
		System.out.println(Arrays.toString(nums));
	}
}