算法：四种冒泡排序（Bubble Sort）实现

背景

大学关于排序的算法，好像就学会了冒泡排序，这个算是排序界的 hello,world 了，冒泡排序的定义如下：

重复的遍历数组。

/// <summary>
/// 重复的遍历数组。
/// 每次遍历都比较两个元素，如果顺序不正确就把他们交换一下。
/// 如果遍历后只交换了 1 次或 0 次，排序结束。
/// 最多需要 length -1 次遍历，第 iterTimes 次需要遍历 length - iterTimes - 1 个元素。
/// </summary>

四种实现代码

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace DataStuctureStudy.Sorts
  8 {
  9     /// <summary>
 10     /// 重复的遍历数组。
 11     /// 每次遍历都比较两个元素，如果顺序不正确就把他们交换一下。
 12     /// 如果遍历后只交换了 1 次或 0 次，排序结束。
 13     /// 最多需要 length -1 次遍历，第 iterTimes 次需要遍历 length - iterTimes - 1 个元素。
 14     /// </summary>
 15     class BubbleSort<T>
 16         where T : IComparable<T>
 17     {
 18         private static void Swap(T[] items, int left, int right)
 19         {
 20             if (left != right)
 21             {
 22                 var temp = items[left];
 23                 items[left] = items[right];
 24                 items[right] = temp;
 25             }
 26         }
 27 
 28         public static void Sort1(T[] items)
 29         {
 30             if (items.Length < 2)
 31             {
 32                 return;
 33             }
 34 
 35             int swappedTimes;
 36             do
 37             {
 38                 swappedTimes = 0;
 39                 // 重复的遍历数组。
 40                 for (var i = 1; i < items.Length; i++)
 41                 {
 42                     // 每次遍历都比较两个元素，如果顺序不正确就把他们交换一下。
 43                     if (items[i - 1].CompareTo(items[i]) > 0)
 44                     {
 45                         Swap(items, i - 1, i);
 46                         swappedTimes++;
 47                     }
 48                 }
 49             } while (swappedTimes > 1);// 如果遍历后只交换了 1 次或 0 次，排序结束。
 50         }
 51 
 52         public static void Sort2(T[] items)
 53         {
 54             if (items.Length < 2)
 55             {
 56                 return;
 57             }
 58 
 59             int swappedTimes;
 60             do
 61             {
 62                 swappedTimes = 0;
 63                 int iterTimes = 0;
 64 
 65                 for (var i = 1; i < items.Length - iterTimes; i++)
 66                 {
 67                     if (items[i - 1].CompareTo(items[i]) > 0)
 68                     {
 69                         Swap(items, i - 1, i);
 70                         swappedTimes++;
 71                     }
 72                 }
 73                 iterTimes--;
 74             } while (swappedTimes > 1);
 75         }
 76 
 77         public static void Sort3(T[] items)
 78         {
 79             if (items.Length < 2)
 80             {
 81                 return;
 82             }
 83 
 84             for (var i = 1; i < items.Length; i++)
 85             {
 86                 int swappedTimes = 0;
 87                 for (var j = 1; j < items.Length - i + 1; j++)
 88                 {
 89                     if (items[j - 1].CompareTo(items[j]) > 0)
 90                     {
 91                         Swap(items, j - 1, j);
 92                         swappedTimes++;
 93                     }
 94                 }
 95 
 96                 if (swappedTimes <= 1)
 97                 {
 98                     break;
 99                 }
100             }
101         }
102 
103         public static void Sort4(T[] items)
104         {
105             Sort4Helper(items, 0);
106         }
107 
108         private static void Sort4Helper(T[] items, int iterTimes)
109         {
110             if (items.Length < 2)
111             {
112                 return;
113             }
114 
115             int swappedTimes = 0;
116             for (var i = 1; i < items.Length - iterTimes; i++)
117             {
118                 if (items[i - 1].CompareTo(items[i]) > 0)
119                 {
120                     Swap(items, i - 1, i);
121                     swappedTimes++;
122                 }
123             }
124 
125             if (swappedTimes <= 1)
126             {
127                 return;
128             }
129 
130             Sort4Helper(items, iterTimes + 1);
131         }
132     }
133 }

备注

真不知道如何说，说明我对这些简单算法的理解还不够深入。