CSharp排序算法小结
前言
算法这个东西其实在开发中很少用到，特别是web开发中，但是算法也很重要，因为任何的程序，任何的软件，都是由很多的算法和数据结构组成的。但是这不意味着算法对于每个软件设计人员的实际工作都是很重要的。每个项目特点和需求特殊也导致算法运用场景上不同。但是个人觉得算法运用的好的话会给自己在程序设计的时候提供比较好的思路。下面就对一些排序算法小结一下，就当做自己的一个笔记吧。
插入排序
1.简介
插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
2.算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
1.从第一个元素开始，该元素可以认为已经被排序
2.取出下一个元素，在已经排序的元素序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一位置
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到该位置后
6.重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。
3.使用插入排序为一列数字进行排序的过程
最差时间复杂度 
最优时间复杂度 
平均时间复杂度
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)
平均时间复杂度 根据步长串行的不同而不同。
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.实现过程
最差时间复杂度
最优时间复杂度
平均时间复杂度
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;
}
}
}
}
8种主要排序算法的CSharp实现
8种主要排序算法的C#实现
Excerpt
8种主要排序算法的实现及优化，包含选择排序，冒泡排序，插入排序，快速排序，归并排序，堆排序，希尔排序，基数排序。文末实际测试并比较。
新的一年到了，很多园友都辞职要去追求更好的工作环境，我也是其中一个，呵呵！
最近闲暇的时候我开始重温一些常用的算法。老早就买了《算法导论》，一直都没啃下去。
这本书确实很好，只是太难读了，总是读了几章就又读不下去了！工作上也几乎用不到。
我这段时间发现看这些排序算法比以前容易了很多，就借此机会将它们整理总结起来。
一是方便以后重温，二是可以应对笔试面试。同时也希望这篇博文可以帮助各位刚辞职和正在学习排序算法的园友。
PS：有可能实现的代码并不是最优的，如果有什么错误或者值得改进的地方，还请大家帮忙指出。
简介
排序算法是我们编程中遇到的最多的算法。目前主流的算法有8种。
平均时间复杂度从高到低依次是：
冒泡排序（o(n2)），选择排序（o(n2)），插入排序（o(n2)），堆排序（o(nlogn)），
归并排序（o(nlogn)），快速排序（o(nlogn)）， 希尔排序（o(n1.25)），基数排序（o(n)）
这些平均时间复杂度是参照维基百科排序算法罗列的。
是计算的理论平均值，并不意味着你的代码实现能达到这样的程度。
例如希尔排序，时间复杂度是由选择的步长决定的。基数排序时间复杂度最小，
但我实现的基数排序的速度并不是最快的，后面的结果测试图可以看到。
本文代码实现使用的数据源类型为IList
List
选择排序
选择排序是我觉得最简单暴力的排序方式了。
以前刚接触排序算法的时候，感觉算法太多搞不清，唯独记得选择排序的做法及实现。
原理：找出参与排序的数组最大值，放到末尾（或找到最小值放到开头） 维基入口
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> SelectSort(IList<<span>int</span>><span> data) |
过程解析：将剩余数组的最小数交换到开头。
冒泡排序
冒泡排序是笔试面试经常考的内容，虽然它是这些算法里排序速度最慢的（汗），后面有测试为证。
原理：从头开始，每一个元素和它的下一个元素比较，如果它大，就将它与比较的元素交换，否则不动。
这意味着，大的元素总是在向后慢慢移动直到遇到比它更大的元素。所以每一轮交换完成都能将最大值
冒到最后。 维基入口
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> BubbleSort(IList<<span>int</span>><span> data) |
过程解析：中需要注意的是j<i，每轮冒完泡必然会将最大值排到数组末尾，所以需要排序的数应该是在减少的。
很多网上版本每轮冒完泡后依然还是将所有的数进行第二轮冒泡即j<data.Count-1，这样会增加比较次数。
通过标识提升冒泡排序
在维基上看到，可以通过添加标识来分辨剩余的数是否已经有序来减少比较次数。感觉很有意思，可以试试。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> BubbleSortImprovedWithFlag(IList<<span>int</span>><span> data) |
过程解析：发现某轮冒泡没有任何数进行交换（即已经有序），就跳出排序。
我起初也以为这个方法是应该有不错效果的，可是实际测试结果并不如想的那样。和未优化耗费时间一样（对于随机数列）。
由果推因，那么应该是冒泡排序对于随机数列，当剩余数列有序的时候，也没几个数要排列了！？
不过如果已经是有序数列或者部分有序的话，这个冒泡方法将会提升很大速度。
鸡尾酒排序（来回排序）
对冒泡排序进行更大的优化
冒泡排序只是单向冒泡，而鸡尾酒来回反复双向冒泡。
原理：自左向右将大数冒到末尾，然后将剩余数列再自右向左将小数冒到开头，如此循环往复。维基入口
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> BubbleCocktailSort(IList<<span>int</span>><span> data) |
过程解析：分析第i轮冒泡，i是偶数则将剩余数列最大值向右冒泡至末尾，是奇数则将剩余数列最小值
向左冒泡至开头。对于剩余数列，n为始，data.Count-1-m为末。
来回冒泡比单向冒泡：对于随机数列，更容易得到有序的剩余数列。因此这里使用标识将会提升的更加明显。
插入排序
插入排序是一种对于有序数列高效的排序。非常聪明的排序。只是对于随机数列，效率一般，交换的频率高。
原理：通过构建有序数列，将未排序的数从后向前比较，找到合适位置并插入。维基入口
第一个数当作有序数列。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> InsertSort(IList<<span>int</span>><span> data) |
过程解析：将要排序的数（索引为i）存储起来，向前查找合适位置j+1，将i-1到j+1的元素依次向后
移动一位，空出j+1，然后将之前存储的值放在这个位置。
这个方法写的不如维基上的简洁清晰，由于合适位置是j+1所以多出了对j==0的判断，但实际效率影响无差别。
建议比照维基和我写的排序，自行选择。
二分查找法优化插入排序
插入排序主要工作是在有序的数列中对要排序的数查找合适的位置，而查找里面经典的二分查找法正可以适用。
原理：通过二分查找法的方式找到一个位置索引。当要排序的数插入这个位置时，大于前一个数，小于后一个数。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> InsertSortImprovedWithBinarySearch(IList<<span>int</span>><span> data) |
过程解析：需要注意的是二分查找方法实现中high-low==1的时候mid==low，所以需要33行
mid-1<0即mid==0的判断，否则下行会索引越界。
快速排序
快速排序是一种有效比较较多的高效排序。它包含了“分而治之”以及“哨兵”的思想。
原理：从数列中挑选一个数作为“哨兵”，使比它小的放在它的左侧，比它大的放在它的右侧。将要排序是数列递归地分割到
最小数列，每次都让分割出的数列符合“哨兵”的规则，自然就将数列变得有序。 维基入口
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> QuickSortStrict(IList<<span>int</span>><span> data) |
过程解析：取的哨兵是数列的第一个值，然后从第二个和末尾同时查找，左侧要显示的是小于哨兵的值，
所以要找到不小于的i，右侧要显示的是大于哨兵的值，所以要找到不大于的j。将找到的i和j的数交换，
这样可以减少交换次数。i>=j时，数列全部查找了一遍，而不符合条件j必然是在小的那一边，而哨兵
是第一个数，位置本应是小于自己的数。所以将哨兵与j交换，使符合“哨兵”的规则。
这个版本的缺点在于如果是有序数列排序的话，递归次数会很可怕的。
另一个版本
这是维基上的一个C#版本，我觉得很有意思。这个版本并没有严格符合“哨兵”的规则。但却将“分而治之”
以及“哨兵”思想融入其中，代码简洁。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> QuickSortRelax(IList<<span>int</span>><span> data) |
过程解析：取的哨兵是数列中间的数。将数列分成两波，左侧小于等于哨兵，右侧大于等于哨兵。
也就是说，哨兵不一定处于两波数的中间。虽然哨兵不在中间，但不妨碍“哨兵”的思想的实现。所以
这个实现也可以达到快速排序的效果。但却造成了每次递归完成，要排序的数列数总和没有减少（除非i==j）。
针对这个版本的缺点，我进行了优化
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> QuickSortRelaxImproved(IList<<span>int</span>><span> data) |
过程解析：定义了一个变量Index，来跟踪哨兵的位置。发现哨兵最后在小于自己的那堆，
那就与j交换，否则与i交换。达到每次递归都能减少要排序的数列数总和的目的。
归并排序
归并排序也是采用“分而治之”的方式。刚发现分治法是一种算法范式，我还一直以为是一种需要意会的思想呢。
不好意思了，孤陋寡闻了，哈哈！
原理：将两个有序的数列，通过比较，合并为一个有序数列。 维基入口
为方便理解，此处实现用了List
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> List<<span>int</span>> MergeSortOnlyList(List<<span>int</span>> data, <span>int</span> low, <span>int</span><span> high) |
过程解析：将数列分为两部分，分别得到两部分数列的有序版本，然后逐个比较，将比较出的小数逐个放进
新的空数列中。当一个数列放完后，将另一个数列剩余数全部放进去。
IList版本
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> IList<<span>int</span>> MergeSort(IList<<span>int</span>><span> data) |
过程原理与上个一样，此处就不赘述了。
堆排序
堆排序是根据堆这种数据结构设计的一种算法。堆的特性：父节点的值总是小于（或大于）它的子节点。近似二叉树。
原理：将数列构建为最大堆数列（即父节点总是最大值），将最大值（即根节点）交换到数列末尾。这样要排序的数列数总和减少，
同时根节点不再是最大值，调整最大堆数列。如此重复，最后得到有序数列。 维基入口 有趣的演示
实现准备：如何将数列构造为堆——父节点i的左子节点为2i+1，右子节点为2i+2。节点i的父节点为floor((i-1)/2)。
实现如下（这个实现判断和临时变量使用太多，导致效率低，评论中@小城故事提出了更好的实现）：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> HeapSort(IList<<span>int</span>><span> data) |
过程解析：BuildMaxHeapify为排序前构建的最大堆数列方法，主要内容为从最后一个父节点开始往前将每个三角组合
（即父节点与它的两个子节点）符合父节点值最大的规则。ReSortMaxBranch为将三角调整为父节点值最大，
并返回该值之前的索引，用来判断是否进行了交换，以及原来的父节点值交换到了什么位置。在HeapSort里首先
构建了最大堆数列，然后将根节点交换到末尾，根节点不是最大值了，在while语句中对最大堆数列进行调整。
插曲：自从看了Martin Fowler大师《重构》第三版，我发现我更不喜欢写注释了。每次都想着尽量让方法的名字更贴切，
即使会造成方法的名字很长很丑。这算不算曲解了大师的意思啊！？上面的代码注释都是写博客的时候现加的（源代码很干净的。汗!）。
希尔排序
希尔排序是插入排序的一种更高效的改进版本。
在前面介绍的插入排序，我们知道1.它对有序数列排序的效率是非常高的 2.要排序的数向前移动是一步步进行的导致插入排序效率低。
希尔排序正是利用第一点，改善第二点，达到更理想的效果。
原理：通过奇妙的步长，插入排序间隔步长的元素，随后逐渐缩短步长至1，实现数列的插入排序。 维基入口
疑问：可以想象到排序间隔步长的数，会逐渐让数列变得有序，提升最后步长为1时标准插入排序的效率。在维基上看到这么
一句话“可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的”注意用词是‘可能’。我的疑问是
这是个正确的命题吗？如何证明呢？看维基上也是由果推因，说是如果不是这样，就不会排序那么快了。可这我感觉还是太牵强了，
哪位大哥发现相关资料，希望能分享出来，不胜感激。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> ShellSort(IList<<span>int</span>><span> data) |
过程解析：采用的步长是N/2，每次取半，直至1。循环内部就是标准的插入排序。
——————
修正：修正后希尔排序才是真正牛叉的希尔啊！感谢@390218462的提出
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> ShellSortCorrect(IList<<span>int</span>><span> data) |
——————
这里实现的貌似是最差的希尔排序。主要源于步长的选择。维基上有各种牛叉的“凌波微步”，极限在哪里，
喜欢挑战的同学可以去学习学习。看维基排序算法里六种排序的测试，希尔最快，比快速排序还快！！我没实现啊！
只是对于神奇的步长更充满了敬畏。
基数排序
基数排序是一种非比较型整数排序。
“非比较型”是什么意思呢？因为它内部使用的是桶排序，而桶排序是非比较型排序。
这里就要说说桶排序了。一个非常有意思的排序。
桶排序
原理：取一定数量（数列中的最大值）的编好序号的桶，将数列每个数放进编号为它的桶里，然后将不是空的桶依次倒出来，
就组成有序数列了。 维基入口
好吧！聪明的人一眼就看出桶排序的破绽了。假设只有两个数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没数。这个时候就需要在放
入每个位置时采用其它排序（比如插入排序）办法对这个位置的多个数排序了。
为基数排序做个过渡，我这里实现了一个个位数桶排序
涉及到了当重复的数出现的处理。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> BucketSortOnlyUnitDigit(IList<<span>int</span>><span> data) |
过程解析：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。这样就通过提前给重复的数空出位置，解决了
重复的数出现的问题。当然，你也可以考虑用二维数组来解决重复。
下面继续基数排序。
基数排序原理：将整数按位数切割成不同的数字，然后按每个位数分别比较。
取得最大数的位数，从低位开始，每个位上进行桶排序。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> IList<<span>int</span>> RadixSort(IList<<span>int</span>><span> data) |
过程解析：得出最大数的位数，从低位开始桶排序。我写的这个实现代码并不简洁，但逻辑更清晰。
后面测试的时候我们就会发现，按理来说这个实现也还行吧！ 但并不如想象的那么快！
循环的次数太多？（统计频率n次+9次计算+n次放到新的数组）*位数。
创建的新实例太多？(new int[10]两次+NewInstance is反射判断创建实例+new int[n])*位数
测试比较
添加随机数组，数组有序校验，微软Linq排序
代码如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>int</span>[] RandomSet(<span>int</span> length, <span>int</span><span> max) |
测试主体如下：
1 | <span> 1</span> <span>static</span> <span>void</span> Main(<span>string</span><span>[] args) |
剩余代码折叠在此处
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
或者int[]来调用微软封装的方法。这样说来，题目说C#实现倒快有点名不副实了。不过这样却也方便了其它语言
朋友。比如将我这篇博文里的实现随便改改，就可以说是另一个语言版本的8种排序算法了。哈哈！在这里，
我想说下这次学习排序对我的意义：老久不怎么动脑了，突然动起来，磨磨唧唧地得出结果，最后倒也有点成就感！
在学习过程中，经常会脑子转不过弯，想不通的，只是走在路上或者睡觉前突然灵感一现，有点小惊喜的感觉！
这大概就是进步的特征吧！哈哈！这次写demo+写博客花费了不少时间，倒也收获颇多，尤其在我将8种
排序都实现之前，没进行过一次测试，全部实现完成后，测试时各种索引越界+无限循环+各种问题，没几个
能跑通的，到后来的几乎都没有问题，也算是锻炼了思维，找出错原因的能力。本篇是自我学习的一个总结，
要学习及锻炼的园友，还望一定自己实现一下，可以和我的比较一下，解除疑惑或者提出改进。
主要参考：维基百科，有趣的演示
Demo源码
PS:我打算三月份去广州发展，主要会Asp.net mvc+jquery（不介意学习新的技术[除了webform]及语言[除了java]）。
设计模式总结
设计模式是软件开发中经过总结和验证的、解决特定场景下常见问题的最佳实践，它能提升代码的可复用性、可维护性、可读性和扩展性。根据目的和应用场景，设计模式主要分为创建型模式、结构型模式、行为型模式三大类，以下是各类模式的核心总结及对应UML图：
一、创建型模式
创建型模式聚焦于对象的创建过程，封装对象创建的细节，降低创建逻辑与业务逻辑的耦合，让程序在创建对象时更灵活。
1. 单例模式（Singleton）
核心意图：保证一个类仅有一个实例，并提供一个全局访问点。
适用场景：配置管理、日志记录器、数据库连接池等需唯一实例的场景。
实现要点：私有化构造方法，通过静态方法/属性返回唯一实例；需考虑线程安全（如懒汉式加锁、饿汉式提前初始化）、序列化/反序列化破坏单例的问题。
优缺点：优点是节省资源、全局统一访问；缺点是违背单一职责，扩展困难，可能引发并发问题（未妥善处理时）。
UML类图：
2. 工厂方法模式（Factory Method）
核心意图：定义创建对象的接口，让子类决定实例化哪个类，将对象创建延迟到子类。
适用场景：产品种类可扩展，创建逻辑需隔离的场景（如日志框架支持不同日志输出类型）。
实现要点：抽象工厂类定义创建方法，具体工厂类实现该方法创建对应产品。
优缺点：优点是符合开闭原则，解耦产品创建与使用；缺点是新增产品需新增工厂类，类数量增多。
UML类图：
3. 抽象工厂模式（Abstract Factory）
核心意图：提供一个创建一系列相关或相互依赖对象的接口，无需指定具体类。
适用场景：需创建一套“产品族”（如操作系统+UI组件组合、数据库+驱动组合）的场景。
实现要点：抽象工厂定义多个产品创建方法，具体工厂实现所有方法，产出对应产品族。
优缺点：优点是保证产品族一致性，隔离具体产品；缺点是新增产品族需修改抽象工厂，违背开闭原则。
UML类图：
4. 建造者模式（Builder）
核心意图：将复杂对象的构建与表示分离，使得同样的构建过程可以创建不同的表示。
适用场景：对象属性多、构造逻辑复杂（如建造汽车、生成复杂文档）。
实现要点：建造者类封装构建步骤，指挥者类控制构建流程，产品类表示最终对象。
优缺点：优点是解耦构建与表示，灵活控制构建过程；缺点是产品属性固定时冗余，类数量增加。
UML类图：
5. 原型模式（Prototype）
核心意图：通过复制现有实例（原型）创建新对象，避免重复初始化开销。
适用场景：对象创建成本高（如数据库查询后的数据对象）、需批量创建相似对象的场景。
实现要点：实现克隆接口（浅克隆/深克隆），通过原型对象复制生成新对象。
优缺点：优点是简化创建过程，提升性能；缺点是深克隆需处理复杂引用关系。
UML类图：
二、结构型模式
结构型模式关注类和对象的组合方式，通过合理的结构设计，提升代码的灵活性和复用性，解决类/对象间的耦合与扩展问题。
1. 适配器模式（Adapter）
核心意图：将一个类的接口转换成客户希望的另一个接口，让不兼容的类可以协同工作。
适用场景：集成第三方库、复用现有类但接口不匹配、新旧系统对接。
实现要点：类适配器（继承适配者）、对象适配器（组合适配者）、接口适配器（默认空实现）。
优缺点：优点是复用现有代码，解耦接口与实现；缺点是增加额外类，复杂场景可能导致适配链过长。
UML类图（对象适配器）：
2. 装饰器模式（Decorator）
核心意图：动态地给一个对象添加一些额外的职责，比继承更灵活。
适用场景：需扩展对象功能，且功能可组合（如IO流、日志增强、权限叠加）。
实现要点：装饰器类与被装饰类实现同一接口，持有被装饰对象引用，重写方法并增强逻辑。
优缺点：优点是灵活扩展，符合开闭原则；缺点是多层装饰会增加代码复杂度。
UML类图：
3. 代理模式（Proxy）
核心意图：为其他对象提供一种代理以控制对这个对象的访问。
适用场景：远程代理（RPC）、虚拟代理（懒加载）、保护代理（权限控制）、日志代理（监控）。
实现要点：静态代理（手动编写代理类）、动态代理（JDK动态代理、CGLIB），代理类与目标类实现同一接口/继承目标类。
优缺点：优点是隔离目标对象，增强访问控制；缺点是增加代理层，可能降低性能。
UML类图（静态代理）：
4. 外观模式（Facade）
核心意图：为子系统中的一组接口提供一个一致的入口，简化子系统的使用。
适用场景：复杂系统（如电商下单：库存、支付、物流子系统）、对外提供统一API。
实现要点：外观类封装子系统交互逻辑，对外暴露简单接口。
优缺点：优点是降低使用复杂度，解耦客户端与子系统；缺点是外观类可能成为“上帝类”，耦合过多逻辑。
UML类图：
5. 桥接模式（Bridge）
核心意图：将抽象部分与它的实现部分分离，使它们都可以独立地变化。
适用场景：多维度变化的场景（如“形状+颜色”、“操作系统+文件系统”）。
实现要点：抽象类持有实现类引用，抽象与实现分层，各自独立扩展。
优缺点：优点是解耦抽象与实现，符合开闭原则；缺点是增加代码复杂度，理解成本高。
UML类图：
6. 组合模式（Composite）
核心意图：将对象组合成树形结构以表示“部分-整体”的层次结构，统一对待单个对象和组合对象。
适用场景：树形结构场景（如菜单、文件目录、组织架构）。
实现要点：抽象组件类定义公共方法，叶子节点类表示单个对象，组合节点类包含子组件集合。
优缺点：优点是统一访问单个/组合对象，简化客户端逻辑；缺点是设计复杂，限制类型时需额外判断。
UML类图：
7. 享元模式（Flyweight）
核心意图：运用共享技术有效地支持大量细粒度的对象，减少内存占用。
适用场景：大量相似对象（如池化资源、字符常量池、游戏角色）。
实现要点：区分内部状态（共享）和外部状态（不共享），享元工厂管理共享对象池。
优缺点：优点是减少内存消耗，提升性能；缺点是增加系统复杂度，需处理外部状态。
UML类图：
三、行为型模式
行为型模式关注对象间的交互和职责分配，优化对象的通信方式和行为逻辑，提升代码的协作性和可扩展性。
1. 观察者模式（Observer）
核心意图：定义对象间的一对多依赖，当一个对象状态改变时，所有依赖它的对象都得到通知并自动更新。
适用场景：事件驱动、发布-订阅（如GUI事件、消息通知、数据监听）。
实现要点：主题（被观察者）维护观察者列表，提供注册/移除/通知方法；观察者实现更新方法。
优缺点：优点是解耦主题与观察者，支持广播通知；缺点是观察者过多时通知效率低，可能引发循环依赖。
UML类图：
2. 策略模式（Strategy）
核心意图：定义一系列算法，将每个算法封装起来，使它们可以互相替换，且算法的变化不影响使用算法的客户。
适用场景：多种算法可选（如排序算法、支付方式、优惠计算）。
实现要点：策略接口定义算法方法，具体策略类实现算法，上下文类持有策略引用并调用。
优缺点：优点是算法可灵活切换，符合开闭原则；缺点是客户端需了解所有策略，策略过多时类数量增加。
UML类图：
3. 模板方法模式（Template Method）
核心意图：定义一个操作中的算法骨架，将一些步骤延迟到子类中，子类不改变算法结构即可重定义某些步骤。
适用场景：流程固定但步骤实现可变（如框架初始化、报表生成、测试流程）。
实现要点：抽象父类定义模板方法（固定流程）和抽象方法（可变步骤），子类实现抽象方法。
优缺点：优点是复用流程代码，控制扩展点；缺点是模板方法过多时父类复杂，子类受限。
UML类图：
4. 迭代器模式（Iterator）
核心意图：提供一种方法顺序访问一个聚合对象中的各个元素，而不暴露其内部表示。
适用场景：遍历集合（如列表、集合、树），统一遍历接口。
实现要点：迭代器接口定义遍历方法（next、hasNext），聚合类提供获取迭代器的方法。
优缺点：优点是统一遍历接口，解耦聚合与遍历；缺点是简单遍历场景下增加冗余类。
UML类图：
5. 命令模式（Command）
核心意图：将请求封装成对象，以便使用不同的请求、队列或日志来参数化其他对象，支持撤销/重做操作。
适用场景：请求解耦（如GUI按钮、事务操作、任务队列）。
实现要点：命令接口定义执行方法，具体命令类封装接收者和动作，调用者触发命令执行。
优缺点：优点是解耦请求者与接收者，支持命令组合、撤销；缺点是类数量增加，简单场景冗余。
UML类图：
6. 责任链模式（Chain of Responsibility）
核心意图：为请求创建一个接收者对象的链，使多个对象都有机会处理请求，避免请求发送者与接收者耦合。
适用场景：请求需多节点处理（如权限审批、日志分级、异常处理链）。
实现要点：处理者接口定义处理方法，每个处理者持有下一个处理者引用，自行处理或转发请求。
优缺点：优点是解耦请求与处理，动态调整责任链；缺点是请求可能无人处理，调试复杂。
UML类图：
7. 状态模式（State）
核心意图：允许对象在其内部状态改变时改变它的行为，对象看起来似乎修改了它的类。
适用场景：对象行为依赖状态（如订单状态、电梯状态、游戏角色状态）。
实现要点：状态接口定义行为方法，具体状态类实现对应行为，上下文类持有当前状态并委托状态处理。
优缺点：优点是状态逻辑集中管理，避免大量if-else；缺点是状态多时有大量状态类。
UML类图：
8. 备忘录模式（Memento）
核心意图：在不破坏封装的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态，以便后续恢复。
适用场景：撤销操作（如编辑器、游戏存档、事务回滚）。
实现要点：备忘录类存储状态，原发器创建/恢复备忘录，管理者管理备忘录。
优缺点：优点是支持状态回滚，封装状态；缺点是消耗内存（大量备忘录）。
UML类图：
9. 中介者模式（Mediator）
核心意图：用一个中介对象来封装一系列的对象交互，使各对象不需要显式地相互引用，降低耦合。
适用场景：多对象复杂交互（如聊天室、GUI组件交互、分布式系统协调）。
实现要点：中介者接口定义交互方法，具体中介者封装对象间交互，同事类通过中介者通信。
优缺点：优点是解耦对象间交互，简化维护；缺点是中介者可能成为“上帝类”，复杂度高。
UML类图：
10. 解释器模式（Interpreter）
核心意图：给定一个语言，定义它的文法的一种表示，并定义一个解释器，该解释器使用该表示来解释语言中的句子。
适用场景：简单语法解析（如表达式计算、配置解析、自定义脚本）。
实现要点：抽象表达式定义解释方法，终结符/非终结符表达式实现具体逻辑，环境类存储上下文。
优缺点：优点是灵活扩展语法；缺点是语法复杂时类数量爆炸，效率低。
UML类图：
四、设计模式核心原则
所有设计模式均围绕SOLID原则展开，是设计模式的底层逻辑：
单一职责原则（SRP）：一个类只负责一个职责，降低耦合。
开闭原则（OCP）：对扩展开放，对修改关闭，通过抽象/接口实现。
里氏替换原则（LSP）：子类可替换父类且不影响程序正确性。
接口隔离原则（ISP）：拆分臃肿接口，提供最小化专用接口。
依赖倒置原则（DIP）：依赖抽象而非具体实现，降低耦合。
五、设计模式使用建议
不要过度设计：仅在问题重复出现、需复用/扩展时使用，避免为了用模式而用模式。
优先复用现有框架：多数框架已内置设计模式（如Spring的单例、代理，MyBatis的工厂、装饰器），无需重复实现。
结合场景选择：如创建对象选创建型，扩展功能选装饰器/策略，解耦交互选观察者/中介者。
理解本质而非形式：模式的核心是解决问题的思路，而非固定代码结构。
设计模式是经验的沉淀，掌握其思想能让代码更贴合“高内聚、低耦合”的软件设计目标，提升系统的可维护性和扩展性。
解释器模式
解释器模式（Interpreter Pattern）是行为型设计模式的重要分支，其核心设计思想是定义特定语言的文法规则，并构建对应的解释器，将复杂的语法解析拆解为多个简单的解释器节点，通过组合这些节点完成整体语法的解释与执行。该模式专注于“语法解析与逻辑执行”的解耦，适用于处理固定语法规则的场景，如表达式计算、自定义配置解析、简单脚本解释、领域特定语言（DSL）实现等。本文将从核心结构拆解、多语言落地实现、优缺点深度剖析、适用场景梳理及实战总结等维度，系统解读解释器模式的设计思想与工程实践，为开发者提供可直接复用的技术方案。
一、解释器模式核心结构
解释器模式的核心价值在于“拆分复杂语法、实现模块化解析”，通过五大核心角色的协同工作，完成语法树的构建与解释执行，各角色职责边界清晰、耦合度低，具体定义与交互逻辑如下：
1.1 抽象表达式（Abstract Expression）
抽象表达式是所有具体表达式的基类或接口，核心职责是定义统一的解释操作接口（通常命名为Interpret方法）。该接口是所有表达式节点的通用入口，确保终结符与非终结符表达式能以统一的方式被调用，为多态解析提供基础。
1.2 终结符表达式（Terminal Expression）
终结符表达式是语法树的叶子节点，对应文法中的终结符（即语法规则中不可再拆分的最小单元），如算术表达式中的数字、常量，配置语法中的键值对等。其核心职责是实现终结符的具体解释逻辑，无需依赖其他表达式，直接返回解析结果。
1.3 非终结符表达式（Nonterminal Expression）
非终结符表达式对应文法中的非终结符（可拆分为多个子表达式的语法单元），如算术表达式中的加减乘除运算符、逻辑表达式中的与或非逻辑等。其核心职责是组合多个子表达式（终结符或非终结符），通过递归调用子表达式的解释方法，完成复杂语法的解析与执行。
1.4 环境（Context）
环境类用于存储解释器的全局上下文信息，供所有表达式共享使用，如变量映射关系、语法解析的中间状态、计算结果缓存等。环境类的存在的可以减少表达式之间的直接依赖，同时为后续扩展（如变量替换）提供灵活支撑。
1.5 客户端（Client）
客户端负责两个核心操作：一是根据预设的文法规则，构建由终结符表达式和非终结符表达式组成的语法树；二是调用语法树根节点的解释方法，触发整个语法树的逐层解析与执行，最终获取解析结果。
核心交互流程：客户端定义文法规则 → 构建语法树（组合终结符与非终结符表达式） → 初始化环境上下文 → 调用根节点Interpret方法 → 子表达式逐层递归解析 → 返回最终执行结果。
二、多语言实现解释器模式
以“简单算术表达式解析（支持整数加减运算）”为统一实战场景，设计核心逻辑：通过解释器模式解析表达式“1 + 2 - 3”，拆解为“加法表达式”与“减法表达式”的组合，最终计算出结果。以下提供C#、Python、Golang、C++及纯C的可运行实现，贴合各语言原生特性，补充规范注释、边界校验与资源释放逻辑，兼顾实用性与严谨性，清晰呈现模式在不同语言中的适配思路。
2.1 C# 实现（面向对象规范实现）
C#作为强类型面向对象语言，通过接口定义抽象表达式，依托类实现终结符与非终结符逻辑，借助多态特性实现统一解析。代码结构清晰、可维护性高，适用于企业级应用中的简单表达式解析、配置语法解析等场景。
1 | using System; |
2.2 Python 实现（动态语言简洁实现）
Python遵循“鸭子类型”，无需显式定义接口，通过基类+子类继承实现抽象表达式逻辑，语法简洁、无冗余类型声明。依托动态特性，可灵活扩展表达式类型，无需修改核心解析逻辑，适用于快速开发、轻量级解析场景（如简单配置解析、小型计算器）。
1 | class Context: |
2.3 Golang 实现（接口至上轻量实现）
Go语言无类和继承，遵循“组合优于继承”原则，通过接口定义抽象表达式，结构体实现接口方法，依托接口多态实现统一解析。代码极简高效、无冗余，贴合Go语言“简洁、高效”的设计理念，适配高并发后端场景（如服务端配置解析、简单规则引擎）。
1 | package main |
2.4 C++ 实现（抽象类+虚函数经典实现）
C++通过抽象类（纯虚函数）定义抽象表达式，子类继承并实现具体解释逻辑，依托虚函数实现多态解析。同时通过手动内存管理，避免内存泄漏，兼顾灵活性与高性能，适用于底层开发、高频调用场景（如编译器简化版表达式解析、嵌入式设备规则解析）。
1 |
|
2.5 纯C语言实现（结构体+函数指针模拟实现）
纯C无面向对象特性，通过“结构体封装数据+函数指针封装行为”模拟解释器模式的核心逻辑，依托函数指针实现统一的解释接口，通过命名约定区分终结符与非终结符表达式。底层可控性强、无额外依赖，适用于嵌入式、底层开发等资源受限场景，完整还原模式“拆分语法、组合解析”的核心思想。
1 |
|
三、解释器模式的优缺点
解释器模式的核心优势是“高扩展性、语法模块化”，但同时存在性能损耗与维护成本的权衡。实际开发中需结合业务场景，判断是否适用该模式，避免过度设计或滥用。
3.1 核心优点
扩展性极强：新增文法规则时，只需新增对应的终结符或非终结符表达式，无需修改现有解析逻辑，完全符合“开闭原则”。例如，在现有加减表达式基础上，新增乘法表达式，仅需实现
MultiplyExpression类，无需改动其他代码。语法解析模块化：将复杂语法拆解为多个简单的表达式节点，每个节点职责单一，代码可读性高、易于理解和维护。例如，算术表达式拆分为数字、加法、减法等节点，每个节点仅处理自身的解析逻辑。
代码复用性高：相同的表达式节点可在不同的语法树中复用，例如数字表达式可同时用于加减乘除等多种运算表达式中，减少代码冗余。
易于实现简单语法：对于固定且简单的文法规则，无需依赖复杂的解析工具，通过解释器模式可快速实现解析逻辑，开发成本低。
3.2 主要缺点
性能损耗较大：语法树的解析依赖递归调用，嵌套层级越深，递归次数越多，性能损耗越明显；同时，每个表达式节点都是独立对象（或结构体），大量节点会占用较多内存，尤其在高频解析场景中，性能瓶颈突出。
维护成本高：若文法规则复杂（如支持乘除、括号、优先级、变量替换等），需定义大量的表达式类/结构体，代码量会急剧增加，后续维护和扩展的成本大幅上升。
适用场景有限：仅适用于固定且简单的文法规则，无法应对动态、复杂的语法解析场景（如完整的编程语言解释器、复杂SQL解析），此类场景更适合使用专业的解析器生成工具（如ANTLR、Yacc）。
调试难度高：语法解析过程是递归执行的，当解析出现异常时，难以定位问题所在，调试成本较高。
四、解释器模式的使用场景
解释器模式的适用场景具有明确的核心前提：文法规则固定且简单，需要自定义语法解析，且对解析性能要求不高。以下结合具体业务场景与实战案例，帮助开发者精准判断适用性，避免滥用。
4.1 核心适用场景
简单表达式计算：如计算器中的加减乘除、逻辑表达式（&&、||、!）解析，自定义公式计算（如业务系统中的折扣计算、积分计算）。
自定义配置解析：解析自定义格式的配置文件，如自定义键值对规则、简单条件配置（如“if 条件A then 执行B”），适用于轻量级配置场景。
领域特定语言（DSL）实现：实现简化版的领域特定语言，如数据库查询语言（简化版SQL）、脚本语言（如Lua子集）、规则引擎中的规则语法（如风控规则、权限规则）。
格式转换与解析：如日期格式解析（如“yyyy-MM-dd”转换为日期对象）、数据格式解析（如自定义协议数据解析）、简单模板解析（如静态模板中的变量替换）。
简单规则执行：业务规则简单且固定的场景，如工作流中的节点跳转规则、消息推送的条件规则，通过解释器模式解析规则并执行。
4.2 不适用场景
复杂语法解析场景（如完整的编程语言解释器、复杂SQL解析）：此类场景文法规则复杂，使用解释器模式会导致代码量激增、维护困难，应使用专业的解析器生成工具。
高频解析、高性能要求场景（如实时数据解析、高并发接口中的表达式计算）：解释器模式的递归解析会导致性能损耗，应使用编译期优化、逆波兰表达式等更高效的方案。
文法规则频繁变更的场景：每次规则变更都需新增或修改表达式节点，维护成本过高，不适合使用解释器模式。
五、总结
解释器模式通过“拆分语法、组合解析”的思路，将复杂的语法解释逻辑拆解为可复用的简单节点，核心价值是简化固定语法的解析逻辑并提供良好的扩展性，其本质是“语法的模块化与多态解析”。该模式让客户端无需关注具体的解析细节，只需构建语法树并调用解释方法，即可完成语法解析与执行。
从多语言实现来看，不同语言的实现风格虽有显著差异，但核心逻辑高度一致：
面向对象语言（C#、Python、C++、Golang）可直接通过接口/抽象类+多态实现，代码结构贴合解释器模式的经典定义，开发高效、可读性强；
纯C语言则通过结构体+函数指针模拟面向对象特性，虽实现过程稍繁琐，但能在资源受限的底层场景中还原模式核心价值，兼顾底层可控性。
在实际开发中，使用解释器模式需重点权衡两个核心点：一是扩展性与维护成本，若文法规则简单且稳定，解释器模式是优雅的选择；若规则复杂，需优先考虑专业解析工具；二是性能与场景适配，高频解析场景需避免使用，优先选择更高效的解析方案。
总之，解释器模式是“简单语法解析”场景下的高效解决方案，掌握其核心结构与多语言实现，能帮助开发者在实际项目中优雅处理自定义语法解析、规则执行等需求，平衡代码设计与工程落地成本，提升系统的可扩展性与可维护性。