类别：排序-交换排序
参看 维基百科的定义
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