8种主要排序算法的CSharp实现

发表于 1899-11-30 更新于 2025-03-27 分类于 Lessons ，排序算法 Valine：

8种主要排序算法的C#实现

Excerpt
8种主要排序算法的实现及优化，包含选择排序，冒泡排序，插入排序，快速排序，归并排序，堆排序，希尔排序，基数排序。文末实际测试并比较。

新的一年到了，很多园友都辞职要去追求更好的工作环境，我也是其中一个，呵呵！

最近闲暇的时候我开始重温一些常用的算法。老早就买了《算法导论》，一直都没啃下去。

这本书确实很好，只是太难读了，总是读了几章就又读不下去了！工作上也几乎用不到。

我这段时间发现看这些排序算法比以前容易了很多，就借此机会将它们整理总结起来。

一是方便以后重温，二是可以应对笔试面试。同时也希望这篇博文可以帮助各位刚辞职和正在学习排序算法的园友。

PS：有可能实现的代码并不是最优的，如果有什么错误或者值得改进的地方，还请大家帮忙指出。

简介

排序算法是我们编程中遇到的最多的算法。目前主流的算法有8种。

平均时间复杂度从高到低依次是：

冒泡排序（o(n²)），选择排序（o(n²)），插入排序（o(n²)），堆排序（o(nlogn)），

归并排序（o(nlogn)），快速排序（o(nlogn)），希尔排序（o(n^1.25)），基数排序（o(n)）

这些平均时间复杂度是参照维基百科排序算法罗列的。

是计算的理论平均值，并不意味着你的代码实现能达到这样的程度。

例如希尔排序，时间复杂度是由选择的步长决定的。基数排序时间复杂度最小，

但我实现的基数排序的速度并不是最快的，后面的结果测试图可以看到。

本文代码实现使用的数据源类型为IList，这样可以兼容int[]和List(虽然int[]有ToList()，

List有ToArray()，哈哈！)。

选择排序

选择排序是我觉得最简单暴力的排序方式了。

以前刚接触排序算法的时候，感觉算法太多搞不清，唯独记得选择排序的做法及实现。

原理：找出参与排序的数组最大值，放到末尾（或找到最小值放到开头）维基入口

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> SelectSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; data.Count - <span>1</span>; i++<span>)
</span><span> 4</span> <span>            {
</span><span> 5</span>                 <span>int</span> min =<span> i;
</span><span> 6</span>                 <span>int</span> temp =<span> data[i];
</span><span> 7</span>                 <span>for</span> (<span>int</span> j = i + <span>1</span>; j &lt; data.Count; j++<span>)
</span><span> 8</span> <span>                {
</span><span> 9</span>                     <span>if</span> (data[j] &lt;<span> temp)
</span><span>10</span> <span>                    {
</span><span>11</span>                         min =<span> j;
</span><span>12</span>                         temp =<span> data[j];
</span><span>13</span> <span>                    }
</span><span>14</span> <span>                }
</span><span>15</span>                 <span>if</span> (min !=<span> i)
</span><span>16</span> <span>                    Swap(data, min, i);
</span><span>17</span> <span>            }
</span><span>18</span>         }

过程解析：将剩余数组的最小数交换到开头。

冒泡排序

冒泡排序是笔试面试经常考的内容，虽然它是这些算法里排序速度最慢的（汗），后面有测试为证。

原理：从头开始，每一个元素和它的下一个元素比较，如果它大，就将它与比较的元素交换，否则不动。

这意味着，大的元素总是在向后慢慢移动直到遇到比它更大的元素。所以每一轮交换完成都能将最大值

冒到最后。维基入口

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> BubbleSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>for</span> (<span>int</span> i = data.Count - <span>1</span>; i &gt; <span>0</span>; i--<span>)
</span><span> 4</span> <span>            {
</span><span> 5</span>                 <span>for</span> (<span>int</span> j = <span>0</span>; j &lt; i; j++<span>)
</span><span> 6</span> <span>                {
</span><span> 7</span>                     <span>if</span> (data[j] &gt; data[j + <span>1</span><span>])
</span><span> 8</span>                         Swap(data, j, j + <span>1</span><span>);
</span><span> 9</span> <span>                }
</span><span>10</span> <span>            }
</span><span>11</span>         }

过程解析：中需要注意的是j<i，每轮冒完泡必然会将最大值排到数组末尾，所以需要排序的数应该是在减少的。

很多网上版本每轮冒完泡后依然还是将所有的数进行第二轮冒泡即j<data.Count-1，这样会增加比较次数。

通过标识提升冒泡排序

在维基上看到，可以通过添加标识来分辨剩余的数是否已经有序来减少比较次数。感觉很有意思，可以试试。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> BubbleSortImprovedWithFlag(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>bool</span><span> flag;
</span><span> 4</span>             <span>for</span> (<span>int</span> i = data.Count - <span>1</span>; i &gt; <span>0</span>; i--<span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 flag = <span>true</span><span>;
</span><span> 7</span>                 <span>for</span> (<span>int</span> j = <span>0</span>; j &lt; i; j++<span>)
</span><span> 8</span> <span>                {
</span><span> 9</span>                     <span>if</span> (data[j] &gt; data[j + <span>1</span><span>])
</span><span>10</span> <span>                    {
</span><span>11</span>                         Swap(data, j, j + <span>1</span><span>);
</span><span>12</span>                         flag = <span>false</span><span>;
</span><span>13</span> <span>                    }
</span><span>14</span> <span>                }
</span><span>15</span>                 <span>if</span> (flag) <span>break</span><span>;
</span><span>16</span> <span>            }
</span><span>17</span>         }

过程解析：发现某轮冒泡没有任何数进行交换（即已经有序），就跳出排序。

我起初也以为这个方法是应该有不错效果的，可是实际测试结果并不如想的那样。和未优化耗费时间一样（对于随机数列）。

由果推因，那么应该是冒泡排序对于随机数列，当剩余数列有序的时候，也没几个数要排列了！？

不过如果已经是有序数列或者部分有序的话，这个冒泡方法将会提升很大速度。

鸡尾酒排序（来回排序）

对冒泡排序进行更大的优化

冒泡排序只是单向冒泡，而鸡尾酒来回反复双向冒泡。

原理：自左向右将大数冒到末尾，然后将剩余数列再自右向左将小数冒到开头，如此循环往复。维基入口

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> BubbleCocktailSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>bool</span><span> flag;
</span><span> 4</span>             <span>int</span> m = <span>0</span>, n = <span>0</span><span>;
</span><span> 5</span>             <span>for</span> (<span>int</span> i = data.Count - <span>1</span>; i &gt; <span>0</span>; i--<span>)
</span><span> 6</span> <span>            {
</span><span> 7</span>                 flag = <span>true</span><span>;
</span><span> 8</span>                 <span>if</span> (i % <span>2</span> == <span>0</span><span>)
</span><span> 9</span> <span>                {
</span><span>10</span>                     <span>for</span> (<span>int</span> j = n; j &lt; data.Count - <span>1</span> - m; j++<span>)
</span><span>11</span> <span>                    {
</span><span>12</span>                         <span>if</span> (data[j] &gt; data[j + <span>1</span><span>])
</span><span>13</span> <span>                        {
</span><span>14</span>                             Swap(data, j, j + <span>1</span><span>);
</span><span>15</span>                             flag = <span>false</span><span>;
</span><span>16</span> <span>                        }
</span><span>17</span> <span>                    }
</span><span>18</span>                     <span>if</span> (flag) <span>break</span><span>;
</span><span>19</span>                     m++<span>;
</span><span>20</span> <span>                }
</span><span>21</span>                 <span>else</span>
<span>22</span> <span>                {
</span><span>23</span>                     <span>for</span> (<span>int</span> k = data.Count - <span>1</span> - m; k &gt; n; k--<span>)
</span><span>24</span> <span>                    {
</span><span>25</span>                         <span>if</span> (data[k] &lt; data[k - <span>1</span><span>])
</span><span>26</span> <span>                        {
</span><span>27</span>                             Swap(data, k, k - <span>1</span><span>);
</span><span>28</span>                             flag = <span>false</span><span>;
</span><span>29</span> <span>                        }
</span><span>30</span> <span>                    }
</span><span>31</span>                     <span>if</span> (flag) <span>break</span><span>;
</span><span>32</span>                     n++<span>;
</span><span>33</span> <span>                }
</span><span>34</span> <span>            }
</span><span>35</span>         }

过程解析：分析第i轮冒泡，i是偶数则将剩余数列最大值向右冒泡至末尾，是奇数则将剩余数列最小值

向左冒泡至开头。对于剩余数列，n为始，data.Count-1-m为末。

来回冒泡比单向冒泡：对于随机数列，更容易得到有序的剩余数列。因此这里使用标识将会提升的更加明显。

插入排序

插入排序是一种对于有序数列高效的排序。非常聪明的排序。只是对于随机数列，效率一般，交换的频率高。

原理：通过构建有序数列，将未排序的数从后向前比较，找到合适位置并插入。维基入口

第一个数当作有序数列。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> InsertSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span><span> temp;
</span><span> 4</span>             <span>for</span> (<span>int</span> i = <span>1</span>; i &lt; data.Count; i++<span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 temp =<span> data[i];
</span><span> 7</span>                 <span>for</span> (<span>int</span> j = i - <span>1</span>; j &gt;= <span>0</span>; j--<span>)
</span><span> 8</span> <span>                {
</span><span> 9</span>                     <span>if</span> (data[j] &gt;<span> temp)
</span><span>10</span> <span>                    {
</span><span>11</span>                         data[j + <span>1</span>] =<span> data[j];
</span><span>12</span>                         <span>if</span> (j == <span>0</span><span>)
</span><span>13</span> <span>                        {
</span><span>14</span>                             data[<span>0</span>] =<span> temp;
</span><span>15</span>                             <span>break</span><span>;
</span><span>16</span> <span>                        }
</span><span>17</span> <span>                    }
</span><span>18</span>                     <span>else</span>
<span>19</span> <span>                    {
</span><span>20</span>                         data[j + <span>1</span>] =<span> temp;
</span><span>21</span>                         <span>break</span><span>;
</span><span>22</span> <span>                    }
</span><span>23</span> <span>                }
</span><span>24</span> <span>            }
</span><span>25</span>         }

过程解析：将要排序的数（索引为i）存储起来，向前查找合适位置j+1，将i-1到j+1的元素依次向后

移动一位，空出j+1，然后将之前存储的值放在这个位置。

这个方法写的不如维基上的简洁清晰，由于合适位置是j+1所以多出了对j==0的判断，但实际效率影响无差别。

建议比照维基和我写的排序，自行选择。

二分查找法优化插入排序

插入排序主要工作是在有序的数列中对要排序的数查找合适的位置，而查找里面经典的二分查找法正可以适用。

原理：通过二分查找法的方式找到一个位置索引。当要排序的数插入这个位置时，大于前一个数，小于后一个数。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> InsertSortImprovedWithBinarySearch(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span><span> temp;
</span><span> 4</span>             <span>int</span><span> tempIndex;
</span><span> 5</span>             <span>for</span> (<span>int</span> i = <span>1</span>; i &lt; data.Count; i++<span>)
</span><span> 6</span> <span>            {
</span><span> 7</span>                 temp =<span> data[i];
</span><span> 8</span>                 tempIndex = BinarySearchForInsertSort(data, <span>0</span><span>, i, i);
</span><span> 9</span>                 <span>for</span> (<span>int</span> j = i - <span>1</span>; j &gt;= tempIndex; j--<span>)
</span><span>10</span> <span>                {
</span><span>11</span>                     data[j + <span>1</span>] =<span> data[j];
</span><span>12</span> <span>                }
</span><span>13</span>                 data[tempIndex] =<span> temp;
</span><span>14</span> <span>            }
</span><span>15</span> <span>        }
</span><span>16</span> 
<span>17</span>         <span>public</span> <span>static</span> <span>int</span> BinarySearchForInsertSort(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span> high, <span>int</span><span> key)
</span><span>18</span> <span>        {
</span><span>19</span>             <span>if</span> (low &gt;= data.Count - <span>1</span><span>)
</span><span>20</span>                 <span>return</span> data.Count - <span>1</span><span>;
</span><span>21</span>             <span>if</span> (high &lt;= <span>0</span><span>)
</span><span>22</span>                 <span>return</span> <span>0</span><span>;
</span><span>23</span>             <span>int</span> mid = (low + high) / <span>2</span><span>;
</span><span>24</span>             <span>if</span> (mid == key) <span>return</span><span> mid;
</span><span>25</span>             <span>if</span> (data[key] &gt;<span> data[mid])
</span><span>26</span> <span>            {
</span><span>27</span>                 <span>if</span> (data[key] &lt; data[mid + <span>1</span><span>])
</span><span>28</span>                     <span>return</span> mid + <span>1</span><span>;
</span><span>29</span>                 <span>return</span> BinarySearchForInsertSort(data, mid + <span>1</span><span>, high, key);
</span><span>30</span> <span>            }
</span><span>31</span>             <span>else  <span>// data[key] &lt;= data[mid]</span></span>
<span>32</span> <span>            {
</span><span>33</span>                 <span>if</span> (mid - <span>1</span> &lt; <span>0</span>) <span>return</span> <span>0</span><span>;
</span><span>34</span>                 <span>if</span> (data[key] &gt; data[mid - <span>1</span><span>])
</span><span>35</span>                     <span>return</span><span> mid;
</span><span>36</span>                 <span>return</span> BinarySearchForInsertSort(data, low, mid - <span>1</span><span>, key);
</span><span>37</span> <span>            }
</span><span>38</span>         }

过程解析：需要注意的是二分查找方法实现中high-low==1的时候mid==low，所以需要33行

mid-1<0即mid==0的判断，否则下行会索引越界。

快速排序

快速排序是一种有效比较较多的高效排序。它包含了“分而治之”以及“哨兵”的思想。

原理：从数列中挑选一个数作为“哨兵”，使比它小的放在它的左侧，比它大的放在它的右侧。将要排序是数列递归地分割到

