知识结构：
图1知识结构1.排序的基本概念与术语假设含有
个记录的序列为
，其相应的关键字分别为
，需确定的一种排列
，使其相应的关键字满足
的关系，即使得序列成为一个按关键字有序的序列，这个样的操作就称为排列。
能唯一标识某一记录的关键字称为主关键字。
假设，且在排序前的序列中
领先于
（即$ij$）。如果排序后$r_i$仍领先于$r_j$，则称所用的排序方法是
领先于
，则称所用的排序方法是不稳定的。
例如：
待排序序列：稳定的排序结果：
不稳定的排序结果：
内部排序：排序过程都在内存中进行的排序。
外部排序：排序过程需要在内存和外存之间不断交换数据的排序。
根据排序过程中借助的主要操作，我们把内排序分为：插入排序、选择排序、交换排序和并归排序。可以说，这些都是比较成熟的排序技术，已经被广泛地应用于许许多多的程序语言或数据库当中，甚至它们都已经封装了关于排序算法的实现代码。因此，我们学习这些排序算法的目的不是为了去现实排序算法，而是通过学习来提高我们编写算法的能力，以便于去解决更多复杂和灵活的应用性问题。
图2排序类2.插入排序2.1直接插入排序将一个记录插入到已经排好序的有序表中，从而得到一个新的记录增1的有序表。
即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
如：int[]Key=newint[]{45,34,78,12,34,32,29,64};
排序过程：
程序代码：
///summary///直接插入排序////summary///typeparamname="T"需要排序记录的类型/typeparam///paramname="array"需要排序的记录集合/parampublicstaticvoidStraightInsertSortT(T[]array)whereT:IComparableT{for(inti=1;iarray.Length;i++){intj=i-1;Tcurrent=array;while(j=0array[j].CompareTo(current)0){array[j+1]=array[j];j--;}array[j+1]=current;}}
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面，所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以直接插入排序是稳定的。
2.2希尔插入排序希尔排序是年由D.L.Shell提出来的，相对直接插入排序有较大的改进。希尔插入排序又叫做缩小增量排序。
直接插入排序的效率在某些时候是很高的，比如我们的记录本身就是基本有序的，我们只需要少量的插入操作，就可以完成整个记录集的排序工作，此时直接插入排序很高效。还有就是记录数比较少时，直接插入的优势也比较明显。可问题在于，两个条件本身就过于苛刻，现实中记录少或者基本有序都属于特殊情况。
不过别着急，有条件当然是好，条件不存在，我们创造条件也是可以去做的。于是科学家希尔研究出了一种排序方法，对直接插入排序改进后可以增加效率。
思想：按待排序列下标的一定增量分组（如：增量序列
，其中
，
），将整个待排序列分割成若干子序列，分别进行直接插入排序，随着增量逐渐减少，所分组包含的记录越来越多，到增量值减至1时，整个记录集被分成一组（这时待排序列“基本有序”），再对全体记录进行直接插入排序，算法终止（对待排序列进行了
趟直接插入排序）。
我所理解ShellInsertionSort最牛的地方是，让排序算法能够并行化。
希尔插入排序增量的取法：
即：先将要排序的一组记录按某个增量
（
，
为要排序数的个数）分成若干组子序列，每组中记录的下标相差
。对每组中全部元素进行直接插入排序，然后在用一个较小的增量（
）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。
如：int[]Key=newint[]{45,34,78,12,34,32,29,64};
排序过程：
程序代码：
privatestaticvoidShellT(intdelta,T[]array)whereT:IComparableT{//带增量的直接插入排序for(inti=delta;iarray.Length;i++){intj=i-delta;Tcurrent=array;while(j=0array[j].CompareTo(current)0){array[j+delta]=array[j];j=j-delta;}array[j+delta]=current;}}///summary///希尔插入排序////summary///typeparamname="T"需要排序记录的类型/typeparam///paramname="array"需要排序的记录集合/parampublicstaticvoidShellInsertSortT(T[]array)whereT:IComparableT{for(intdelta=array.Length/2;delta0;delta=delta/2){Shell(delta,array);}}
希尔插入排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列
的选取。目前还没有人给出选取最好的增量因子序列的方法。希尔插入排序方法是一个不稳定的排序方法。
3.选择排序3.1直接选择排序思想：每一趟在
个记录中选取关键字最小的记录作为有序序列中第
个记录。（在要排列的一组数中，选出最小的一个数与第1个位置的数交换；然后在剩下的数当中再找最小的与第2个位置的数交换，依次类推，直到第
个元素和第
个元素比较为止。）
如：int[]Key=newint[]{45,34,78,12,34,32,29,64};
排序过程：
程序代码：
///summary///直接选择排序////summary///typeparamname="T"需要排序记录的类型/typeparam///paramname="array"需要排序的记录集合/parampublicstaticvoidStraightSelectSortT(T[]array)whereT:IComparableT{for(inti=0;iarray.Length-1;i++){intminIndex=i;Tmin=array;for(intj=i+1;jarray.Length;j++){if(array[j].CompareTo(min)0){min=array[j];minIndex=j;}}if(minIndex!=i){array[minIndex]=array;array=min;}}}
直接选择排序是不稳定的。
3.2堆选择排序直接选择排序并没有把每一趟的比较结果保存下来，在后一趟的比较中，许多比较在前一趟已经做过了，但由于前一趟排序时未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作，因而执行的比较次数较多。
如果可以做到每次在选择到最小记录的同时，并根据比较结果对其他记录做出相应的调整，那样排序的总体效率就会非常高了。而堆选择排序是一种树形选择排序，是对直接选择排序的有效改进。堆选择排序算法是Floyd和Williams在年共同发明的，同时，他们也发明了“堆”这样的数据结构。
堆的概念：具有
个元素的序列
当且仅当满足
时称之为堆。
若关键码的集合
，把它们按照完全二叉树的顺序存放在一维数组中。
若满足且
则称作小根堆。若满足
且
则称作大根堆。
小根堆：int[]Key=newint[]{9,17,65,23,45,78,87,53,31,58,64};
图3小根堆大根堆：int[]Key=newint[]{94,93,75,91,85,44,51,18,48,58,10,34};
图4大根堆思想（以大根堆为例）：构建大根堆之后，输出堆顶记录，对剩余的
个记录接着构建大根堆，便可得到
个记录的次大值，如此反复执行，就能得到一个有序序列，这个过程称为堆选择排序。
堆选择排序需解决的两个问题：
问题1：如何建堆，对初始序列建堆的过程，就是一个反复进行筛选的过程。
（1）对一棵具有个结点的完全二叉树来说最后一个结点是第
个结点的子树。（2）筛选从第
个结点为根的子树开始，该子树成为堆。（3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。
即把序号为
，的记录作为根的子树都调整为堆。
问题2：输出堆顶元素后，如何调整新堆。
（1）设有个元素的堆，输出堆顶元素后，剩下
个元素。将堆底元素送入堆顶（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。（2）将根结点与左，右子树中较大元素进行交换。（3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复第二步。（4）若与右子树交换：如果右子树堆被破坏，即右子树的根结点不满足堆的性质，则重复第二步。（5）继续对不满足堆性质的子树进行上述操作，直到叶子结点，堆被重建成。
即：输出堆顶元素，将最后一个叶子结点放在堆顶，重新构建大根堆。
如：int[]Key=newint[]{45,34,78,12,34,32,29,64};
排序过程：
初始时：
建堆后：
图5构建大根堆堆重建后：
图6堆重建程序代码：
privatestaticvoidRestoreT(T[]array,intj,intvCount)whereT:IComparableT{//构建以结点j为根,一共有vCount个结点的大根堆while(j=vCount/2){intm=(2*j+1=vCountarray[2*j+1].CompareTo(array[2*j])0)?2*j+1:2*j;if(array[m].CompareTo(array[j])0){Ttemp=array[m];array[m]=array[j];array[j]=temp;j=m;}else{break;}}}///summary///堆选择排序////summary///typeparamname="T"需要排序记录的类型/typeparam///paramname="array"需要排序的记录集合/parampublicstaticvoidHeapSelectSortT(T[]array)whereT:IComparableT{intvCount=array.Length;T[]tempArray=newT[vCount+1];for(inti=0;ivCount;i++)tempArray[i+1]=array;//初建大根堆for(inti=vCount/2;i=1;i--)Restore(tempArray,i,vCount);//大根堆的重构与排序for(inti=vCount;i1;i--){Ttemp=tempArray;tempArray=tempArray[1];tempArray[1]=temp;Restore(tempArray,1,i-1);}for(inti=0;ivCount;i++)array=tempArray[i+1];}4.交换排序4.1冒泡交换排序
思想：通过相邻记录之间的比较和交换，使关键字较小的记录如气泡一般逐渐向上漂移直至水面。
如：int[]Key=newint[]{45,34,78,12,34,32,29,64};
程序代码：
///summary///冒泡交换排序////summary///typeparamname="T"需要排序记录的类型/typeparam///paramname="array"需要排序的记录集合/parampublicstaticvoidBubbleExchangeSortT(T[]array)whereT:IComparableT{for(inti=0;iarray.Length-1;i++){for(intj=array.Length-1;ji;j--){if(array[j].CompareTo(array[j-1])0){Ttemp=array[j-1];array[j-1]=array[j];array[j]=temp;}}}}
对冒泡排序常见的改进方法是加入一个标志性变量flag，用于标志某一趟排序过程是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。
程序代码：
///summary///改进的冒泡交换排序////summary///typeparamname="T"需要排序记录的类型/typeparam///paramname="array"需要排序的记录集合/parampublicstaticvoidBubbleExchangeSortImprovedT(T[]array)whereT:IComparableT{for(inti=0;iarray.Length-1;i++){boolflag=false;for(intj=array.Length-1;ji;j--){if(array[j].CompareTo(array[j-1])0){Ttemp=array[j-1];array[j-1]=array[j];array[j]=temp;flag=true;}}if(flag==false)break;}}4.2快速交换排序
快速交换排序是由图灵奖获得者TonyHoare（东尼.霍尔）所发展的一种排序算法，是采用分治策略的一个非常典型的应用。快速交换排序虽然高端，但其思想是来自冒泡交换排序的，冒泡交换排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速交换排序是比较和交换小数和大数，这样一来不仅小数冒泡到上面的同时也把大数沉到下面。
其基本思想如下：
（1）选择一个基准元素，通常选择第一个元素或者最后一个元素。（2）通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小，另一部分记录的元素值比基准值大。（3）此时基准元素在其排好序的正确位置。（4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。即：从待排记录中选一记录，将其放入正确的位置，然后以该位置为界，对左右两部分再做快速排序，直到划分的长度为1。
如：int[]Key=newint[]{45,34,78,12,34,32,29,64};
程序代码：
privatestaticvoidQuickSortT(T[]array,intleft,intright)whereT:IComparableT{//快速排序递归函数if(leftright){Tcurrent=array[left];inti=left;intj=right;while(ij){while(array[j].CompareTo(current)0ij)j--;while(array.CompareTo(current)=0ij)i++;if(ij){Ttemp=array;array=array[j];array[j]=temp;j--;i++;}}array[left]=array[j];array[j]=current;if(leftj-1)QuickSort(array,left,j-1);if(rightj+1)QuickSort(array,j+1,right);}}///summary///快速交换排序////summary///typeparamname="T"需要排序记录的类型/typeparam///paramname="array"需要排序的记录集合/parampublicstaticvoidQuickExchangeSortT(T[]array)whereT:IComparableT{QuickSort(array,0,array.Length-1);}
其实上面的代码还可以再优化，上面代码中基准元素已经在current中保存了，所以不需要每次交换都设置一个temp变量，在交换的时候只需要先后覆盖就可以了。这样既能较少空间的使用还能降低赋值运算的次数。
优化代码如下：
privatestaticvoidQuickSortImprovedT(T[]array,intleft,intright)whereT:IComparableT{//快速排序递归函数if(leftright){Tcurrent=array[left];inti=left;intj=right;while(ij){while(array[j].CompareTo(current)0ij)j--;array=array[j];while(array.CompareTo(current)=0ij)i++;array[j]=array;}array[j]=current;if(leftj-1)QuickSortImproved(array,left,j-1);if(rightj+1)QuickSortImproved(array,j+1,right);}}///summary///快速交换排序////summary///typeparamname="T"需要排序记录的类型/typeparam///paramname="array"需要排序的记录集合/parampublicstaticvoidQuickExchangeSortImprovedT(T[]array)whereT:IComparableT{QuickSortImproved(array,0,array.Length-1);}5.并归排序
我们首先先看两个有序序列合并的例子，如：
int[]Key1=newint[]{1,3,5,7,9};int[]Key2=newint[]{2,4,6,8,10,12,14}int[]temp=newint[Key1.Length+Key2.Length];
程序代码：
///summary///合并排序////summary///typeparamname="T"需要排序记录的类型/typeparam///paramname="array1"有序记录集合1/param///paramname="array2"有序记录集合2/param///returns合并后的有序记录集合/returnspublicstaticT[]MergeSortT(T[]array1,T[]array2)whereT:IComparableT{T[]temp=newT[array1.Length+array2.Length];inti=0,j=0,k=0;while(iarray1.Lengthjarray2.Length){if(array1.CompareTo(array2)0){temp[k++]=array1[i++];}else{temp[k++]=array2[j++];}}while(iarray1.Length){temp[k++]=array1[i++];}while(jarray2.Length){temp[k++]=array2[j++];}returntemp;}
我们接着看一个序列的并归排序。
首先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列构成，然后合并两个子序列，接着把子序列看成由两个有序序列组成……。倒过来看，其实就是先两两合并，然后四四合并……最终形成有序序列。该算法是采用分治策略的一个非常典型的应用，俗称2-路并归。
如：int[]Key=newint[]{45,34,78,12,34,32,29,64};
图7并归排序程序代码：
///summary///合并排序的递归合并函数////summary///typeparamname="T"需要排序记录的类型/typeparam///paramname="array"需要排序的记录集合/param///paramname="left"起点位置/param///paramname="mid"中间位置/param///paramname="right"终点位置/paramprivatestaticvoidMergeT(T[]array,intleft,intmid,intright)whereT:IComparableT{T[]temp=newT[right-left+1];inti=left;intj=mid+1;intk=0;while(i=midj=right){if(array.CompareTo(array[j])0){temp[k++]=array[i++];}else{temp[k++]=array[j++];}}while(i=mid){temp[k++]=array[i++];}while(j=right){temp[k++]=array[j++];}for(intn=0;ntemp.Length;n++){array[left+n]=temp[n];}}///summary///合并排序的递归分治函数////summary///typeparamname="T"需要排序记录的类型/typeparam///paramname="array"需要排序的记录集合/param///paramname="left"起点位置/param///paramname="right"终点位置/paramprivatestaticvoidMergeSortT(T[]array,intleft,intright)whereT:IComparableT{if(left=right)return;intmid=(left+right)/2;MergeSort(array,left,mid);//递归排序左边MergeSort(array,mid+1,right);//递归排序右边Merge(array,left,mid,right);//合并}///summary///合并排序////summary///typeparamname="T"需要排序记录的类型/typeparam///paramname="array"需要排序的记录集合/parampublicstaticvoidMergeSortT(T[]array)whereT:IComparableT{MergeSort(array,0,array.Length-1);}LSGOGroup
感谢您对团队的支持！