梳排序的知名度远没有其他排序算法那么高,它是在冒泡排序的基础上做的改进,引入类似“步长”以及“子序列”概念,这两个概念在后面的排序算法中会经常提及。
待排序列:{10, 2, 11, 8, 7} groupNums = length = 5
步长系数(分组系数)coefficient = 1.3
排序过程如下图所示。
Java
1 package com.algorithm.sort;
2
3 import java.util.Arrays;
4
5 /**
6 * 梳排序
7 * Created by 余林丰 on 2017/6/20.
8 */
9 public class Comb {
10 public static void main(String[] args) {
11 int[] nums = {10, 2, 11, 8, 7};
12 nums = combSort(nums);
13 System.out.println(Arrays.toString(nums));
14 }
15
16 /**
17 * 梳排序
18 * @param nums 待排序数组
19 * @return 排好序的数组
20 */
21 private static int[] combSort(int[] nums) {
22 float cofficient = 1.3f; //步长系数(分组系数) = 1.3,大量试验获得的最佳值
23 int groupNums = nums.length;
24 boolean flag = false;
25 while (groupNums > 1 || flag) {
26 groupNums = (int) ((groupNums / cofficient) > 1 ? (groupNums / cofficient) : 1);
27 flag = false;
28 for (int i = 0; i + groupNums < nums.length; i++) {
29 if (nums[i] > nums[i + groupNums]) {
30 int temp = nums[i];
31 nums[i] = nums[i + groupNums];
32 nums[i + groupNums] = temp;
33 flag = true;
34 }
35 }
36 }
37 return nums;
38 }
39 }
Python3
1 #梳排序
2 def comb_sort(nums):
3 cofficient = 1.3 #最佳系数
4 groupNums = len(nums)
5 flag = False
6 while groupNums > 1 or flag:
7 groupNums = int(groupNums / cofficient) if (groupNums / cofficient) > 1 else 1
8 flag = False
9 for i in range(len(nums)):
10 if i + groupNums >= len(nums):
11 break
12 if nums[i] > nums[i + groupNums]:
13 temp = nums[i]
14 nums[i] = nums[i + groupNums]
15 nums[i + groupNums] = temp
16 flag = True
17
18 return nums
19
20 nums = [10, 2, 11, 8, 7]
21 nums = comb_sort(nums)
22 print(nums)