最小数列，每次都让分割出的数列符合“哨兵”的规则，自然就将数列变得有序。维基入口

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortStrict(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             QuickSortStrict(data, <span>0</span>, data.Count - <span>1</span><span>);
</span><span> 4</span> <span>        }
</span><span> 5</span> 
<span> 6</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortStrict(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 7</span> <span>        {
</span><span> 8</span>             <span>if</span> (low &gt;= high) <span>return</span><span>;
</span><span> 9</span>             <span>int</span> temp =<span> data[low];
</span><span>10</span>             <span>int</span> i = low + <span>1</span>, j =<span> high;
</span><span>11</span>             <span>while</span> (<span>true</span><span>)
</span><span>12</span> <span>            {
</span><span>13</span>                 <span>while</span> (data[j] &gt; temp) j--<span>;
</span><span>14</span>                 <span>while</span> (data[i] &lt; temp &amp;&amp; i &lt; j) i++<span>;
</span><span>15</span>                 <span>if</span> (i &gt;= j) <span>break</span><span>;
</span><span>16</span> <span>                Swap(data, i, j);
</span><span>17</span>                 i++; j--<span>;
</span><span>18</span> <span>            }
</span><span>19</span>             <span>if</span> (j !=<span> low)
</span><span>20</span> <span>                Swap(data, low, j);
</span><span>21</span>             QuickSortStrict(data, j + <span>1</span><span>, high);
</span><span>22</span>             QuickSortStrict(data, low, j - <span>1</span><span>);
</span><span>23</span>         }

过程解析：取的哨兵是数列的第一个值，然后从第二个和末尾同时查找，左侧要显示的是小于哨兵的值，

所以要找到不小于的i，右侧要显示的是大于哨兵的值，所以要找到不大于的j。将找到的i和j的数交换，

这样可以减少交换次数。i>=j时，数列全部查找了一遍，而不符合条件j必然是在小的那一边，而哨兵

是第一个数，位置本应是小于自己的数。所以将哨兵与j交换，使符合“哨兵”的规则。

这个版本的缺点在于如果是有序数列排序的话，递归次数会很可怕的。

另一个版本

这是维基上的一个C#版本，我觉得很有意思。这个版本并没有严格符合“哨兵”的规则。但却将“分而治之”

以及“哨兵”思想融入其中，代码简洁。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortRelax(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             QuickSortRelax(data, <span>0</span>, data.Count - <span>1</span><span>);
</span><span> 4</span> <span>        }
</span><span> 5</span> 
<span> 6</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortRelax(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 7</span> <span>        {
</span><span> 8</span>             <span>if</span> (low &gt;= high) <span>return</span><span>;
</span><span> 9</span>             <span>int</span> temp = data[(low + high) / <span>2</span><span>];
</span><span>10</span>             <span>int</span> i = low - <span>1</span>, j = high + <span>1</span><span>;
</span><span>11</span>             <span>while</span> (<span>true</span><span>)
</span><span>12</span> <span>            {
</span><span>13</span>                 <span>while</span> (data[++i] &lt;<span> temp) ;
</span><span>14</span>                 <span>while</span> (data[--j] &gt;<span> temp) ;
</span><span>15</span>                 <span>if</span> (i &gt;= j) <span>break</span><span>;
</span><span>16</span> <span>                Swap(data, i, j);
</span><span>17</span> <span>            }
</span><span>18</span>             QuickSortRelax(data, j + <span>1</span><span>, high);
</span><span>19</span>             QuickSortRelax(data, low, i - <span>1</span><span>);
</span><span>20</span>         }

过程解析：取的哨兵是数列中间的数。将数列分成两波，左侧小于等于哨兵，右侧大于等于哨兵。

也就是说，哨兵不一定处于两波数的中间。虽然哨兵不在中间，但不妨碍“哨兵”的思想的实现。所以

这个实现也可以达到快速排序的效果。但却造成了每次递归完成，要排序的数列数总和没有减少（除非i==j）。

针对这个版本的缺点，我进行了优化

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortRelaxImproved(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             QuickSortRelaxImproved(data, <span>0</span>, data.Count - <span>1</span><span>);
</span><span> 4</span> <span>        }
</span><span> 5</span> 
<span> 6</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortRelaxImproved(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 7</span> <span>        {
</span><span> 8</span>             <span>if</span> (low &gt;= high) <span>return</span><span>;
</span><span> 9</span>             <span>int</span> temp = data[(low + high) / <span>2</span><span>];
</span><span>10</span>             <span>int</span> i = low - <span>1</span>, j = high + <span>1</span><span>;
</span><span>11</span>             <span>int</span> index = (low + high) / <span>2</span><span>;
</span><span>12</span>             <span>while</span> (<span>true</span><span>)
</span><span>13</span> <span>            {
</span><span>14</span>                 <span>while</span> (data[++i] &lt;<span> temp) ;
</span><span>15</span>                 <span>while</span> (data[--j] &gt;<span> temp) ;
</span><span>16</span>                 <span>if</span> (i &gt;= j) <span>break</span><span>;
</span><span>17</span> <span>                Swap(data, i, j);
</span><span>18</span>                 <span>if</span> (i == index) index =<span> j;
</span><span>19</span>                 <span>else</span> <span>if</span> (j == index) index =<span> i;
</span><span>20</span> <span>            }
</span><span>21</span>             <span>if</span> (j ==<span> i)
</span><span>22</span> <span>            {
</span><span>23</span>                 QuickSortRelaxImproved(data, j + <span>1</span><span>, high);
</span><span>24</span>                 QuickSortRelaxImproved(data, low, i - <span>1</span><span>);
</span><span>25</span> <span>            }
</span><span>26</span>             <span>else</span> <span>//</span><span>i-j==1</span>
<span>27</span> <span>            {
</span><span>28</span>                 <span>if</span> (index &gt;=<span> i)
</span><span>29</span> <span>                {
</span><span>30</span>                     <span>if</span> (index !=<span> i)
</span><span>31</span> <span>                        Swap(data, index, i);
</span><span>32</span>                     QuickSortRelaxImproved(data, i + <span>1</span><span>, high);
</span><span>33</span>                     QuickSortRelaxImproved(data, low, i - <span>1</span><span>);
</span><span>34</span> <span>                }
</span><span>35</span>                 <span>else <span>//</span><span>index &lt; i</span></span>
<span>36</span> <span>                {
</span><span>37</span>                     <span>if</span> (index !=<span> j)
</span><span>38</span> <span>                        Swap(data, index, j);
</span><span>39</span>                     QuickSortRelaxImproved(data, j + <span>1</span><span>, high);
</span><span>40</span>                     QuickSortRelaxImproved(data, low, j - <span>1</span><span>);
</span><span>41</span> <span>                }
</span><span>42</span> <span>            }
</span><span>43</span>         }

过程解析：定义了一个变量Index，来跟踪哨兵的位置。发现哨兵最后在小于自己的那堆，

那就与j交换，否则与i交换。达到每次递归都能减少要排序的数列数总和的目的。

归并排序

归并排序也是采用“分而治之”的方式。刚发现分治法是一种算法范式，我还一直以为是一种需要意会的思想呢。

不好意思了，孤陋寡闻了，哈哈！

原理：将两个有序的数列，通过比较，合并为一个有序数列。维基入口

为方便理解，此处实现用了List的一些方法，随后有IList版本。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> List&lt;<span>int</span>&gt; MergeSortOnlyList(List&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>if</span> (low ==<span> high)
</span><span> 4</span>                 <span>return</span> <span>new</span> List&lt;<span>int</span>&gt;<span> { data[low] };
</span><span> 5</span>             List&lt;<span>int</span>&gt; mergeData = <span>new</span> List&lt;<span>int</span>&gt;<span>();
</span><span> 6</span>             <span>int</span> mid = (low + high) / <span>2</span><span>;
</span><span> 7</span>             List&lt;<span>int</span>&gt; leftData =<span> MergeSortOnlyList(data, low, mid);
</span><span> 8</span>             List&lt;<span>int</span>&gt; rightData = MergeSortOnlyList(data, mid + <span>1</span><span>, high);
</span><span> 9</span>             <span>int</span> i = <span>0</span>, j = <span>0</span><span>;
</span><span>10</span>             <span>while</span> (<span>true</span><span>)
</span><span>11</span> <span>            {
</span><span>12</span>                 <span>if</span> (leftData[i] &lt;<span> rightData[j])
</span><span>13</span> <span>                {
</span><span>14</span> <span>                    mergeData.Add(leftData[i]);
</span><span>15</span>                     <span>if</span> (++i ==<span> leftData.Count)
</span><span>16</span> <span>                    {
</span><span>17</span>                         mergeData.AddRange(rightData.GetRange(j, rightData.Count -<span> j));
</span><span>18</span>                         <span>break</span><span>;
</span><span>19</span> <span>                    }
</span><span>20</span> <span>                }
</span><span>21</span>                 <span>else</span>
<span>22</span> <span>                {
</span><span>23</span> <span>                    mergeData.Add(rightData[j]);
</span><span>24</span>                     <span>if</span> (++j ==<span> rightData.Count)
</span><span>25</span> <span>                    {
</span><span>26</span>                         mergeData.AddRange(leftData.GetRange(i, leftData.Count -<span> i));
</span><span>27</span>                         <span>break</span><span>;
</span><span>28</span> <span>                    }
</span><span>29</span> <span>                }
</span><span>30</span> <span>            }
</span><span>31</span>             <span>return</span><span> mergeData;
</span><span>32</span> <span>        }
</span><span>33</span> 
<span>34</span>         <span>public</span> <span>static</span> List&lt;<span>int</span>&gt; MergeSortOnlyList(List&lt;<span>int</span>&gt;<span> data)
</span><span>35</span> <span>        {
</span><span>36</span>             data = MergeSortOnlyList(data, <span>0</span>, data.Count - <span>1</span><span>);  <span>//不会改变外部引用 参照<a href="http://www.cnblogs.com/fatbird/p/parametersInCsharp.html" target="_blank">C#参数传递
</a></span></span><span>37</span>             <span>return</span><span> data;
</span><span>38</span>         }

过程解析：将数列分为两部分，分别得到两部分数列的有序版本，然后逐个比较，将比较出的小数逐个放进

新的空数列中。当一个数列放完后，将另一个数列剩余数全部放进去。

IList版本

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> IList&lt;<span>int</span>&gt; MergeSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             data = MergeSort(data, <span>0</span>, data.Count - <span>1</span><span>);
</span><span> 4</span>             <span>return</span><span> data;
</span><span> 5</span> <span>        }
</span><span> 6</span> 
<span> 7</span>         <span>public</span> <span>static</span> IList&lt;<span>int</span>&gt; MergeSort(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 8</span> <span>        {
</span><span> 9</span>             <span>int</span> length = high - low + <span>1</span><span>;
</span><span>10</span>             IList&lt;<span>int</span>&gt; mergeData =<span> NewInstance(data, length);
</span><span>11</span>             <span>if</span> (low ==<span> high)
</span><span>12</span> <span>            {
</span><span>13</span>                 mergeData[<span>0</span>] =<span> data[low];
</span><span>14</span>                 <span>return</span><span> mergeData;
</span><span>15</span> <span>            }
</span><span>16</span>             <span>int</span> mid = (low + high) / <span>2</span><span>;
</span><span>17</span>             IList&lt;<span>int</span>&gt; leftData =<span> MergeSort(data, low, mid);
</span><span>18</span>             IList&lt;<span>int</span>&gt; rightData = MergeSort(data, mid + <span>1</span><span>, high);
</span><span>19</span>             <span>int</span> i = <span>0</span>, j = <span>0</span><span>;
</span><span>20</span>             <span>while</span> (<span>true</span><span>)
</span><span>21</span> <span>            {
</span><span>22</span>                 <span>if</span> (leftData[i] &lt;<span> rightData[j])
</span><span>23</span> <span>                {
</span><span>24</span>                     mergeData[i + j] = leftData[i++]; <span>//</span><span>不能使用Add,Array Length不可变</span>
<span>25</span>                     <span>if</span> (i ==<span> leftData.Count)
</span><span>26</span> <span>                    {
</span><span>27</span>                         <span>int</span> rightLeft = rightData.Count -<span> j;
</span><span>28</span>                         <span>for</span> (<span>int</span> m = <span>0</span>; m &lt; rightLeft; m++<span>)
</span><span>29</span> <span>                        {
</span><span>30</span>                             mergeData[i + j] = rightData[j++<span>];
</span><span>31</span> <span>                        }
</span><span>32</span>                         <span>break</span><span>;
</span><span>33</span> <span>                    }
</span><span>34</span> <span>                }
</span><span>35</span>                 <span>else</span>
<span>36</span> <span>                {
</span><span>37</span>                     mergeData[i + j] = rightData[j++<span>];
</span><span>38</span>                     <span>if</span> (j ==<span> rightData.Count)
</span><span>39</span> <span>                    {
</span><span>40</span>                         <span>int</span> leftleft = leftData.Count -<span> i;
</span><span>41</span>                         <span>for</span> (<span>int</span> n = <span>0</span>; n &lt; leftleft; n++<span>)
</span><span>42</span> <span>                        {
</span><span>43</span>                             mergeData[i + j] = leftData[i++<span>];
</span><span>44</span> <span>                        }
</span><span>45</span>                         <span>break</span><span>;
</span><span>46</span> <span>                    }
</span><span>47</span> <span>                }
</span><span>48</span> <span>            }
</span><span>49</span>             <span>return</span><span> mergeData;
</span><span>50</span> 
<span>51</span>         }

过程原理与上个一样，此处就不赘述了。

堆排序

堆排序是根据堆这种数据结构设计的一种算法。堆的特性：父节点的值总是小于（或大于）它的子节点。近似二叉树。

原理：将数列构建为最大堆数列（即父节点总是最大值），将最大值（即根节点）交换到数列末尾。这样要排序的数列数总和减少，

同时根节点不再是最大值，调整最大堆数列。如此重复，最后得到有序数列。维基入口有趣的演示

实现准备：如何将数列构造为堆——父节点i的左子节点为2i+1，右子节点为2i+2。节点i的父节点为floor((i-1)/2)。

实现如下（这个实现判断和临时变量使用太多，导致效率低，评论中@小城故事提出了更好的实现）：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> HeapSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span> <span>            BuildMaxHeapify(data);
</span><span> 4</span>             <span>int</span> j =<span> data.Count;
</span><span> 5</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt;<span> j; )
</span><span> 6</span> <span>            {
</span><span> 7</span>                 Swap(data, i, --<span>j);
</span><span> 8</span>                 <span>if</span> (j - <span>2</span> &lt; <span>0</span><span>)  <span>//只剩下1个数 j代表余下要排列的数的个数
</span></span><span> 9</span>                     <span>break</span><span>;
</span><span>10</span>                 <span>int</span> k = <span>0</span><span>;
</span><span>11</span>                 <span>while</span> (<span>true</span><span>)
</span><span>12</span> <span>                {
</span><span>13</span>                     <span>if</span> (k &gt; (j - <span>2</span>) / <span>2</span>) <span>break</span><span>;  <span>//即：k &gt; ((j-1)-1)/2</span> <span>超出最后一个父节点的位置  
</span></span><span>14</span>                     <span>else</span>
<span>15</span> <span>                    {
</span><span>16</span>                         <span>int</span> temp =<span> k;
</span><span>17</span>                         k = ReSortMaxBranch(data, k, <span>2</span> * k + <span>1</span>, <span>2</span> * k + <span>2</span>, j - <span>1</span><span>);
</span><span>18</span>                         <span>if</span> (temp == k) <span>break</span><span>;
</span><span>19</span> <span>                    }
</span><span>20</span> <span>                }
</span><span>21</span> <span>            }
</span><span>22</span> <span>        }
</span><span>23</span> 
<span>24</span>         <span>public</span> <span>static</span> <span>void</span> BuildMaxHeapify(IList&lt;<span>int</span>&gt;<span> data)
</span><span>25</span> <span>        {
</span><span>26</span>             <span>for</span> (<span>int</span> i = data.Count / <span>2</span> - <span>1</span>; i &gt;= <span>0</span>; i--<span>)  <span>//(data.Count-1)-1)/2为数列最大父节点索引
</span></span><span>27</span> <span>            {
</span><span>28</span>                 <span>int</span> temp =<span> i;
</span><span>29</span>                 temp = ReSortMaxBranch(data, i, <span>2</span> * i + <span>1</span>, <span>2</span> * i + <span>2</span>, data.Count - <span>1</span><span>);
</span><span>30</span>                 <span>if</span> (temp !=<span> i)
</span><span>31</span> <span>                {
</span><span>32</span>                     <span>int</span> k =<span> i;
</span><span>33</span>                     <span>while</span> (k != temp &amp;&amp; temp &lt;= data.Count / <span>2</span> - <span>1</span><span>)
</span><span>34</span> <span>                    {
</span><span>35</span>                         k =<span> temp;
</span><span>36</span>                         temp = ReSortMaxBranch(data, temp, <span>2</span> * temp + <span>1</span>, <span>2</span> * temp + <span>2</span>, data.Count - <span>1</span><span>);
</span><span>37</span> <span>                    }
</span><span>38</span> <span>                }
</span><span>39</span> <span>            }
</span><span>40</span> <span>        }
</span><span>41</span> 
<span>42</span>         <span>public</span> <span>static</span> <span>int</span> ReSortMaxBranch(IList&lt;<span>int</span>&gt; data, <span>int</span> maxIndex, <span>int</span> left, <span>int</span> right, <span>int</span><span> lastIndex)
</span><span>43</span> <span>        {
</span><span>44</span>             <span>int</span><span> temp;
</span><span>45</span>             <span>if</span> (right &gt;<span> lastIndex)  <span>//父节点只有一个子节点
</span></span><span>46</span>                 temp =<span> left;
</span><span>47</span>             <span>else</span>
<span>48</span> <span>            {
</span><span>49</span>                 <span>if</span> (data[left] &gt;<span> data[right])
</span><span>50</span>                     temp =<span> left;
</span><span>51</span>                 <span>else</span> temp =<span> right;
</span><span>52</span> <span>            }
</span><span>53</span> 
<span>54</span>             <span>if</span> (data[maxIndex] &lt;<span> data[temp])
</span><span>55</span> <span>                Swap(data, maxIndex, temp);
</span><span>56</span>             <span>else</span> temp =<span> maxIndex;
</span><span>57</span>             <span>return</span><span> temp;
</span><span>58</span>         }

过程解析：BuildMaxHeapify为排序前构建的最大堆数列方法，主要内容为从最后一个父节点开始往前将每个三角组合

（即父节点与它的两个子节点）符合父节点值最大的规则。ReSortMaxBranch为将三角调整为父节点值最大，

并返回该值之前的索引，用来判断是否进行了交换，以及原来的父节点值交换到了什么位置。在HeapSort里首先

构建了最大堆数列，然后将根节点交换到末尾，根节点不是最大值了，在while语句中对最大堆数列进行调整。

插曲：自从看了Martin Fowler大师《重构》第三版，我发现我更不喜欢写注释了。每次都想着尽量让方法的名字更贴切，

即使会造成方法的名字很长很丑。这算不算曲解了大师的意思啊！？上面的代码注释都是写博客的时候现加的（源代码很干净的。汗!）。

希尔排序

希尔排序是插入排序的一种更高效的改进版本。

在前面介绍的插入排序，我们知道1.它对有序数列排序的效率是非常高的 2.要排序的数向前移动是一步步进行的导致插入排序效率低。

希尔排序正是利用第一点，改善第二点，达到更理想的效果。

原理：通过奇妙的步长，插入排序间隔步长的元素，随后逐渐缩短步长至1，实现数列的插入排序。维基入口

疑问：可以想象到排序间隔步长的数，会逐渐让数列变得有序，提升最后步长为1时标准插入排序的效率。在维基上看到这么

一句话“可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的”注意用词是‘可能’。我的疑问是

这是个正确的命题吗？如何证明呢？看维基上也是由果推因，说是如果不是这样，就不会排序那么快了。可这我感觉还是太牵强了，

哪位大哥发现相关资料，希望能分享出来，不胜感激。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> ShellSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span><span> temp;
</span><span> 4</span>             <span>for</span> (<span>int</span> gap = data.Count / <span>2</span>; gap &gt; <span>0</span>; gap /= <span>2</span><span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 <span>for</span> (<span>int</span> i = gap; i &lt; data.Count; i +=<span> gap)
</span><span> 7</span> <span>                {
</span><span> 8</span>                     temp =<span> data[i];
</span><span> 9</span>                     <span>for</span> (<span>int</span> j = i - gap; j &gt;= <span>0</span>; j -=<span> gap)
</span><span>10</span> <span>                    {
</span><span>11</span>                         <span>if</span> (data[j] &gt;<span> temp)
</span><span>12</span> <span>                        {
</span><span>13</span>                             data[j + gap] =<span> data[j];
</span><span>14</span>                             <span>if</span> (j == <span>0</span><span>)
</span><span>15</span> <span>                            {
</span><span>16</span>                                 data[j] =<span> temp;
</span><span>17</span>                                 <span>break</span><span>;
</span><span>18</span> <span>                            }
</span><span>19</span> <span>                        }
</span><span>20</span>                         <span>else</span>
<span>21</span> <span>                        {
</span><span>22</span>                             data[j + gap] =<span> temp;
</span><span>23</span>                             <span>break</span><span>;
</span><span>24</span> <span>                        }
</span><span>25</span> <span>                    }
</span><span>26</span> <span>                }
</span><span>27</span> <span>            }
</span><span>28</span>         }

