JFinal

登录 注册

排序算法:梳排序

排序算法梳排序


递减率:递减率


基本思想:梳排序和希尔排序很类似。希尔排序是在直接插入排序的基础上做的优化,而梳排序是在冒泡排序的基础上做的优化。也是想希尔排序一样,将待排序序列通过增量分为若干个子序列,然后对子序列进行一趟冒泡排序,一步步减小增量,直至增量为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));
	}
}


评论

  • 发送