首先来看比较简单的选择排序(Selectionsort)，插入排序(Insertionsort)，然后在分析插入排序的特征和缺点的基础上，介绍在插入排序基础上改进的希尔排序(Shellsort)。
原理：
选择排序很简单，他的步骤如下：
之所以称之为选择排序，是因为每一次遍历未排序的序列我们总是从中选择出最小的元素。下面是选择排序的动画演示：
实现：
算法实现起来也很简单，我们新建一个Sort泛型类，让该类型必须实现IComparable接口，然后我们定义SelectionSort方法，方法传入T数组，代码如下：
publicstaticvoidSelectionSort(T[]array){intn=array.Length;for(inti=0;iintmin=i;//从第i+1个元素开始，找最小值for(intj=i+1;jif(array[min].CompareTo(array[j])>0)min=j;}//找到之后和第i个元素交换Swap(array,i,min);}}//////元素交换////////////privatestaticvoidSwap(T[]array,inti,intmin){Ttemp=array[i];array[i]=array[min];array[min]=temp;}}下图分析了选择排序中每一次排序的过程，您可以对照图中右边的柱状图来看。
测试如下：
输出结果：
分析：
选择排序的在各种初始条件下的排序效果如下：
插入排序也是一种比较直观的排序方式。可以以我们平常打扑克牌为例来说明，假设我们那在手上的牌都是排好序的，那么插入排序可以理解为我们每一次将摸到的牌，和手中的牌从左到右依次进行对比，如果找到合适的位置则直接插入。具体的步骤为：
下面是插入排序的动画演示：
在Sort泛型方法中，我们添加如下方法，下面的方法和上面的定义一样
插入排序的在各种初始条件下的排序效果如下：
1.插入排序平均需要N2/4次比较和N2/4次交换。在最坏的情况下需要N2/2次比较和交换；在最好的情况下只需要N-1次比较和0次交换。
先考虑最坏情况，那就是所有的元素逆序排列，那么第i个元素需要与前面的i-1个元素进行i-1次比较和交换，所有的加起来大概等于N(N-1)/2~N2/2，在数组随机排列的情况下，只需要和前面一半的元素进行比较和交换，所以平均需要N2/4次比较和N2/4次交换。
在最好的情况下，所有元素都排好序，只需要从第二个元素开始都和前面的元素比较一次即可，不需要交换，所以为N-1次比较和0次交换。
2.插入排序中，元素交换的次数等于序列中逆序元素的对数。元素比较的次数最少为元素逆序元素的对数，最多为元素逆序的对数加上数组的个数减1。
3.总体来说，插入排序对于部分有序序列以及元素个数比较小的序列是一种比较有效的方式。
如上图中，序列AEELMOTRXPS，中逆序的对数为T-R，T-P，T-S，R-P，X-S6对。典型的部分有序队列的特征有：
对于部分有序数组，插入排序是比较有效的。当数组中逆元素的对数越低，插入排序要比其他排序方法要高效的多。
选择排序和插入排序的比较：
上图展示了插入排序和选择排序的动画效果。图中灰色的柱子是不用动的，黑色的是需要参与到比较中的，红色的是参与交换的。图中可以看出：
插入排序不会动右边的元素，选择排序不会动左边的元素；由于插入排序涉及到的未触及的元素要比插入的元素要少，涉及到的比较操作平均要比选择排序少一半。
希尔排序也称之为递减增量排序，他是对插入排序的改进。在第二部插入排序中，我们知道，插入排序对于近似已排好序的序列来说，效率很高，可以达到线性排序的效率。但是插入排序效率也是比较低的，他一次只能将数据向前移一位。比如如果一个长度为N的序列，最小的元素如果恰巧在末尾，那么使用插入排序仍需一步一步的向前移动和比较，要N-1次比较和交换。
希尔排序通过将待比较的元素划分为几个区域来提升插入排序的效率。这样可以让元素可以一次性的朝最终位置迈进一大步，然后算法再取越来越小的步长进行排序，最后一步就是步长为1的普通的插入排序的，但是这个时候，整个序列已经是近似排好序的，所以效率高。
如下图，我们对下面数组进行排序的时候，首先以4为步长，这是元素分为了LMPT，EHSS，ELOX，AELR几个序列，我们对这几个独立的序列进行插入排序，排序完成之后，我们减小步长继续排序，最后直到步长为1，步长为1即为一般的插入排序，他保证了元素一定会被排序。
希尔排序的增量递减算法可以随意指定，可以以N/2递减，只要保证最后的步长为1即可。
publicstaticvoidShellSort(T[]array){intn=array.Length;inth=1;//初始最大步长while(hwhile(h>=1){//从第二个元素开始for(inti=1;i//从第i个元素开始，依次次和前面已经排好序的i-h个元素比较，如果小于，则交换for(intj=i;j>=h;j=j-h){if(array[j].CompareTo(array[j-h])<0)=""{=""swap(array,=""j,=""j=""-=""h);=""}="">else//如果大于，则不用继续往前比较了，因为前面的元素已经排好序，比较大的大就是教大的了。break;}}//步长除3递减h=h/3;}}可以看到，希尔排序的实现是在插入排序的基础上改进的，插入排序的步长为1，每一次递减1，希尔排序的步长为我们定义的h，然后每一次和前面的-h位置上的元素进行比较。算法中，我们首先获取小于N/3的最大的步长，然后逐步长递减至步长为1的一般的插入排序。
下面是希尔排序在各种情况下的排序动画：
该序列由下面两个表达式交互获得:
“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
名称
最好
平均
最坏
内存占用
稳定排序
插入排序
n
n2
1
是
选择排序
否
希尔排序
nlog2n或n3/2
依赖于增量递减序列目前最好的是nlog2n
希望本文对您了解以上三个基本的排序算法有所帮助，后面将会介绍合并排序和快速排序。