过程解析：采用的步长是N/2，每次取半，直至1。循环内部就是标准的插入排序。

——————

修正：修正后希尔排序才是真正牛叉的希尔啊！感谢@390218462的提出

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> ShellSortCorrect(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span><span> temp;
</span><span> 4</span>             <span>for</span> (<span>int</span> gap = data.Count / <span>2</span>; gap &gt; <span>0</span>; gap /= <span>2</span><span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 <span>for</span> (<span>int</span> i = gap; i &lt; data.Count; <span>i++</span><span>)      // <span>i+ = gap 改为了 i++
</span></span><span> 7</span> <span>                {
</span><span> 8</span>                     temp =<span> data[i];
</span><span> 9</span>                     <span>for</span> (<span>int</span> j = i - gap; j &gt;= <span>0</span>; j -=<span> gap)
</span><span>10</span> <span>                    {
</span><span>11</span>                         <span>if</span> (data[j] &gt;<span> temp)
</span><span>12</span> <span>                        {
</span><span>13</span>                             data[j + gap] =<span> data[j];
</span><span>14</span>                             <span>if</span> (j == <span>0</span><span>)
</span><span>15</span> <span>                            {
</span><span>16</span>                                 data[j] =<span> temp;
</span><span>17</span>                                 <span>break</span><span>;
</span><span>18</span> <span>                            }
</span><span>19</span> <span>                        }
</span><span>20</span>                         <span>else</span>
<span>21</span> <span>                        {
</span><span>22</span>                             data[j + gap] =<span> temp;
</span><span>23</span>                             <span>break</span><span>;
</span><span>24</span> <span>                        }
</span><span>25</span> <span>                    }
</span><span>26</span> <span>                }
</span><span>27</span> <span>            }
</span><span>28</span>         }

——————

这里实现的貌似是最差的希尔排序。主要源于步长的选择。维基上有各种牛叉的“凌波微步”，极限在哪里，

喜欢挑战的同学可以去学习学习。看维基排序算法里六种排序的测试，希尔最快，比快速排序还快！！我没实现啊！

只是对于神奇的步长更充满了敬畏。

基数排序

基数排序是一种非比较型整数排序。

“非比较型”是什么意思呢？因为它内部使用的是桶排序，而桶排序是非比较型排序。

这里就要说说桶排序了。一个非常有意思的排序。

桶排序

原理：取一定数量（数列中的最大值）的编好序号的桶，将数列每个数放进编号为它的桶里，然后将不是空的桶依次倒出来，

就组成有序数列了。维基入口

好吧！聪明的人一眼就看出桶排序的破绽了。假设只有两个数1,10000，岂不是要一万个桶！？这确实是个问题啊！我也

没想出解决办法。我起初也以为桶排序就是一个通过牺牲空间来换取时间的排序算法，它不需要比较，所以是非比较型算法。

但看了有趣的演示的桶排序后，发现世界之大，你没有解决，不代表别人没解决，睿智的人总是很多。

1，9999的桶排序实现：new Int[2];总共有两个数，得出最大数9999的位数4，取10的4次幂即10000作为分母，

要排序的数（1或9999）作为分子，并乘以数列总数2，即1*2/10000,9999*2/10000得到各自的位置0,1，完成排序。

如果是1,10000进行排序的话，上面的做法就需要稍微加一些处理——发现最大数是10的n次幂，就将它作为分母，并

放在数列末尾就好了。

如果是9999,10000进行排序的话，那就需要二维数组了，两个都在位置1，位置0没数。这个时候就需要在放

入每个位置时采用其它排序（比如插入排序）办法对这个位置的多个数排序了。

为基数排序做个过渡，我这里实现了一个个位数桶排序

涉及到了当重复的数出现的处理。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> BucketSortOnlyUnitDigit(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span>[] indexCounter = <span>new</span> <span>int</span>[<span>10</span><span>];
</span><span> 4</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; data.Count; i++<span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 indexCounter[data[i]]++<span>;
</span><span> 7</span> <span>            }
</span><span> 8</span>             <span>int</span>[] indexBegin = <span>new</span> <span>int</span>[<span>10</span><span>];
</span><span> 9</span>             <span>for</span> (<span>int</span> i = <span>1</span>; i &lt; <span>10</span>; i++<span>)
</span><span>10</span> <span>            {
</span><span>11</span>                 indexBegin[i] = indexBegin[i-1]+<span> indexCounter[i-1];
</span><span>15</span> <span>            }
</span><span>16</span>             IList&lt;<span>int</span>&gt; tempList =<span> NewInstance(data, data.Count);
</span><span>17</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; data.Count; i++<span>)
</span><span>18</span> <span>            {
</span><span>19</span>                 <span>int</span> number =<span> data[i];
</span><span>20</span>                 tempList[indexBegin[number]++] =<span> data[i];
</span><span>21</span> <span>            }
</span><span>22</span>             data =<span> tempList;
</span><span>23</span>         }

过程解析：indexCounter进行对每个数出现的频率的统计。indexBegin存储每个数的起始索引。

比如 1 1 2，indexCounter统计到0个0,2个1,1个2。indexBegin计算出0,1,2的起始索引分别为

0,0,2。当1个1已取出排序，那索引将+1,变为0,1,2。这样就通过提前给重复的数空出位置，解决了

重复的数出现的问题。当然，你也可以考虑用二维数组来解决重复。

下面继续基数排序。

基数排序原理：将整数按位数切割成不同的数字，然后按每个位数分别比较。

取得最大数的位数，从低位开始，每个位上进行桶排序。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> IList&lt;<span>int</span>&gt; RadixSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span> max = data[<span>0</span><span>];
</span><span> 4</span>             <span>for</span> (<span>int</span> i = <span>1</span>; i &lt; data.Count; i++<span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 <span>if</span> (data[i] &gt;<span> max)
</span><span> 7</span>                     max =<span> data[i];
</span><span> 8</span> <span>            }
</span><span> 9</span>             <span>int</span> digit = <span>1</span><span>;
</span><span>10</span>             <span>while</span> (max / <span>10</span> != <span>0</span><span>)
</span><span>11</span> <span>            {
</span><span>12</span>                 digit++<span>;
</span><span>13</span>                 max /= <span>10</span><span>;
</span><span>14</span> <span>            }
</span><span>15</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; digit; i++<span>)
</span><span>16</span> <span>            {
</span><span>17</span>                 <span>int</span>[] indexCounter = <span>new</span> <span>int</span>[<span>10</span><span>];
</span><span>18</span>                 IList&lt;<span>int</span>&gt; tempList =<span> NewInstance(data, data.Count);
</span><span>19</span>                 <span>for</span> (<span>int</span> j = <span>0</span>; j &lt; data.Count; j++<span>)
</span><span>20</span> <span>                {
</span><span>21</span>                     <span>int</span> number = (data[j] % Convert.ToInt32(Math.Pow(<span>10</span>, i + <span>1</span>))) / Convert.ToInt32(Math.Pow(<span>10</span>, i));  <span>//</span><span>得出i+1位上的数</span>
<span>22</span>                     indexCounter[number]++<span>;
</span><span>23</span> <span>                }
</span><span>24</span>                 <span>int</span>[] indexBegin = <span>new</span> <span>int</span>[<span>10</span><span>];
</span><span>25</span>                 <span>for</span> (<span>int</span> k = <span>1</span>; k &lt; <span>10</span>; k++<span>)
</span><span>26</span> <span>                {
</span><span>27</span>                     indexBegin[k] = indexBegin[k - <span>1</span>] + indexCounter[k - <span>1</span><span>];
</span><span>28</span> <span>                }
</span><span>29</span>                 <span>for</span> (<span>int</span> k = <span>0</span>; k &lt; data.Count; k++<span>)
</span><span>30</span> <span>                {
</span><span>31</span>                     <span>int</span> number = (data[k] % Convert.ToInt32(Math.Pow(<span>10</span>, i + <span>1</span>))) / Convert.ToInt32(Math.Pow(<span>10</span><span>, i));
</span><span>32</span>                     tempList[indexBegin[number]++] =<span> data[k];
</span><span>33</span> <span>                }
</span><span>34</span>                 data =<span> tempList;
</span><span>35</span> <span>            }
</span><span>36</span>             <span>return</span><span> data;
</span><span>37</span>         }

过程解析：得出最大数的位数，从低位开始桶排序。我写的这个实现代码并不简洁，但逻辑更清晰。

后面测试的时候我们就会发现，按理来说这个实现也还行吧！但并不如想象的那么快！

循环的次数太多？（统计频率n次+9次计算+n次放到新的数组）*位数。

创建的新实例太多？(new int[10]两次+NewInstance is反射判断创建实例+new int[n])*位数

测试比较

添加随机数组，数组有序校验，微软Linq排序

代码如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>int</span>[] RandomSet(<span>int</span> length, <span>int</span><span> max)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span>[] result = <span>new</span> <span>int</span><span>[length];
</span><span> 4</span>             Random rand = <span>new</span><span> Random();
</span><span> 5</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; result.Length; i++<span>)
</span><span> 6</span> <span>            {
</span><span> 7</span>                 result[i] =<span> rand.Next(max);
</span><span> 8</span> <span>            }
</span><span> 9</span>             <span>return</span><span> result;
</span><span>10</span> <span>        }
</span><span>11</span> 
<span>12</span>         <span>public</span> <span>static</span> <span>bool</span> IsAscOrdered(IList&lt;<span>int</span>&gt;<span> data)
</span><span>13</span> <span>        {
</span><span>14</span>             <span>bool</span> flag = <span>true</span><span>;
</span><span>15</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; data.Count - <span>1</span>; i++<span>)
</span><span>16</span> <span>            {
</span><span>17</span>                 <span>if</span> (data[i] &gt; data[i + <span>1</span><span>])
</span><span>18</span>                     flag = <span>false</span><span>;
</span><span>19</span> <span>            }
</span><span>20</span>             <span>return</span><span> flag;
</span><span>21</span> <span>        }
</span><span>22</span> 
<span>23</span>         <span>public</span> <span>static</span> <span>void</span> TestMicrosoft(IList&lt;<span>int</span>&gt;<span> data)
</span><span>24</span> <span>        {
</span><span>25</span>             Stopwatch stopwatch = <span>new</span><span> Stopwatch();
</span><span>26</span> <span>            stopwatch.Start();
</span><span>27</span>             List&lt;<span>int</span>&gt; result = data.OrderBy(a =&gt;<span> a).ToList();
</span><span>28</span> <span>            stopwatch.Stop();
</span><span>29</span>             <span>string</span> methodName = <span>"</span><span>TestMicrosoft</span><span>"</span><span>;
</span><span>30</span>             <span>int</span> length =<span> methodName.Length;
</span><span>31</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; <span>40</span> - length; i++<span>)
</span><span>32</span> <span>            {
</span><span>33</span>                 methodName += <span>"</span> <span>"</span><span>;
</span><span>34</span> <span>            }
</span><span>35</span>             Console.WriteLine(methodName +
<span>36</span>                 <span>"</span><span>  IsAscOrdered:</span><span>"</span> + IsAscOrdered(result) + <span>"</span><span>  Time:</span><span>"</span> +<span> stopwatch.Elapsed.TotalSeconds);
</span><span>37</span> 
<span>38</span>         }

测试主体如下：

<span> 1</span>         <span>static</span> <span>void</span> Main(<span>string</span><span>[] args)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span>[] aa = RandomSet(<span>50000</span>, <span>99999</span><span>);
</span><span> 4</span>             <span>//</span><span>int[] aa = OrderedSet(5000);</span>
<span> 5</span>             Console.WriteLine(<span>"</span><span>Array Length:</span><span>"</span> +<span> aa.Length);
</span><span> 6</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)SelectSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span> 7</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)BubbleSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span> 8</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)BubbleSortImprovedWithFlag, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span> 9</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)BubbleCocktailSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>10</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)InsertSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>11</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)InsertSortImprovedWithBinarySearch, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>12</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)QuickSortStrict, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>13</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)QuickSortRelax, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>14</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)QuickSortRelaxImproved, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>15</span>             RunTheMethod((Func&lt;IList&lt;<span>int</span>&gt;, IList&lt;<span>int</span>&gt;&gt;)MergeSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>16</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)ShellSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>17</span>             RunTheMethod((Func&lt;IList&lt;<span>int</span>&gt;, IList&lt;<span>int</span>&gt;&gt;)RadixSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>18</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)HeapSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>19</span>             TestMicrosoft(aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>20</span> <span>            Console.Read();
</span><span>21</span> <span>        }
</span><span>22</span> 
<span>23</span>         <span>public</span> <span>static</span> <span>void</span> RunTheMethod(Func&lt;IList&lt;<span>int</span>&gt;, IList&lt;<span>int</span>&gt;&gt; method, IList&lt;<span>int</span>&gt;<span> data)
</span><span>24</span> <span>        {
</span><span>25</span>             Stopwatch stopwatch = <span>new</span><span> Stopwatch();
</span><span>26</span> <span>            stopwatch.Start();
</span><span>27</span>             IList&lt;<span>int</span>&gt; result =<span> method(data);
</span><span>28</span> <span>            stopwatch.Stop();
</span><span>29</span>             <span>string</span> methodName =<span> method.Method.Name;
</span><span>30</span>             <span>int</span> length =<span> methodName.Length;
</span><span>31</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; <span>40</span> - length; i++<span>)
</span><span>32</span> <span>            {
</span><span>33</span>                 methodName += <span>"</span> <span>"</span><span>;
</span><span>34</span> <span>            }
</span><span>35</span>             Console.WriteLine(methodName +
<span>36</span>                 <span>"</span><span>  IsAscOrdered:</span><span>"</span> + IsAscOrdered(result) + <span>"</span><span>  Time:</span><span>"</span> +<span> stopwatch.Elapsed.TotalSeconds);
</span><span>37</span> <span>        }
</span><span>38</span> 
<span>39</span>         <span>public</span> <span>static</span> <span>void</span> RunTheMethod(Action&lt;IList&lt;<span>int</span>&gt;&gt; method, IList&lt;<span>int</span>&gt;<span> data)
</span><span>40</span> <span>        {
</span><span>41</span>             Stopwatch stopwatch = <span>new</span><span> Stopwatch();
</span><span>42</span> <span>            stopwatch.Start();
</span><span>43</span> <span>            method(data);
</span><span>44</span> <span>            stopwatch.Stop();
</span><span>45</span>             <span>string</span> methodName =<span> method.Method.Name;
</span><span>46</span>             <span>int</span> length =<span> methodName.Length;
</span><span>47</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; <span>40</span> - length; i++<span>)
</span><span>48</span> <span>            {
</span><span>49</span>                 methodName += <span>"</span> <span>"</span><span>;
</span><span>50</span> <span>            }
</span><span>51</span>             Console.WriteLine(methodName +
<span>52</span>                 <span>"</span><span>  IsAscOrdered:</span><span>"</span> + IsAscOrdered(data) + <span>"</span><span>  Time:</span><span>"</span> +<span> stopwatch.Elapsed.TotalSeconds);
</span><span>53</span>         }

