推荐订阅源

类别：排序-交换排序
参看 维基百科的定义

 1 using System;
 2  using System.Collections.Generic;
 3 
 4 namespace Com.Colobu.Algorithm.Exchange
 5 {
 6     /// <summary>
 7     /// <b>Comb sort</b> improves on bubble sort, and rivals algorithms like Quicksort. 
 8     /// The basic idea is to eliminate turtles, or small values near the end of the list, 
 9     /// since in a bubble sort these slow the sorting down tremendously.
10     /// 
11     /// 平均时间复杂度:O(nlogn)
12     /// Stability:No
13     /// </summary>
14     public class CombSortAlgorithm
15     {
16         public static void CombSort<T>(IList<T> szArray) where T : IComparable
17         {
18             int gap = szArray.Count;
19             bool swapped = true;
20 
21             while (gap > 1 || swapped)
22             {
23                 if (gap > 1)
24                 {
25                     gap = (int)(gap / 1.25);
26                 }
27 
28                 int i = 0;
29                 swapped = false;
30                 while (i + gap < szArray.Count)
31                 {
32                     if (szArray[i].CompareTo(szArray[i + gap]) > 0)
33                     {
34                         T t = szArray[i];
35                         szArray[i] = szArray[i + gap];
36                         szArray[i + gap] = t;
37                         swapped = true;
38                     }
39                     i++;
40                 }
41             }
42         }
43     }
44 }
45