2.比較排序之梳排序

　　梳排序的知名度遠沒有其他排序演算法那麼高，它是在冒泡排序的基礎上做的改進，引入類似“步長”以及“子序列”概念，這兩個概念在後面的排序演算法中會經常提及。

　　待排序列：{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)