剩余代码折叠在此处

View Code

测试设备：win8(64位)，i7-3630QM,8G内存，vs2012

测试结果：

100000,50000,10000,5000,1000,100依次是：

结果分析：可以看出在大数组的时候，微软自带排序更接近快速排序。而当数组变小时，速度却没有明显提升，甚至变得更慢，

比如1000和100。可以推断出在数组足够小的时候，比较已经不是影响这个方法主要因素。而根据它对大数组的表现。我们可以

推断出它应该用的是快速排序。反编译验证下：

在System.Linq.EnumerableSorter下。有兴趣的同学可以去看下详细实现。

维基上也有个测试。硬件没我的好。时间是我测试结果时间的几百倍。有兴趣的同学可以比较下。

在上面的测试中，我们可以看到快速最快，归并其次，冒泡最慢（维基上是希尔最快，估计使用的是某种神奇的步长）。

在我这里，以前实现的希尔还不如二分查找优化版的快，修正后希尔快了相当多，上面测试的希尔排序是以前错误的实现。

修正后的实现测试效果请点击右侧导航到希尔排序查看。希尔排序是一种神奇又有潜力的算法。步长不好会很挫！

而基数排序却是比平均时间复杂度为o(nlogn)的堆排序，归并排序，快速排序还要慢的，虽然它的平均时间复杂度为o(n)。

冒泡标识优化版对随机数列结果优化不明显，鸡尾酒版优化可以看到，但也不是很厉害。

插入排序二分查找优化版优化比较明显。我优化的快速排序QuickSortRelaxImproved优化也不明显。

以上是随机数列的测试结果，最大值为99999。

而对于有序数列，这些方法表现又会如何呢？

我这里就不演示了。本文末尾会附上demo，大家可以自行测试。

有意思的是:

我在测试有序数列的时候，QuickSortStrict方法栈溢出了（stack overflow exception）。这个异常

是让我去stackoverflow搜寻答案吗？哈哈！我确信我的方法不是无限循环。跳过一堆链接。。。我是

在测试10000个数排序的时候发生的错误。我跟踪后发现大约在9400多次递归的时候，栈溢出。找啊找

终于找见了一个类似的问题。上面说如果一个递归9000多次而没有返回值，也会报栈溢出的。而这个方法

对于10000个有序数列，确实每次减少一个数地递归，次数会超过限制。

我的算法理论不怎么好，对于时间复杂度和空间复杂度，还有稳定度，搞得也不怎么清楚，只知道个大致的

意思。各位要笔试面试的朋友可以去维基百科这个表来了解学习。

总结

我觉得使用IList更贴近数列，更能展现基本的操作。所以我的实现中都没有将它强制转化为List

或者int[]来调用微软封装的方法。这样说来，题目说C#实现倒快有点名不副实了。不过这样却也方便了其它语言

朋友。比如将我这篇博文里的实现随便改改，就可以说是另一个语言版本的8种排序算法了。哈哈！在这里，

我想说下这次学习排序对我的意义：老久不怎么动脑了，突然动起来，磨磨唧唧地得出结果，最后倒也有点成就感！

在学习过程中，经常会脑子转不过弯，想不通的，只是走在路上或者睡觉前突然灵感一现，有点小惊喜的感觉！

这大概就是进步的特征吧！哈哈！这次写demo+写博客花费了不少时间，倒也收获颇多，尤其在我将8种

排序都实现之前，没进行过一次测试，全部实现完成后，测试时各种索引越界+无限循环+各种问题，没几个

能跑通的，到后来的几乎都没有问题，也算是锻炼了思维，找出错原因的能力。本篇是自我学习的一个总结，

要学习及锻炼的园友，还望一定自己实现一下，可以和我的比较一下，解除疑惑或者提出改进。

Demo源码

PS:我打算三月份去广州发展，主要会Asp.net mvc+jquery（不介意学习新的技术[除了webform]及语言[除了java]）。

CSharp排序算法小结

发表于 1899-11-30 更新于 2025-03-27 分类于 Lessons ，排序算法 Valine：

前言

算法这个东西其实在开发中很少用到，特别是web开发中，但是算法也很重要，因为任何的程序，任何的软件，都是由很多的算法和数据结构组成的。但是这不意味着算法对于每个软件设计人员的实际工作都是很重要的。每个项目特点和需求特殊也导致算法运用场景上不同。但是个人觉得算法运用的好的话会给自己在程序设计的时候提供比较好的思路。下面就对一些排序算法小结一下，就当做自己的一个笔记吧。

插入排序

1.简介

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

2.算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
1.从第一个元素开始，该元素可以认为已经被排序
2.取出下一个元素，在已经排序的元素序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一位置
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到该位置后
6.重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

3.使用插入排序为一列数字进行排序的过程

最差时间复杂度 $O(n^{2})$

最优时间复杂度 $O(n)$

平均时间复杂度 $O(n^{2})$

4.C#实现

    /// <summary>
    /// 插入排序 /// </summary>
    public class InsertionSorter
    { public void Sort(int\[\] list)
        { for (int i = 1; i < list.Length; ++i)
            { int t = list\[i\]; int j = i; while ((j > 0) && (list\[j - 1\] > t))
                {
                    list\[j\] \= list\[j - 1\]; \--j;
                }
                list\[j\] \= t;
            }

        }
    }

数组

int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };

希尔排序

1.简介

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

2.算法实现

原始的算法实现在最坏的情况下需要进行O(n2)的比较和交换。V. Pratt的书[1] 对算法进行了少量修改，可以使得性能提升至O(n log2 n)。这比最好的比较算法的O(n log n)要差一些。
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。
一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。

3.排序过程

最差时间复杂度根据步长串行的不同而不同。 $O(n\log^2 n)$

最优时间复杂度 O(n)

平均时间复杂度根据步长串行的不同而不同。

4.C#实现

    /// <summary>
    /// 希尔排序 /// </summary>
    public class ShellSorter
    { public void Sort(int\[\] list)
        { int inc; for (inc = 1; inc <= list.Length / 9; inc = 3 \* inc + 1) ; for (; inc > 0; inc /= 3)
            { for (int i = inc + 1; i <= list.Length; i += inc)
                { int t = list\[i - 1\]; int j = i; while ((j > inc) && (list\[j - inc - 1\] > t))
                    {
                        list\[j \- 1\] = list\[j - inc - 1\];
                        j \-= inc;
                    }
                    list\[j \- 1\] = t;
                }
            }
        }
    }

选择排序

1.简介

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

2.实现过程

最差时间复杂度 О(n²)

最优时间复杂度 О(n²)

平均时间复杂度 О(n²)

3.C#实现

    /// <summary>
    /// 选择排序 /// </summary>
    public class SelectionSorter
    { // public enum comp {COMP\_LESS,COMP\_EQUAL,COMP\_GRTR};
        private int min; // private int m=0;
        public void Sort(int\[\] list)
        { for (int i = 0; i < list.Length - 1; ++i)
            {
                min \= i; for (int j = i + 1; j < list.Length; ++j)
                { if (list\[j\] < list\[min\])
                        min \= j;
                } int t = list\[min\];
                list\[min\] \= list\[i\];
                list\[i\] \= t; // Console.WriteLine("{0}",list\[i\]);

}

        }
    }

冒泡排序

1.简介

冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序对n个项目需要O(n^{2})的比较次数，且可以原地排序。尽管这个算法是最简单了解和实作的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。
冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要O(n^{2})次交换，而插入排序只要最多O(n)交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行（O(n^{2})），而插入排序在这个例子只需要O(n)个运算。因此很多现代的算法教科书避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时，使用一个旗标来表示有无需要交换的可能，也有可能把最好的复杂度降低到O(n)。在这个情况，在已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序和比较大小反过来，也可以稍微地改进效率。有时候称为往返排序，因为算法会从数列的一端到另一端之间穿梭往返。

2.算法实现
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

3.实现过程

最差时间复杂度 $O(n^{2})$

最优时间复杂度 $O(n)$

平均时间复杂度 $O(n^{2})$

4.C#实现

   /// <summary>
    /// 冒泡排序 /// </summary>
    public class bubblesort
    { public void BubbleSort(int\[\] R)
        { int i, j, temp; //交换标志 
            bool exchange; for (i = 0; i < R.Length; i++) //最多做R.Length-1趟排序

{
exchange = false; //本趟排序开始前，交换标志应为假
for (j = R.Length - 2; j >= i; j–)
{ if (R[j + 1] < R[j])　//交换条件
{
temp = R[j + 1];
R[j + 1] = R[j];
R[j] = temp;
exchange = true; //发生了交换，故将交换标志置为真
}
} if (!exchange) //本趟排序未发生交换，提前终止算法
{ break;
}
}
}
}

CSharp设计模式(10)——组合模式（Composite Pattern）

发表于 1899-11-30 更新于 2025-03-27 分类于 Lessons ，设计模式 Valine：

一、引言

在软件开发过程中，我们经常会遇到处理简单对象和复合对象的情况，例如对操作系统中目录的处理就是这样的一个例子，因为目录可以包括单独的文件，也可以包括文件夹，文件夹又是由文件组成的，由于简单对象和复合对象在功能上区别，导致在操作过程中必须区分简单对象和复合对象，这样就会导致客户调用带来不必要的麻烦，然而作为客户，它们希望能够始终一致地对待简单对象和复合对象。然而组合模式就是解决这样的问题。下面让我们看看组合模式是怎样解决这个问题的。

二、组合模式的详细介绍

2.1 组合模式的定义

组合模式允许你将对象组合成树形结构来表现”部分-整体“的层次结构，使得客户以一致的方式处理单个对象以及对象的组合。下面我们用绘制的例子来详细介绍组合模式，图形可以由一些基本图形元素组成（如直线，圆等），也可以由一些复杂图形组成（由基本图形元素组合而成），为了使客户对基本图形和复杂图形的调用保持一致，我们使用组合模式来达到整个目的。

组合模式实现的最关键的地方是——简单对象和复合对象必须实现相同的接口。这就是组合模式能够将组合对象和简单对象进行一致处理的原因。

2.2 组合模式的实现

介绍完组合模式的定义之后，让我们以图形的例子来实现组合模式，具体代码如下：

// 通过一些简单图形以及一些复杂图形构建图形树来演示组合模式 // 客户端调用
class Client
{ static void Main(string[] args)
{
ComplexGraphics complexGraphics = new ComplexGraphics(“一个复杂图形和两条线段组成的复杂图形”);
complexGraphics.Add(new Line(“线段A”));
ComplexGraphics CompositeCG = new ComplexGraphics(“一个圆和一条线组成的复杂图形”);
CompositeCG.Add(new Circle(“圆”));
CompositeCG.Add(new Circle(“线段B”));
complexGraphics.Add(CompositeCG);
Line l = new Line(“线段C”);
complexGraphics.Add(l); // 显示复杂图形的画法
Console.WriteLine(“复杂图形的绘制如下：”);
Console.WriteLine(“-——————–”);
complexGraphics.Draw();
Console.WriteLine(“复杂图形绘制完成”);
Console.WriteLine(“-——————–”);
Console.WriteLine(); // 移除一个组件再显示复杂图形的画法
complexGraphics.Remove(l);
Console.WriteLine(“移除线段C后，复杂图形的绘制如下：”);
Console.WriteLine(“-——————–”);
complexGraphics.Draw();
Console.WriteLine(“复杂图形绘制完成”);
Console.WriteLine(“-——————–”);
Console.Read();
}
} ///

/// 图形抽象类， ///

public abstract class Graphics
{ public string Name { get; set; } public Graphics(string name)
{ this.Name = name;
} public abstract void Draw(); public abstract void Add(Graphics g); public abstract void Remove(Graphics g);
} ///

/// 简单图形类——线 ///

public class Line : Graphics
{ public Line(string name)
: base(name)
{ } // 重写父类抽象方法
public override void Draw()
{
Console.WriteLine(“画 “ + Name);
} // 因为简单图形在添加或移除其他图形，所以简单图形Add或Remove方法没有任何意义 // 如果客户端调用了简单图形的Add或Remove方法将会在运行时抛出异常 // 我们可以在客户端捕获该类移除并处理
public override void Add(Graphics g)
{ throw new Exception(“不能向简单图形Line添加其他图形”);
} public override void Remove(Graphics g)
{ throw new Exception(“不能向简单图形Line移除其他图形”);
}
} ///

/// 简单图形类——圆 ///

public class Circle : Graphics
{ public Circle(string name)
: base(name)
{ } // 重写父类抽象方法
public override void Draw()
{
Console.WriteLine(“画 “ + Name);
} public override void Add(Graphics g)
{ throw new Exception(“不能向简单图形Circle添加其他图形”);
} public override void Remove(Graphics g)
{ throw new Exception(“不能向简单图形Circle移除其他图形”);
}
} ///

/// 复杂图形，由一些简单图形组成,这里假设该复杂图形由一个圆两条线组成的复杂图形 ///

public class ComplexGraphics : Graphics
{ private List complexGraphicsList = new List(); public ComplexGraphics(string name)
: base(name)
{ } ///

/// 复杂图形的画法 ///

public override void Draw()
{ foreach (Graphics g in complexGraphicsList)
{
g.Draw();
}
} public override void Add(Graphics g)
{
complexGraphicsList.Add(g);
} public override void Remove(Graphics g)
{
complexGraphicsList.Remove(g);
}
}

复制代码

由于基本图形对象不存在Add和Remove方法，上面实现中直接通过抛出一个异常的方式来解决这样的问题的，但是我们想以一种更安全的方式来解决——因为基本图形根本不存在这样的方法，我们是不是可以移除这些方法呢？为了移除这些方法，我们就不得不修改Graphics接口，我们把管理子对象的方法声明放在复合图形对象里面，这样简单对象Line、Circle使用这些方法时在编译时就会出错，这样的一种实现方式我们称为安全式的组合模式，然而上面的实现方式称为透明式的组合模式，下面让我们看看安全式的组合模式又是怎样实现的，具体实现代码如下：

复制代码

/// 安全式的组合模式 /// 此方式实现的组合模式把管理子对象的方法声明在树枝构件ComplexGraphics类中 /// 这样如果叶子节点Line、Circle使用了Add或Remove方法时，就能在编译期间出现错误 /// 但这种方式虽然解决了透明式组合模式的问题，但是它使得叶子节点和树枝构件具有不一样的接口。 /// 所以这两种方式实现的组合模式各有优缺点，具体使用哪个，可以根据问题的实际情况而定
class Client
{ static void Main(string[] args)
{
ComplexGraphics complexGraphics = new ComplexGraphics(“一个复杂图形和两条线段组成的复杂图形”);
complexGraphics.Add(new Line(“线段A”));
ComplexGraphics CompositeCG = new ComplexGraphics(“一个圆和一条线组成的复杂图形”);
CompositeCG.Add(new Circle(“圆”));
CompositeCG.Add(new Circle(“线段B”));
complexGraphics.Add(CompositeCG);
Line l = new Line(“线段C”);
complexGraphics.Add(l); // 显示复杂图形的画法
Console.WriteLine(“复杂图形的绘制如下：”);
Console.WriteLine(“-——————–”);
complexGraphics.Draw();
Console.WriteLine(“复杂图形绘制完成”);
Console.WriteLine(“-——————–”);
Console.WriteLine(); // 移除一个组件再显示复杂图形的画法
complexGraphics.Remove(l);
Console.WriteLine(“移除线段C后，复杂图形的绘制如下：”);
Console.WriteLine(“-——————–”);
complexGraphics.Draw();
Console.WriteLine(“复杂图形绘制完成”);
Console.WriteLine(“-——————–”);
Console.Read();
}
} ///

/// 图形抽象类， ///

public abstract class Graphics
{ public string Name { get; set; } public Graphics(string name)
{ this.Name = name;
} public abstract void Draw(); // 移除了Add和Remove方法 // 把管理子对象的方法放到了ComplexGraphics类中进行管理 // 因为这些方法只在复杂图形中才有意义
} ///

/// 简单图形类——线 ///

public class Line : Graphics
{ public Line(string name)
: base(name)
{ } // 重写父类抽象方法
public override void Draw()
{
Console.WriteLine(“画 “ + Name);
}
} ///

/// 简单图形类——圆 ///

public class Circle : Graphics
{ public Circle(string name)
: base(name)
{ } // 重写父类抽象方法
public override void Draw()
{
Console.WriteLine(“画 “ + Name);
}
} ///

/// 复杂图形，由一些简单图形组成,这里假设该复杂图形由一个圆两条线组成的复杂图形 ///

public class ComplexGraphics : Graphics
{ private List complexGraphicsList = new List(); public ComplexGraphics(string name)
: base(name)
{ } ///

/// 复杂图形的画法 ///

public override void Draw()
{ foreach (Graphics g in complexGraphicsList)
{
g.Draw();
}
} public void Add(Graphics g)
{
complexGraphicsList.Add(g);
} public void Remove(Graphics g)
{
complexGraphicsList.Remove(g);
}
}

复制代码

2.3 组合模式的类图

看完了上面两者方式的实现之后，让我们具体看看组合模式的类图来理清楚组合模式中类之间的关系。

透明式的组合模式类图：

安全式组合模式的类图：

组合模式中涉及到三个角色：

抽象构件（Component）角色：这是一个抽象角色，上面实现中Graphics充当这个角色，它给参加组合的对象定义出了公共的接口及默认行为，可以用来管理所有的子对象（在透明式的组合模式是这样的）。在安全式的组合模式里，构件角色并不定义出管理子对象的方法，这一定义由树枝结构对象给出。
树叶构件（Leaf）角色：树叶对象时没有下级子对象的对象，上面实现中Line和Circle充当这个角色，定义出参加组合的原始对象的行为
树枝构件（Composite）角色：代表参加组合的有下级子对象的对象，上面实现中ComplexGraphics充当这个角色，树枝对象给出所有管理子对象的方法实现，如Add、Remove等。

三、组合模式的优缺点

优点：

组合模式使得客户端代码可以一致地处理对象和对象容器，无需关系处理的单个对象，还是组合的对象容器。
将”客户代码与复杂的对象容器结构“解耦。
可以更容易地往组合对象中加入新的构件。

缺点：使得设计更加复杂。客户端需要花更多时间理清类之间的层次关系。（这个是几乎所有设计模式所面临的问题）。

注意的问题：

有时候系统需要遍历一个树枝结构的子构件很多次，这时候可以考虑把遍历子构件的结构存储在父构件里面作为缓存。
客户端尽量不要直接调用树叶类中的方法（在我上面实现就是这样的，创建的是一个树枝的具体对象，应该使用Graphics complexGraphics = new ComplexGraphics(“一个复杂图形和两条线段组成的复杂图形”);），而是借用其父类（Graphics）的多态性完成调用，这样可以增加代码的复用性。

四、组合模式的使用场景

在以下情况下应该考虑使用组合模式：

需要表示一个对象整体或部分的层次结构。
希望用户忽略组合对象与单个对象的不同，用户将统一地使用组合结构中的所有对象。

五、组合模式在.NET中的应用

组合模式在.NET 中最典型的应用就是应用与WinForms和Web的开发中，在.NET类库中，都为这两个平台提供了很多现有的控件，然而System.Windows.Forms.dll中System.Windows.Forms.Control类就应用了组合模式，因为控件包括Label、TextBox等这样的简单控件，同时也包括GroupBox、DataGrid这样复合的控件，每个控件都需要调用OnPaint方法来进行控件显示，为了表示这种对象之间整体与部分的层次结构，微软把Control类的实现应用了组合模式（确切地说应用了透明式的组合模式）。

六、总结

到这里组合模式的介绍就结束了，组合模式解耦了客户程序与复杂元素内部结构，从而使客户程序可以向处理简单元素一样来处理复杂元素。

本文中所有源码：设计模式之组合模式

CSharp设计模式(12)——享元模式（Flyweight Pattern）

发表于 1899-11-30 更新于 2025-03-27 分类于 Lessons ，设计模式 Valine：

一、引言

在软件开发过程，如果我们需要重复使用某个对象的时候，如果我们重复地使用new创建这个对象的话，这样我们在内存就需要多次地去申请内存空间了，这样可能会出现内存使用越来越多的情况，这样的问题是非常严重，然而享元模式可以解决这个问题，下面具体看看享元模式是如何去解决这个问题的。

二、享元模式的详细介绍

在前面说了，享元模式可以解决上面的问题了，在介绍享元模式之前，让我们先要分析下如果去解决上面那个问题，上面的问题就是重复创建了同一个对象，如果让我们去解决这个问题肯定会这样想：“既然都是同一个对象，能不能只创建一个对象，然后下次需要创建这个对象的时候，让它直接用已经创建好了的对象就好了”，也就是说——让一个对象共享。不错，这个也是享元模式的实现精髓所在。

2.1 定义

介绍完享元模式的精髓之后，让我们具体看看享元模式的正式定义：

享元模式——运用共享技术有效地支持大量细粒度的对象。享元模式可以避免大量相似类的开销，在软件开发中如果需要生成大量细粒度的类实例来表示数据，如果这些实例除了几个参数外基本上都是相同的，这时候就可以使用享元模式来大幅度减少需要实例化类的数量。如果能把这些参数（指的这些类实例不同的参数）移动类实例外面，在方法调用时将他们传递进来，这样就可以通过共享大幅度地减少单个实例的数目。（这个也是享元模式的实现要领）,然而我们把类实例外面的参数称为享元对象的外部状态，把在享元对象内部定义称为内部状态。具体享元对象的内部状态与外部状态的定义为：

内部状态：在享元对象的内部并且不会随着环境的改变而改变的共享部分

外部状态：随环境改变而改变的，不可以共享的状态。

2.2 享元模式实现

分析完享元模式的实现思路之后，相信大家实现享元模式肯定没什么问题了，下面以一个实际的应用来实现下享元模式。这个例子是：一个文本编辑器中会出现很多字面，使用享元模式去实现这个文本编辑器的话，会把每个字面做成一个享元对象。享元对象的内部状态就是这个字面，而字母在文本中的位置和字体风格等其他信息就是它的外部状态。下面就以这个例子来实现下享元模式，具体实现代码如下：

///

/// 客户端调用 ///

class Client
{ static void Main(string[] args)
{ // 定义外部状态，例如字母的位置等信息
int externalstate = 10; // 初始化享元工厂
FlyweightFactory factory = new FlyweightFactory(); // 判断是否已经创建了字母A，如果已经创建就直接使用创建的对象A
Flyweight fa = factory.GetFlyweight(“A”); if (fa != null)
{ // 把外部状态作为享元对象的方法调用参数
fa.Operation(–externalstate);
} // 判断是否已经创建了字母B
Flyweight fb = factory.GetFlyweight(“B”); if (fb != null)
{
fb.Operation(--externalstate);
} // 判断是否已经创建了字母C
Flyweight fc = factory.GetFlyweight(“C”); if (fc != null)
{
fc.Operation(--externalstate);
} // 判断是否已经创建了字母D
Flyweight fd= factory.GetFlyweight(“D”); if (fd != null)
{
fd.Operation(--externalstate);
} else {
Console.WriteLine(“驻留池中不存在字符串D”); // 这时候就需要创建一个对象并放入驻留池中
ConcreteFlyweight d = new ConcreteFlyweight(“D”);
factory.flyweights.Add(“D”, d);
}

        Console.Read();
    }
} /// <summary>
/// 享元工厂，负责创建和管理享元对象 /// </summary>
public class FlyweightFactory
{ // 最好使用泛型Dictionary<string,Flyweighy> //public Dictionary<string, Flyweight> flyweights = new Dictionary<string, Flyweight>();
    public Hashtable flyweights = new Hashtable(); public FlyweightFactory()
    {
        flyweights.Add("A", new ConcreteFlyweight("A"));
        flyweights.Add("B", new ConcreteFlyweight("B"));
        flyweights.Add("C", new ConcreteFlyweight("C"));
    } public Flyweight GetFlyweight(string key)
    {

// 更好的实现如下
//Flyweight flyweight = flyweights[key] as Flyweight;
//if (flyweight == null)
//{
// Console.WriteLine(“驻留池中不存在字符串” + key);
// flyweight = new ConcreteFlyweight(key);
//}
//return flyweight;

return flyweights[key] as Flyweight;
}
} ///

/// 抽象享元类，提供具体享元类具有的方法 ///

public abstract class Flyweight
{ public abstract void Operation(int extrinsicstate);
} // 具体的享元对象，这样我们不把每个字母设计成一个单独的类了，而是作为把共享的字母作为享元对象的内部状态
public class ConcreteFlyweight : Flyweight
{ // 内部状态
private string intrinsicstate ; // 构造函数
public ConcreteFlyweight(string innerState)
{ this.intrinsicstate = innerState;
} ///

/// 享元类的实例方法 ///

/// 外部状态
public override void Operation(int extrinsicstate)
{
Console.WriteLine(“具体实现类: intrinsicstate {0}, extrinsicstate {1}”, intrinsicstate, extrinsicstate);
}
}

在享元模式的实现中，我们没有像之前一样，把一个细粒度的类实例设计成一个单独的类，而是把它作为共享对象的内部状态放在共享类的内部定义，具体的解释注释中都有了，大家可以参考注释去进一步理解享元模式。

2.3 享元模式的类图

看完享元模式的实现之后，为了帮助大家理清楚享元模式中各类之间的关系，下面给出上面实现代码中的类图，如下所示：

（摘自http://www.cnblogs.com/zhenyulu/articles/55793.html）

在上图中，涉及的角色如下几种角色：

抽象享元角色（Flyweight）:此角色是所有的具体享元类的基类，为这些类规定出需要实现的公共接口。那些需要外部状态的操作可以通过调用方法以参数形式传入。

具体享元角色（ConcreteFlyweight）：实现抽象享元角色所规定的接口。如果有内部状态的话，可以在类内部定义。

享元工厂角色（FlyweightFactory）：本角色复杂创建和管理享元角色。本角色必须保证享元对象可以被系统适当地共享，当一个客户端对象调用一个享元对象的时候，享元工厂角色检查系统中是否已经有一个符合要求的享元对象，如果已经存在，享元工厂角色就提供已存在的享元对象，如果系统中没有一个符合的享元对象的话，享元工厂角色就应当创建一个合适的享元对象。

客户端角色（Client）：本角色需要存储所有享元对象的外部状态。

注：上面的实现只是单纯的享元模式，同时还有复合的享元模式，由于复合享元模式较复杂，这里就不给出实现了。

三、享元模式的优缺点

分析完享元模式的实现之后，让我们继续分析下享元模式的优缺点：

优点：

降低了系统中对象的数量，从而降低了系统中细粒度对象给内存带来的压力。

缺点：

为了使对象可以共享，需要将一些状态外部化，这使得程序的逻辑更复杂，使系统复杂化。
享元模式将享元对象的状态外部化，而读取外部状态使得运行时间稍微变长。

四、使用场景

在下面所有条件都满足时，可以考虑使用享元模式：

一个系统中有大量的对象；
这些对象耗费大量的内存；
这些对象中的状态大部分都可以被外部化
这些对象可以按照内部状态分成很多的组，当把外部对象从对象中剔除时，每一个组都可以仅用一个对象代替
软件系统不依赖这些对象的身份，

满足上面的条件的系统可以使用享元模式。但是使用享元模式需要额外维护一个记录子系统已有的所有享元的表，而这也需要耗费资源，所以，应当在有足够多的享元实例可共享时才值得使用享元模式。

注：在.NET类库中，string类的实现就使用了享元模式，更多内容可以参考字符串驻留池的介绍，同时也可以参考这个博文深入理解.NET中string类的设计——http://www.cnblogs.com/artech/archive/2010/11/25/internedstring.html

五、总结

到这里，享元模式的介绍就结束了，享元模式主要用来解决由于大量的细粒度对象所造成的内存开销的问题，它在实际的开发中并不常用，可以作为底层的提升性能的一种手段。

CSharp设计模式(14)——模板方法模式（Template Method）

发表于 1899-11-30 更新于 2025-03-27 分类于 Lessons ，设计模式 Valine：

一、引言

提到模板，大家肯定不免想到生活中的“简历模板”、“论文模板”、“Word中模版文件”等，在现实生活中，模板的概念就是——有一个规定的格式，然后每个人都可以根据自己的需求或情况去更新它，例如简历模板，下载下来的简历模板的格式都是相同的，然而我们下载下来简历模板之后我们可以根据自己的情况填充不同的内容要完成属于自己的简历。在设计模式中，模板方法模式中模板和生活中模板概念非常类似，下面让我们就详细介绍模板方法的定义，大家可以根据生活中模板的概念来理解模板方法的定义。

二、模板方法模式详细介绍

2.1 模板方法模式的定义

模板方法模式——在一个抽象类中定义一个操作中的算法骨架（对应于生活中的大家下载的模板），而将一些步骤延迟到子类中去实现（对应于我们根据自己的情况向模板填充内容）。模板方法使得子类可以不改变一个算法的结构前提下，重新定义算法的某些特定步骤，模板方法模式把不变行为搬到超类中，从而去除了子类中的重复代码。

2.2 模板方法模式的实现

理解了模板方法的定义之后，自然实现模板方法也不是什么难事了，下面以生活中炒蔬菜为例来实现下模板方法模式。在现实生活中，做蔬菜的步骤都大致相同，如果我们针对每种蔬菜类定义一个烧的方法，这样在每个类中都有很多相同的代码，为了解决这个问题，我们一般的思路肯定是把相同的部分抽象出来到抽象类中去定义，具体子类来实现具体的不同部分，这个思路也正式模板方法的实现精髓所在，具体实现代码如下：

// 客户端调用
class Client
{ static void Main(string[] args)
{ // 创建一个菠菜实例并调用模板方法
Spinach spinach = new Spinach();
spinach.CookVegetabel();
Console.Read();
}
} public abstract class Vegetabel
{ // 模板方法，不要把模版方法定义为Virtual或abstract方法，避免被子类重写，防止更改流程的执行顺序
public void CookVegetabel()
{
Console.WriteLine(“抄蔬菜的一般做法”); this.pourOil(); this.HeatOil(); this.pourVegetable(); this.stir_fry();
} // 第一步倒油
public void pourOil()
{
Console.WriteLine(“倒油”);
} // 把油烧热
public void HeatOil()
{
Console.WriteLine(“把油烧热”);
} // 油热了之后倒蔬菜下去，具体哪种蔬菜由子类决定
public abstract void pourVegetable(); // 开发翻炒蔬菜
public void stir_fry()
{
Console.WriteLine(“翻炒”);
}
} // 菠菜
public class Spinach : Vegetabel
{ public override void pourVegetable()
{
Console.WriteLine(“倒菠菜进锅中”);
}
} // 大白菜
public class ChineseCabbage : Vegetabel
{ public override void pourVegetable()
{
Console.WriteLine(“倒大白菜进锅中”);
}
}

在上面的实现中，具体子类中重写了导入蔬菜种类的方法，因为这个真是烧菜方法中不同的地方，所以由具体子类去实现它。

2.3 模板方法模式的类图

实现完模板方法模式之后，让我们看看模板方法的类图结构，以理清该模式中类之间的关系，具体类图如下：

模板方法模式中涉及了两个角色：

抽象模板角色（Vegetable扮演这个角色）：定义了一个或多个抽象操作，以便让子类实现，这些抽象操作称为基本操作。
具体模板角色（ChineseCabbage和Spinach扮演这个角色）：实现父类所定义的一个或多个抽象方法。

三、模板方法模式的优缺点

下面让我们继续分析下模板方法的优缺点。

优点：

实现了代码复用
能够灵活应对子步骤的变化，符合开放-封闭原则

缺点：因为引入了一个抽象类，如果具体实现过多的话，需要用户或开发人员需要花更多的时间去理清类之间的关系。

附：在.NET中模板方法的应用也很多，例如我们在开发自定义的Web控件或WinForm控件时，我们只需要重写某个控件的部分方法。

四、总结

到这里，模板方法的介绍就结束了，模板方法模式在抽象类中定义了算法的实现步骤，将这些步骤的实现延迟到具体子类中去实现，从而使所有子类复用了父类的代码，所以模板方法模式是基于继承的一种实现代码复用的技术。

CSharp设计模式(16)——迭代器模式（Iterator Pattern）

发表于 1899-11-30 更新于 2025-03-27 分类于 Lessons ，设计模式 Valine：

　　在上篇博文中分享了我对命令模式的理解，命令模式主要是把行为进行抽象成命令，使得请求者的行为和接受者的行为形成低耦合。在一章中，将介绍一下迭代器模式。下面废话不多说了，直接进入本博文的主题。

　　迭代器是针对集合对象而生的，对于集合对象而言，必然涉及到集合元素的添加删除操作，同时也肯定支持遍历集合元素的操作，我们此时可以把遍历操作也放在集合对象中，但这样的话，集合对象就承担太多的责任了，面向对象设计原则中有一条是单一职责原则，所以我们要尽可能地分离这些职责，用不同的类去承担不同的职责。迭代器模式就是用迭代器类来承担遍历集合元素的职责。

2.1 迭代器模式的定义

　　迭代器模式提供了一种方法顺序访问一个聚合对象（理解为集合对象）中各个元素，而又无需暴露该对象的内部表示，这样既可以做到不暴露集合的内部结构，又可让外部代码透明地访问集合内部的数据。

2.2 迭代器模式的结构

　　既然，迭代器模式承担了遍历集合对象的职责，则该模式自然存在2个类，一个是聚合类，一个是迭代器类。在面向对象涉及原则中还有一条是针对接口编程，所以，在迭代器模式中，抽象了2个接口，一个是聚合接口，另一个是迭代器接口，这样迭代器模式中就四个角色了，具体的类图如下所示：

　　从上图可以看出，迭代器模式由以下角色组成：

迭代器角色（Iterator）：迭代器角色负责定义访问和遍历元素的接口
具体迭代器角色（Concrete Iteraror）：具体迭代器角色实现了迭代器接口，并需要记录遍历中的当前位置。
聚合角色（Aggregate）：聚合角色负责定义获得迭代器角色的接口
具体聚合角色（Concrete Aggregate）：具体聚合角色实现聚合角色接口。

2.3 迭代器模式的实现

　　介绍完迭代器模式之后，下面就具体看看迭代器模式的实现，具体实现代码如下：

1 // 抽象聚合类
2 public interface IListCollection 3 {
4 Iterator GetIterator();
5 }
6
7 // 迭代器抽象类
8 public interface Iterator 9 {
10 bool MoveNext(); 11 Object GetCurrent();
12 void Next(); 13 void Reset(); 14 }
15
16 // 具体聚合类
17 public class ConcreteList : IListCollection 18 {
19 int[] collection;
20 public ConcreteList() 21 {
22 collection = new int[] { 2, 4, 6, 8 }; 23 }
24
25 public Iterator GetIterator() 26 {
27 return new ConcreteIterator(this);
28 }
29
30 public int Length 31 {
32 get { return collection.Length; } 33 }
34
35 public int GetElement(int index) 36 {
37 return collection[index]; 38 }
39 }
40
41 // 具体迭代器类
42 public class ConcreteIterator : Iterator 43 {
44 // 迭代器要集合对象进行遍历操作，自然就需要引用集合对象
45 private ConcreteList _list; 46 private int _index; 47
48 public ConcreteIterator(ConcreteList list) 49 {
50 _list = list; 51 _index = 0;
52 }
53
54
55 public bool MoveNext() 56 {
57 if (_index < _list.Length) 58 {
59 return true;
60 }
61 return false;
62 }
63
64 public Object GetCurrent() 65 {
66 return _list.GetElement(_index); 67 }
68
69 public void Reset() 70 {
71 _index = 0;
72 }
73
74 public void Next() 75 {
76 if (_index < _list.Length) 77 {
78 _index++;
79 }
80
81 }
82 }
83
84 // 客户端
85 class Program 86 {
87 static void Main(string[] args)
88 {
89 Iterator iterator;
90 IListCollection list = new ConcreteList(); 91 iterator = list.GetIterator(); 92
93 while (iterator.MoveNext()) 94 {
95 int i = (int)iterator.GetCurrent();
96 Console.WriteLine(i.ToString());
97 iterator.Next();
98 }
99
100 Console.Read(); 101 } 102 }

自然，上面代码的运行结果也是对集合每个元素的输出，具体运行结果如下图所示：

　　在.NET下，迭代器模式中的聚集接口和迭代器接口都已经存在了，其中IEnumerator接口扮演的就是迭代器角色，IEnumberable接口则扮演的就是抽象聚集的角色，只有一个GetEnumerator()方法，关于这两个接口的定义可以自行参考MSDN。在.NET 1.0中，.NET 类库中很多集合都已经实现了迭代器模式，大家可以用反编译工具Reflector来查看下mscorlib程序集下的System.Collections命名空间下的类，这里给出ArrayList的定义代码，具体实现代码可以自行用反编译工具查看，具体代码如下所示：

1 public class ArrayList : IList, ICollection, IEnumerable, ICloneable 2 {
3 // Fields
4 private const int _defaultCapacity = 4;
5 private object[] _items;
6 private int _size; 7 [NonSerialized]
8 private object _syncRoot; 9 private int _version; 10 private static readonly object[] emptyArray; 11
12 public virtual IEnumerator GetEnumerator(); 13 public virtual IEnumerator GetEnumerator(int index, int count); 14
15 // Properties
16 public virtual int Capacity { get; set; } 17 public virtual int Count { get; } 18 …………..// 更多代码请自行用反编译工具Reflector查看
19 }

　　通过查看源码你可以发现，ArrayList中迭代器的实现与我们前面给出的示例代码非常相似。然而，在.NET 2.0中，由于有了yield return关键字，实现迭代器模式就更简单了，关于迭代器的更多内容可以参考我的这篇博文。

　　在下面的情况下可以考虑使用迭代器模式：

系统需要访问一个聚合对象的内容而无需暴露它的内部表示。
系统需要支持对聚合对象的多种遍历。
系统需要为不同的聚合结构提供一个统一的接口。

　　由于迭代器承担了遍历集合的职责，从而有以下的优点：

迭代器模式使得访问一个聚合对象的内容而无需暴露它的内部表示，即迭代抽象。
迭代器模式为遍历不同的集合结构提供了一个统一的接口，从而支持同样的算法在不同的集合结构上进行操作

　　迭代器模式存在的缺陷：

迭代器模式在遍历的同时更改迭代器所在的集合结构会导致出现异常。所以使用foreach语句只能在对集合进行遍历，不能在遍历的同时更改集合中的元素。

　　到这里，本博文的内容就介绍结束了，迭代器模式就是抽象一个迭代器类来分离了集合对象的遍历行为，这样既可以做到不暴露集合的内部结构，又可让外部代码透明地访问集合内部的数据。在一篇博文中将为大家介绍观察者模式。

CSharp设计模式(17)——观察者模式（Observer Pattern）

发表于 1899-11-30 更新于 2025-03-27 分类于 Lessons ，设计模式 Valine：

　　在现实生活中，处处可见观察者模式，例如，微信中的订阅号，订阅博客和QQ微博中关注好友，这些都属于观察者模式的应用。在这一章将分享我对观察者模式的理解，废话不多说了，直接进入今天的主题。

2.1 观察者模式的定义

　　从生活中的例子可以看出，只要对订阅号进行关注的客户端，如果订阅号有什么更新，就会直接推送给订阅了的用户。从中，我们就可以得出观察者模式的定义。

　　观察者模式定义了一种一对多的依赖关系，让多个观察者对象同时监听某一个主题对象，这个主题对象在状态发生变化时，会通知所有观察者对象，使它们能够自动更新自己的行为。

2.2 观察者模式的结构

　　从上面观察者模式的定义和生活中的例子，很容易知道，观察者模式中首先会存在两个对象，一个是观察者对象，另一个就是主题对象，然而，根据面向接口编程的原则，则自然就有抽象主题角色和抽象观察者角色。理清楚了观察者模式中涉及的角色后，接下来就要理清他们之间的关联了，要想主题对象状态发生改变时，能通知到所有观察者角色，则自然主题角色必须所有观察者的引用，这样才能在自己状态改变时，通知到所有观察者。有了上面的分析，下面观察者的结构图也就很容易理解了。具体结构图如下所示：

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　图观察者模式结构图

　　可以看出，在观察者模式的结构图有以下角色：

抽象主题角色（Subject）：抽象主题把所有观察者对象的引用保存在一个列表中，并提供增加和删除观察者对象的操作，抽象主题角色又叫做抽象被观察者角色，一般由抽象类或接口实现。
抽象观察者角色（Observer）：为所有具体观察者定义一个接口，在得到主题通知时更新自己，一般由抽象类或接口实现。
具体主题角色（ConcreteSubject）：实现抽象主题接口，具体主题角色又叫做具体被观察者角色。
具体观察者角色（ConcreteObserver）：实现抽象观察者角色所要求的接口，以便使自身状态与主题的状态相协调。

2.3 观察者模式的实现

　　下面以微信订阅号的例子来说明观察者模式的实现。现在要实现监控腾讯游戏订阅号的状态的变化。这里一开始不采用观察者模式来实现，而通过一步步重构的方式，最终重构为观察者模式。因为一开始拿到需求，自然想到有两个类，一个是腾讯游戏订阅号类，另一个是订阅者类。订阅号类中必须引用一个订阅者对象，这样才能在订阅号状态改变时，调用这个订阅者对象的方法来通知到订阅者对象。有了这个分析，自然实现的代码如下所示：

1 // 腾讯游戏订阅号类
2 public class TenxunGame 3 {
4 // 订阅者对象
5 public Subscriber Subscriber {get;set;}
6
7 public String Symbol {get; set;}
8
9 public string Info {get ;set;} 10
11 public void Update() 12 { 13 if (Subscriber != null) 14 { 15 // 调用订阅者对象来通知订阅者
16 Subscriber.ReceiveAndPrintData(this); 17 } 18 } 19
20 } 21
22 // 订阅者类
23 public class Subscriber 24 { 25 public string Name { get; set; } 26 public Subscriber(string name) 27 { 28 this.Name = name; 29 } 30
31 public void ReceiveAndPrintData(TenxunGame txGame) 32 { 33 Console.WriteLine(“Notified {0} of {1}’s” + “ Info is: {2}”, Name, txGame.Symbol, txGame.Info); 34 } 35 } 36
37 // 客户端测试
38 class Program 39 { 40 static void Main(string[] args) 41 { 42 // 实例化订阅者和订阅号对象
43 Subscriber LearningHardSub = new Subscriber(“LearningHard”); 44 TenxunGame txGame = new TenxunGame(); 45
46 txGame.Subscriber = LearningHardSub; 47 txGame.Symbol = “TenXun Game”; 48 txGame.Info = “Have a new game published ….”; 49
50 txGame.Update(); 51
52 Console.ReadLine(); 53 } 54 }

　　上面代码确实实现了监控订阅号的任务。但这里的实现存在下面几个问题：

TenxunGame类和Subscriber类之间形成了一种双向依赖关系，即TenxunGame调用了Subscriber的ReceiveAndPrintData方法，而Subscriber调用了TenxunGame类的属性。这样的实现，如果有其中一个类变化将引起另一个类的改变。
当出现一个新的订阅者时，此时不得不修改TenxunGame代码，即添加另一个订阅者的引用和在Update方法中调用另一个订阅者的方法。

　　上面的设计违背了“开放——封闭”原则，显然，这不是我们想要的。对此我们要做进一步的抽象，既然这里变化的部分是新订阅者的出现，这样我们可以对订阅者抽象出一个接口，用它来取消TenxunGame类与具体的订阅者之间的依赖，做这样一步改进，确实可以解决TenxunGame类与具体订阅者之间的依赖，使其依赖与接口，从而形成弱引用关系，但还是不能解决出现一个订阅者不得不修改TenxunGame代码的问题。对此，我们可以做这样的思考——订阅号存在多个订阅者，我们可以采用一个列表来保存所有的订阅者对象，在订阅号内部再添加对该列表的操作，这样不就解决了出现新订阅者的问题了嘛。并且订阅号也属于变化的部分，所以，我们可以采用相同的方式对订阅号进行抽象，抽象出一个抽象的订阅号类，这样也就可以完美解决上面代码存在的问题了，具体的实现代码为：

1 // 订阅号抽象类
2 public abstract class TenXun 3 {
4 // 保存订阅者列表
5 private List observers = new List();
6
7 public string Symbol { get; set; }
8 public string Info { get; set; }
9 public TenXun(string symbol, string info) 10 { 11 this.Symbol = symbol; 12 this.Info = info; 13 } 14
15 #region 新增对订阅号列表的维护操作
16 public void AddObserver(IObserver ob) 17 { 18 observers.Add(ob); 19 } 20 public void RemoveObserver(IObserver ob) 21 { 22 observers.Remove(ob); 23 } 24 #endregion
25
26 public void Update() 27 { 28 // 遍历订阅者列表进行通知
29 foreach (IObserver ob in observers) 30 { 31 if (ob != null) 32 { 33 ob.ReceiveAndPrint(this); 34 } 35 } 36 } 37 } 38
39 // 具体订阅号类
40 public class TenXunGame : TenXun 41 { 42 public TenXunGame(string symbol, string info) 43 : base(symbol, info) 44 { 45 } 46 } 47
48 // 订阅者接口
49 public interface IObserver 50 { 51 void ReceiveAndPrint(TenXun tenxun); 52 } 53
54 // 具体的订阅者类
55 public class Subscriber : IObserver 56 { 57 public string Name { get; set; } 58 public Subscriber(string name) 59 { 60 this.Name = name; 61 } 62
63 public void ReceiveAndPrint(TenXun tenxun) 64 { 65 Console.WriteLine(“Notified {0} of {1}’s” + “ Info is: {2}”, Name, tenxun.Symbol, tenxun.Info); 66 } 67 } 68
69 // 客户端测试
70 class Program 71 { 72 static void Main(string[] args) 73 { 74 TenXun tenXun = new TenXunGame(“TenXun Game”, “Have a new game published ….”); 75
76 // 添加订阅者
77 tenXun.AddObserver(new Subscriber(“Learning Hard”)); 78 tenXun.AddObserver(new Subscriber(“Tom”)); 79
80 tenXun.Update(); 81
82 Console.ReadLine(); 83 } 84 }

　　上面代码是我们进行重构后的实现，重构后的代码实现类图如下所示：

　　从上图可以发现，这样的实现就是观察者模式的实现。这样，在任何时候，只要调用了TenXun类的Update方法，它就会通知所有的观察者对象，同时，可以看到，观察者模式，取消了直接依赖，变为间接依赖，这样大大提供了系统的可维护性和可扩展性。这里并不是直接给出观察者模式的实现，而是通过一步步重构的方式来引出观察者模式的实现，相信通过这个方式，大家可以更深刻地理解观察者模式所解决的问题和带来的好处。

　　在.NET中，我们可以使用委托与事件来简化观察者模式的实现，上面的例子用事件和委托的实现如下代码所示：

1 namespace ObserverInNET 2 {
3 class Program 4 {
5 // 委托充当订阅者接口类
6 public delegate void NotifyEventHandler(object sender); 7
8 // 抽象订阅号类
9 public class TenXun 10 { 11 public NotifyEventHandler NotifyEvent; 12
13 public string Symbol { get; set; } 14 public string Info { get; set; } 15 public TenXun(string symbol, string info) 16 { 17 this.Symbol = symbol; 18 this.Info = info; 19 } 20
21 #region 新增对订阅号列表的维护操作
22 public void AddObserver(NotifyEventHandler ob) 23 { 24 NotifyEvent += ob; 25 } 26 public void RemoveObserver(NotifyEventHandler ob) 27 { 28 NotifyEvent -= ob; 29 } 30
31 #endregion
32
33 public void Update() 34 { 35 if (NotifyEvent != null) 36 { 37 NotifyEvent(this); 38 } 39 } 40 } 41
42 // 具体订阅号类
43 public class TenXunGame : TenXun 44 { 45 public TenXunGame(string symbol, string info) 46 : base(symbol, info) 47 { 48 } 49 } 50
51 // 具体订阅者类
52 public class Subscriber 53 { 54 public string Name { get; set; } 55 public Subscriber(string name) 56 { 57 this.Name = name; 58 } 59
60 public void ReceiveAndPrint(Object obj) 61 { 62 TenXun tenxun = obj as TenXun; 63
64 if (tenxun != null) 65 { 66 Console.WriteLine(“Notified {0} of {1}’s” + “ Info is: {2}”, Name, tenxun.Symbol, tenxun.Info); 67 } 68 } 69 } 70
71 static void Main(string[] args) 72 { 73 TenXun tenXun = new TenXunGame(“TenXun Game”, “Have a new game published ….”); 74 Subscriber lh = new Subscriber(“Learning Hard”); 75 Subscriber tom = new Subscriber(“Tom”); 76
77 // 添加订阅者
78 tenXun.AddObserver(new NotifyEventHandler(lh.ReceiveAndPrint)); 79 tenXun.AddObserver(new NotifyEventHandler(tom.ReceiveAndPrint)); 80
81 tenXun.Update(); 82
83 Console.WriteLine(“-———————————-“); 84 Console.WriteLine(“移除Tom订阅者”); 85 tenXun.RemoveObserver(new NotifyEventHandler(tom.ReceiveAndPrint)); 86 tenXun.Update(); 87
88 Console.ReadLine(); 89 } 90 } 91 }

　　从上面代码可以看出，使用事件和委托实现的观察者模式中，减少了订阅者接口类的定义，此时，.NET中的委托正式充到订阅者接口类的角色。使用委托和事件，确实简化了观察者模式的实现，减少了一个IObserver接口的定义，上面代码的运行结果如下图所示：

　　在下面的情况下可以考虑使用观察者模式：

当一个抽象模型有两个方面，其中一个方面依赖于另一个方面，将这两者封装在独立的对象中以使它们可以各自独立地改变和复用的情况下。从方面的这个词中可以想到，观察者模式肯定在AOP（面向方面编程）中有所体现，更多内容参考：Observern Pattern in AOP.
当对一个对象的改变需要同时改变其他对象，而又不知道具体有多少对象有待改变的情况下。
当一个对象必须通知其他对象，而又不能假定其他对象是谁的情况下。

　　观察者模式有以下几个优点：

观察者模式实现了表示层和数据逻辑层的分离，并定义了稳定的更新消息传递机制，并抽象了更新接口，使得可以有各种各样不同的表示层，即观察者。
观察者模式在被观察者和观察者之间建立了一个抽象的耦合，被观察者并不知道任何一个具体的观察者，只是保存着抽象观察者的列表，每个具体观察者都符合一个抽象观察者的接口。
观察者模式支持广播通信。被观察者会向所有的注册过的观察者发出通知。

　　观察者也存在以下一些缺点：

如果一个被观察者有很多直接和间接的观察者时，将所有的观察者都通知到会花费很多时间。
虽然观察者模式可以随时使观察者知道所观察的对象发送了变化，但是观察者模式没有相应的机制使观察者知道所观察的对象是怎样发生变化的。
如果在被观察者之间有循环依赖的话，被观察者会触发它们之间进行循环调用，导致系统崩溃，在使用观察者模式应特别注意这点。

　　到这里，观察者模式的分享就介绍了。观察者模式定义了一种一对多的依赖关系，让多个观察者对象可以同时监听某一个主题对象，这个主题对象在发生状态变化时，会通知所有观察者对象，使它们能够自动更新自己，解决的是“当一个对象的改变需要同时改变多个其他对象”的问题。大家可以以微信订阅号的例子来理解观察者模式。

CSharp设计模式(18)——中介者模式（Mediator Pattern）

发表于 1899-11-30 更新于 2025-03-27 分类于 Lessons ，设计模式 Valine：

　　在现实生活中，有很多中介者模式的身影，例如QQ游戏平台，聊天室、QQ群和短信平台，这些都是中介者模式在现实生活中的应用，下面就具体分享下我对中介者模式的理解。

2.1 中介者模式的定义

　　从生活中的例子可以看出，不论是QQ游戏还是QQ群，它们都是充当一个中间平台，QQ用户可以登录这个中间平台与其他QQ用户进行交流，如果没有这些中间平台，我们如果想与朋友进行聊天的话，可能就需要当面才可以了。电话、短信也同样是一个中间平台，有了这个中间平台，每个用户都不要直接依赖与其他用户，只需要依赖这个中间平台就可以了，一切操作都由中间平台去分发。了解完中介模式在生活中的模型后，下面给出中介模式的正式定义。

　　中介者模式，定义了一个中介对象来封装一系列对象之间的交互关系。中介者使各个对象之间不需要显式地相互引用，从而使耦合性降低，而且可以独立地改变它们之间的交互行为。

2.2 中介者模式的结构

　　从生活中例子自然知道，中介者模式设计两个具体对象，一个是用户类，另一个是中介者类，根据针对接口编程原则，则需要把这两类角色进行抽象，所以中介者模式中就有了4类角色，它们分别是：抽象中介者角色，具体中介者角色、抽象同事类和具体同事类。中介者类是起到协调各个对象的作用，则抽象中介者角色中则需要保存各个对象的引用。有了上面的分析，则就不难理解中介者模式的结构图了，具体结构图如下所示：

为什么要使用中介者模式

　　在现实生活中，中介者的存在是不可缺少的，如果没有了中介者，我们就不能与远方的朋友进行交流了。而在软件设计领域，为什么要使用中介者模式呢？如果不使用中介者模式的话，各个同事对象将会相互进行引用，如果每个对象都与多个对象进行交互时，将会形成如下图所示的网状结构。

　　从上图可以发现，如果不使用中介者模式的话，每个对象之间过度耦合，这样的既不利于类的复用也不利于扩展。如果引入了中介者模式，那么对象之间的关系将变成星型结构，采用中介者模式之后会形成如下图所示的结构：

　　从上图可以发现，使用中介者模式之后，任何一个类的变化，只会影响中介者和类本身，不像之前的设计，任何一个类的变化都会引起其关联所有类的变化。这样的设计大大减少了系统的耦合度。

2.3 中介者模式的实现

　　介绍完中介者模式的定义和存在的必要性后，下面就以现实生活中打牌的例子来实现下中介者模式。在现实生活中，两个人打牌，如果某个人赢了都会影响到对方状态的改变。如果此时不采用中介者模式实现的话，则上面的场景的实现如下所示：

1 // 抽象牌友类
2 public abstract class AbstractCardPartner 3 {
4 public int MoneyCount { get; set; }
5
6 public AbstractCardPartner() 7 {
8 MoneyCount = 0;
9 } 10
11 public abstract void ChangeCount(int Count, AbstractCardPartner other); 12 } 13
14 // 牌友A类
15 public class ParterA : AbstractCardPartner 16 { 17 public override void ChangeCount(int Count, AbstractCardPartner other) 18 { 19 this.MoneyCount += Count; 20 other.MoneyCount -= Count; 21 } 22 } 23
24 // 牌友B类
25 public class ParterB : AbstractCardPartner 26 { 27 public override void ChangeCount(int Count, AbstractCardPartner other) 28 { 29 this.MoneyCount += Count; 30 other.MoneyCount -= Count; 31 } 32 } 33
34 class Program 35 { 36 // A,B两个人打牌
37 static void Main(string[] args) 38 { 39 AbstractCardPartner A = new ParterA(); 40 A.MoneyCount = 20; 41 AbstractCardPartner B = new ParterB(); 42 B.MoneyCount = 20; 43
44 // A 赢了则B的钱就减少
45 A.ChangeCount(5, B); 46 Console.WriteLine(“A 现在的钱是：{0}”, A.MoneyCount);// 应该是25
47 Console.WriteLine(“B 现在的钱是：{0}”, B.MoneyCount); // 应该是15 48
49 // B赢了A的钱也减少
50 B.ChangeCount(10, A); 51 Console.WriteLine(“A 现在的钱是：{0}”, A.MoneyCount); // 应该是15
52 Console.WriteLine(“B 现在的钱是：{0}”, B.MoneyCount); // 应该是25
53 Console.Read(); 54 } 55 }

　　上面确实完美解决了上面场景中的问题，并且使用了抽象类使具体牌友A和牌友B都依赖于抽象类，从而降低了同事类之间的耦合度。但是这样的设计，如果其中牌友A发生变化时，此时就会影响到牌友B的状态，如果涉及的对象变多的话，这时候某一个牌友的变化将会影响到其他所有相关联的牌友状态。例如牌友A算错了钱，这时候牌友A和牌友B的钱数都不正确了，如果是多个人打牌的话，影响的对象就会更多。这时候就会思考——能不能把算钱的任务交给程序或者算数好的人去计算呢，这时候就有了我们QQ游戏中的欢乐斗地主等牌类游戏了。所以上面的设计，我们还是有进一步完善的方案的，即加入一个中介者对象来协调各个对象之间的关联，这也就是中介者模式的应用了，具体完善后的实现代码如下所示：

1 namespace MediatorPattern 2 {
3 // 抽象牌友类
4 public abstract class AbstractCardPartner 5 {
6 public int MoneyCount { get; set; }
7
8 public AbstractCardPartner() 9 { 10 MoneyCount = 0; 11 } 12
13 public abstract void ChangeCount(int Count, AbstractMediator mediator); 14 } 15
16 // 牌友A类
17 public class ParterA : AbstractCardPartner 18 { 19 // 依赖与抽象中介者对象
20 public override void ChangeCount(int Count, AbstractMediator mediator) 21 { 22 mediator.AWin(Count); 23 } 24 } 25
26 // 牌友B类
27 public class ParterB : AbstractCardPartner 28 { 29 // 依赖与抽象中介者对象
30 public override void ChangeCount(int Count, AbstractMediator mediator) 31 { 32 mediator.BWin(Count); 33 } 34 } 35
36 // 抽象中介者类
37 public abstract class AbstractMediator 38 { 39 protected AbstractCardPartner A; 40 protected AbstractCardPartner B; 41 public AbstractMediator(AbstractCardPartner a, AbstractCardPartner b) 42 { 43 A = a; 44 B = b; 45 } 46
47 public abstract void AWin(int count); 48 public abstract void BWin(int count); 49 } 50
51 // 具体中介者类
52 public class MediatorPater : AbstractMediator 53 { 54 public MediatorPater(AbstractCardPartner a, AbstractCardPartner b) 55 : base(a, b) 56 { 57 } 58
59 public override void AWin(int count) 60 { 61 A.MoneyCount += count; 62 B.MoneyCount -= count; 63 } 64
65 public override void BWin(int count) 66 { 67 B.MoneyCount += count; 68 A.MoneyCount -= count; 69 } 70 } 71
72 class Program 73 { 74 static void Main(string[] args) 75 { 76 AbstractCardPartner A = new ParterA(); 77 AbstractCardPartner B = new ParterB(); 78 // 初始钱
79 A.MoneyCount = 20; 80 B.MoneyCount = 20; 81
82 AbstractMediator mediator = new MediatorPater(A, B); 83
84 // A赢了
85 A.ChangeCount(5, mediator); 86 Console.WriteLine(“A 现在的钱是：{0}”, A.MoneyCount);// 应该是25
87 Console.WriteLine(“B 现在的钱是：{0}”, B.MoneyCount); // 应该是15 88
89 // B 赢了
90 B.ChangeCount(10, mediator); 91 Console.WriteLine(“A 现在的钱是：{0}”, A.MoneyCount);// 应该是15
92 Console.WriteLine(“B 现在的钱是：{0}”, B.MoneyCount); // 应该是25
93 Console.Read(); 94 } 95 } 96 }

　　从上面实现代码可以看出，此时牌友A和牌友B都依赖于抽象的中介者类，这样如果其中某个牌友类变化只会影响到，只会影响到该变化牌友类本身和中介者类，从而解决前面实现代码出现的问题，具体的运行结果和前面实现结果一样，运行结果如下图所示：

　　在上面的实现代码中，抽象中介者类保存了两个抽象牌友类，如果新添加一个牌友类似时，此时就不得不去更改这个抽象中介者类。可以结合观察者模式来解决这个问题，即抽象中介者对象保存抽象牌友的类别，然后添加Register和UnRegister方法来对该列表进行管理，然后在具体中介者类中修改AWin和BWin方法，遍历列表，改变自己和其他牌友的钱数。这样的设计还是存在一个问题——即增加一个新牌友时，此时虽然解决了抽象中介者类不需要修改的问题，但此时还是不得不去修改具体中介者类，即添加CWin方法，我们可以采用状态模式来解决这个问题，关于状态模式的介绍将会在下一专题进行分享。

　　一般在以下情况下可以考虑使用中介者模式：

一组定义良好的对象，现在要进行复杂的相互通信。
想通过一个中间类来封装多个类中的行为，而又不想生成太多的子类。

　　中介者模式具有以下几点优点：

简化了对象之间的关系，将系统的各个对象之间的相互关系进行封装，将各个同事类解耦，使得系统变为松耦合。
提供系统的灵活性，使得各个同事对象独立而易于复用。

　　然而，中介者模式也存在对应的缺点：

中介者模式中，中介者角色承担了较多的责任，所以一旦这个中介者对象出现了问题，整个系统将会受到重大的影响。例如，QQ游戏中计算欢乐豆的程序出错了，这样会造成重大的影响。
新增加一个同事类时，不得不去修改抽象中介者类和具体中介者类，此时可以使用观察者模式和状态模式来解决这个问题。

　　中介者模式，定义了一个中介对象来封装系列对象之间的交互。中介者使各个对象不需要显式地相互引用，从而使其耦合性降低，而且可以独立地改变它们之间的交互。中介者模式一般应用于一组定义良好的对象之间需要进行通信的场合以及想定制一个分布在多个类中的行为，而又不想生成太多的子类的情形下。

CSharp设计模式(20)——策略者模式（Stragety Pattern）

发表于 1899-11-30 更新于 2025-03-27 分类于 Lessons ，设计模式 Valine：

　　前面主题介绍的状态模式是对某个对象状态的抽象，而本文要介绍的策略模式也就是对策略进行抽象，策略的意思就是方法，所以也就是对方法的抽象，下面具体分享下我对策略模式的理解。

2.1 策略模式的定义

　　在现实生活中，策略模式的例子也非常常见，例如，中国的所得税，分为企业所得税、外商投资企业或外商企业所得税和个人所得税，针对于这3种所得税，针对每种，所计算的方式不同，个人所得税有个人所得税的计算方式，而企业所得税有其对应计算方式。如果不采用策略模式来实现这样一个需求的话，可能我们会定义一个所得税类，该类有一个属性来标识所得税的类型，并且有一个计算税收的CalculateTax()方法，在该方法体内需要对税收类型进行判断，通过if-else语句来针对不同的税收类型来计算其所得税。这样的实现确实可以解决这个场景吗，但是这样的设计不利于扩展，如果系统后期需要增加一种所得税时，此时不得不回去修改CalculateTax方法来多添加一个判断语句，这样明白违背了“开放——封闭”原则。此时，我们可以考虑使用策略模式来解决这个问题，既然税收方法是这个场景中的变化部分，此时自然可以想到对税收方法进行抽象。具体的实现代码见2.3部分。

　　前面介绍了策略模式用来解决的问题，下面具体给出策略的定义。策略模式是针对一组算法，将每个算法封装到具有公共接口的独立的类中，从而使它们可以相互替换。策略模式使得算法可以在不影响到客户端的情况下发生变化。

2.2 策略模式的结构

　　策略模式是对算法的包装，是把使用算法的责任和算法本身分割开，委派给不同的对象负责。策略模式通常把一系列的算法包装到一系列的策略类里面。用一句话慨括策略模式就是——“将每个算法封装到不同的策略类中，使得它们可以互换”。

　　下面是策略模式的结构图：

　　该模式涉及到三个角色：

环境角色（Context）：持有一个Strategy类的引用
抽象策略角色（Strategy）：这是一个抽象角色，通常由一个接口或抽象类来实现。此角色给出所有具体策略类所需实现的接口。
具体策略角色（ConcreteStrategy）：包装了相关算法或行为。

2.3 策略模式的实现

　　下面就以所得税的例子来实现下策略模式，具体实现代码如下所示：

1 namespace StrategyPattern 2 {
3 // 所得税计算策略
4 public interface ITaxStragety 5 {
6 double CalculateTax(double income); 7 }
8
9 // 个人所得税
10 public class PersonalTaxStrategy : ITaxStragety 11 { 12 public double CalculateTax(double income) 13 { 14 return income * 0.12; 15 } 16 } 17
18 // 企业所得税
19 public class EnterpriseTaxStrategy : ITaxStragety 20 { 21 public double CalculateTax(double income) 22 { 23 return (income - 3500) > 0 ? (income - 3500) * 0.045 : 0.0; 24 } 25 } 26
27 public class InterestOperation 28 { 29 private ITaxStragety m_strategy; 30 public InterestOperation(ITaxStragety strategy) 31 { 32 this.m_strategy = strategy; 33 } 34
35 public double GetTax(double income) 36 { 37 return m_strategy.CalculateTax(income); 38 } 39 } 40
41 class App 42 { 43 static void Main(string[] args) 44 { 45 // 个人所得税方式
46 InterestOperation operation = new InterestOperation(new PersonalTaxStrategy()); 47 Console.WriteLine(“个人支付的税为：{0}”, operation.GetTax(5000.00)); 48
49 // 企业所得税
50 operation = new InterestOperation(new EnterpriseTaxStrategy()); 51 Console.WriteLine(“企业支付的税为：{0}”, operation.GetTax(50000.00)); 52
53 Console.Read(); 54 } 55 } 56 }　　

　　在.NET Framework中也不乏策略模式的应用例子。例如，在.NET中，为集合类型ArrayList和List提供的排序功能，其中实现就利用了策略模式，定义了IComparer接口来对比较算法进行封装，实现IComparer接口的类可以是顺序，或逆序地比较两个对象的大小，具体.NET中的实现可以使用反编译工具查看List.Sort(IComparer)的实现。其中List就是承担着环境角色，而IComparer接口承担着抽象策略角色，具体的策略角色就是实现了IComparer接口的类，List类本身实现了存在实现了该接口的类，我们可以自定义继承与该接口的具体策略类。

　　在下面的情况下可以考虑使用策略模式：

一个系统需要动态地在几种算法中选择一种的情况下。那么这些算法可以包装到一个个具体的算法类里面，并为这些具体的算法类提供一个统一的接口。
如果一个对象有很多的行为，如果不使用合适的模式，这些行为就只好使用多重的if-else语句来实现，此时，可以使用策略模式，把这些行为转移到相应的具体策略类里面，就可以避免使用难以维护的多重条件选择语句，并体现面向对象涉及的概念。

　　策略模式的主要优点有：

策略类之间可以自由切换。由于策略类都实现同一个接口，所以使它们之间可以自由切换。
易于扩展。增加一个新的策略只需要添加一个具体的策略类即可，基本不需要改变原有的代码。
避免使用多重条件选择语句，充分体现面向对象设计思想。

　　策略模式的主要缺点有：

客户端必须知道所有的策略类，并自行决定使用哪一个策略类。这点可以考虑使用IOC容器和依赖注入的方式来解决，关于IOC容器和依赖注入（Dependency Inject）的文章可以参考：IoC 容器和Dependency Injection 模式。
策略模式会造成很多的策略类。

　　到这里，策略模式的介绍就结束了，策略模式主要是对方法的封装，把一系列方法封装到一系列的策略类中，从而使不同的策略类可以自由切换和避免在系统使用多重条件选择语句来选择针对不同情况来选择不同的方法。在下一章将会大家介绍责任链模式。

CSharp设计模式(23)——备忘录模式（Memento Pattern）

发表于 1899-11-30 更新于 2025-03-27 分类于 Lessons ，设计模式 Valine：

　　在上一篇博文分享了访问者模式，访问者模式的实现是把作用于某种数据结构上的操作封装到访问者中，使得操作和数据结构隔离。而今天要介绍的备忘者模式与命令模式有点相似，不同的是，命令模式保存的是发起人的具体命令（命令对应的是行为），而备忘录模式保存的是发起人的状态（而状态对应的数据结构，如属性）。下面具体来看看备忘录模式。

2.1 备忘录模式的定义

　　从字面意思就可以明白，备忘录模式就是对某个类的状态进行保存下来，等到需要恢复的时候，可以从备忘录中进行恢复。生活中这样的例子经常看到，如备忘电话通讯录，备份操作操作系统，备份数据库等。

　　备忘录模式的具体定义是：在不破坏封装的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态，这样以后就可以把该对象恢复到原先的状态。

2.2 备忘录模式的结构图

　　介绍完备忘录模式的定义之后，下面具体看看备忘录模式的结构图：

　　备忘录模式中主要有三类角色：

发起人角色：记录当前时刻的内部状态，负责创建和恢复备忘录数据。
备忘录角色：负责存储发起人对象的内部状态，在进行恢复时提供给发起人需要的状态。
管理者角色：负责保存备忘录对象。

2.3 备忘录模式的实现

　　下面以备份手机通讯录为例子来实现了备忘录模式，具体的实现代码如下所示：

// 联系人
public class ContactPerson
{ public string Name { get; set; } public string MobileNum { get; set; }
} // 发起人
public class MobileOwner
{ // 发起人需要保存的内部状态
public List ContactPersons { get; set; } public MobileOwner(List persons)
{
ContactPersons = persons;
} // 创建备忘录，将当期要保存的联系人列表导入到备忘录中
public ContactMemento CreateMemento()
{ // 这里也应该传递深拷贝，new List方式传递的是浅拷贝，
// 因为ContactPerson类中都是string类型,所以这里new list方式对ContactPerson对象执行了深拷贝
// 如果ContactPerson包括非string的引用类型就会有问题，所以这里也应该用序列化传递深拷贝
return new ContactMemento(new List(this.ContactPersons));
} // 将备忘录中的数据备份导入到联系人列表中
public void RestoreMemento(ContactMemento memento)
{ // 下面这种方式是错误的，因为这样传递的是引用，
// 则删除一次可以恢复，但恢复之后再删除的话就恢复不了.
// 所以应该传递contactPersonBack的深拷贝，深拷贝可以使用序列化来完成
this.ContactPersons = memento.contactPersonBack;
} public void Show()
{
Console.WriteLine(“联系人列表中有{0}个人，他们是:”, ContactPersons.Count); foreach (ContactPerson p in ContactPersons)
{
Console.WriteLine(“姓名: {0} 号码为: {1}”, p.Name, p.MobileNum);
}
}
} // 备忘录
public class ContactMemento
{ // 保存发起人的内部状态
public List contactPersonBack; public ContactMemento(List persons)
{
contactPersonBack = persons;
}
} // 管理角色
public class Caretaker
{ public ContactMemento ContactM { get; set; }
} class Program
{ static void Main(string[] args)
{
List persons = new List()
{ new ContactPerson() { Name= “Learning Hard”, MobileNum = “123445”}, new ContactPerson() { Name = “Tony”, MobileNum = “234565”}, new ContactPerson() { Name = “Jock”, MobileNum = “231455”}
};
MobileOwner mobileOwner = new MobileOwner(persons);
mobileOwner.Show(); // 创建备忘录并保存备忘录对象
Caretaker caretaker = new Caretaker();
caretaker.ContactM = mobileOwner.CreateMemento(); // 更改发起人联系人列表
Console.WriteLine(“-—移除最后一个联系人——–”);
mobileOwner.ContactPersons.RemoveAt(2);
mobileOwner.Show(); // 恢复到原始状态
Console.WriteLine(“-——恢复联系人列表——“);
mobileOwner.RestoreMemento(caretaker.ContactM);
mobileOwner.Show();

        Console.Read();
    }
}

　　具体的运行结果如下图所示：

　　从上图可以看出，刚开始通讯录中有3个联系人，然后移除以后一个后变成2个联系人了，最后恢复原来的联系人列表后，联系人列表中又恢复为3个联系人了。

　　上面代码只是保存了一个还原点，即备忘录中只保存了3个联系人的数据，但是，如果想备份多个还原点怎么办呢？即恢复到3个人后，又想恢复到前面2个人的状态，这时候可能你会想，这样没必要啊，到时候在删除不就好了。但是如果在实际应用中，可能我们发了很多时间去创建通讯录中只有2个联系人的状态，恢复到3个人的状态后，发现这个状态时错误的，还是原来2个人的状态是正确的，难道我们又去花之前的那么多时间去重复操作吗？这显然不合理，如果就思考，能不能保存多个还原点呢？保存多个还原点其实很简单，只需要保存多个备忘录对象就可以了。具体实现代码如下所示：

namespace MultipleMementoPattern
{ // 联系人
public class ContactPerson
{ public string Name { get; set; } public string MobileNum { get; set; }
} // 发起人
public class MobileOwner
{ public List ContactPersons { get; set; } public MobileOwner(List persons)
{
ContactPersons = persons;
} // 创建备忘录，将当期要保存的联系人列表导入到备忘录中
public ContactMemento CreateMemento()
{ // 这里也应该传递深拷贝，new List方式传递的是浅拷贝，
// 因为ContactPerson类中都是string类型,所以这里new list方式对ContactPerson对象执行了深拷贝
// 如果ContactPerson包括非string的引用类型就会有问题，所以这里也应该用序列化传递深拷贝
return new ContactMemento(new List(this.ContactPersons));
} // 将备忘录中的数据备份导入到联系人列表中
public void RestoreMemento(ContactMemento memento)
{ if (memento != null)
{ // 下面这种方式是错误的，因为这样传递的是引用，
// 则删除一次可以恢复，但恢复之后再删除的话就恢复不了.
// 所以应该传递contactPersonBack的深拷贝，深拷贝可以使用序列化来完成
this.ContactPersons = memento.ContactPersonBack;
}
} public void Show()
{
Console.WriteLine(“联系人列表中有{0}个人，他们是:”, ContactPersons.Count); foreach (ContactPerson p in ContactPersons)
{
Console.WriteLine(“姓名: {0} 号码为: {1}”, p.Name, p.MobileNum);
}
}
} // 备忘录
public class ContactMemento
{ public List ContactPersonBack {get;set;} public ContactMemento(List persons)
{
ContactPersonBack = persons;
}
} // 管理角色
public class Caretaker
{ // 使用多个备忘录来存储多个备份点
public Dictionary<string, ContactMemento> ContactMementoDic { get; set; } public Caretaker()
{
ContactMementoDic = new Dictionary<string, ContactMemento>();
}
} class Program
{ static void Main(string[] args)
{
List persons = new List()
{ new ContactPerson() { Name= “Learning Hard”, MobileNum = “123445”}, new ContactPerson() { Name = “Tony”, MobileNum = “234565”}, new ContactPerson() { Name = “Jock”, MobileNum = “231455”}
};

        MobileOwner mobileOwner \= new MobileOwner(persons);
        mobileOwner.Show(); // 创建备忘录并保存备忘录对象
        Caretaker caretaker = new Caretaker();
        caretaker.ContactMementoDic.Add(DateTime.Now.ToString(), mobileOwner.CreateMemento()); // 更改发起人联系人列表
        Console.WriteLine("\----移除最后一个联系人--------");
        mobileOwner.ContactPersons.RemoveAt(2);
        mobileOwner.Show(); // 创建第二个备份
        Thread.Sleep(1000);
        caretaker.ContactMementoDic.Add(DateTime.Now.ToString(), mobileOwner.CreateMemento()); // 恢复到原始状态
        Console.WriteLine("\-------恢复联系人列表,请从以下列表选择恢复的日期------"); var keyCollection = caretaker.ContactMementoDic.Keys; foreach (string k in keyCollection)
        {
            Console.WriteLine("Key = {0}", k);
        } while (true)
        {
            Console.Write("请输入数字,按窗口的关闭键退出:"); int index = -1; try {
                index \= Int32.Parse(Console.ReadLine());
            } catch {
                Console.WriteLine("输入的格式错误"); continue;
            }
            
            ContactMemento contactMentor \= null; if (index < keyCollection.Count && caretaker.ContactMementoDic.TryGetValue(keyCollection.ElementAt(index), out contactMentor))
            {
                mobileOwner.RestoreMemento(contactMentor);
                mobileOwner.Show();
            } else {
                Console.WriteLine("输入的索引大于集合长度！");
            }
        }     
    }
}

}

　　这样就保存了多个状态，客户端可以选择恢复的状态点，具体运行结果如下所示：

　　在以下情况下可以考虑使用备忘录模式：

如果系统需要提供回滚操作时，使用备忘录模式非常合适。例如文本编辑器的Ctrl+Z撤销操作的实现，数据库中事务操作。

　　备忘录模式具有以下优点：

如果某个操作错误地破坏了数据的完整性，此时可以使用备忘录模式将数据恢复成原来正确的数据。
备份的状态数据保存在发起人角色之外，这样发起人就不需要对各个备份的状态进行管理。而是由备忘录角色进行管理，而备忘录角色又是由管理者角色管理，符合单一职责原则。

　　当然，备忘录模式也存在一定的缺点：

在实际的系统中，可能需要维护多个备份，需要额外的资源，这样对资源的消耗比较严重。

　　备忘录模式主要思想是——利用备忘录对象来对保存发起人的内部状态，当发起人需要恢复原来状态时，再从备忘录对象中进行获取，在实际开发过程也应用到这点，例如数据库中的事务处理。

8种主要排序算法的C#实现

Excerpt

简介

选择排序

冒泡排序

通过标识提升冒泡排序

鸡尾酒排序（来回排序）

对冒泡排序进行更大的优化

插入排序

二分查找法优化插入排序

快速排序

另一个版本

针对这个版本的缺点，我进行了优化

归并排序

IList版本

堆排序

希尔排序

基数排序

桶排序

为基数排序做个过渡，我这里实现了一个个位数桶排序

测试比较

总结

主要参考：维基百科，有趣的演示

一、引言

二、组合模式的详细介绍

2.1 组合模式的定义

2.2 组合模式的实现

2.3 组合模式的类图

三、组合模式的优缺点

四、组合模式的使用场景

五、组合模式在.NET中的应用

六、总结

一、引言

二、享元模式的详细介绍

2.1 定义

2.2 享元模式实现

2.3 享元模式的类图

三、享元模式的优缺点

四、使用场景

五、总结

一、引言

二、模板方法模式详细介绍

2.1 模板方法模式的定义

2.2 模板方法模式的实现

2.3 模板方法模式的类图

三、模板方法模式的优缺点

四、总结

2.1 迭代器模式的定义

2.2 迭代器模式的结构

2.3 迭代器模式的实现

2.1 观察者模式的定义

2.2 观察者模式的结构

2.3 观察者模式的实现

2.1 中介者模式的定义

2.2 中介者模式的结构

2.3 中介者模式的实现

2.1 策略模式的定义

2.2 策略模式的结构

2.3 策略模式的实现

2.1 备忘录模式的定义

2.2 备忘录模式的结构图

2.3 备忘录模式的实现