算法分类
10种常见的排序算法可以分为两大类：
比较类排序：也称为非线性时间比较类排序，因为比较决定了元素之间的相对顺序，其时间复杂度无法突破o(nlogn )。 非比较类排序：也称为线性时间非比较类排序，因为比较不确定元素之间的相对顺序，突破了基于比较排序的时间下限，可以在线性时间上执行。内部排序要求数据元素全部在内存完成排序，且顺序存储。
1 .直接插入排序一条插入排序的基本步骤R[1…i-1]中查找R[i]的插入位置，r [ 1…j ].key=r [ I ].keyr [ J1…I-1 ].key； Rj 1…i-1] )的所有记录向后移动一个位置； 将R[i]插入R[j 1]的位置。 利用直接插入排序(基于顺序搜索)顺序搜索实现在r[1…i-1]中搜索r[i]的插入位置，从r[i-1]向前顺序搜索，监控哨设置在r[0]；
r[0]=r[i]；
for(j=I-1； r[0].keyr[j].key； j )
循环结束表示r[i]的插入位置为j 1
那些关键字在r[i].key以上的记录在搜索的同时向后移动；
for(j=I-1； r[0].keyr[j].key； j )
r[j 1]=r[j]；
上述循环结束后，可以直接进行“插入”
r[j 1]=r[0]
要插入排序过程：
voidinssort (记录类型[ ]，int length ) {int i，j； for(I=2； I=长度； I({r[0]=r[I]； //将预定插入的记录保存在监视哨r[0]中的j=i-1； while(r[0].keyr[j].key ) ) {r[j 1]=r[j]； j----； }r[j 1]=r[0]； //将要插入的记录插入到已排序序列中}算法分析(1)关键字在记录序列中按顺序排序。
比较次数n-1
移动次数0
)2)关键词按记录顺序反向排列。
比较次数(n 2) n-1 )/2
移动次数(n 4) n-1 )/2
时间复杂度： o(n2 )、空间复杂度： o ) )1) )。
值相等的插入位于原始位置，不更改原始顺序。 因此，直接插入顺序为稳定。
2 .希尔排序又称缩小增量排序，由基本思想(对排序记录序列进行“宏”调整，进行“微观”调整。 “宏”调整是指“跳转表达式”的插入顺序。
具体而言，将记录序列分成几个子序列，并插入排序各个子序列。
例： 46 55 13 42 94 17 05 70
首先，将序列分为n/2个子序列，即4个子序列。 下标分别为0、4、1、5、2、6、3、7，第一个子序列为46、94，第二子序列为55、17，第三个子序列为13、05，第四个子序列为42、
必须分别插入和排序四个子序列，第二子序列和第三子序列是逆序的，并且必须互换顺序。
接着，将序列分为n/4个，即2个子序列，记录下标为0、2、4、6和1、3、5、7。 分别插入这两个子序列进行排序，得到05 17 13 42 46 55 94 70，
最后，插入间隔为1的子序列进行排序。
算法实现：
voidshellinsert(sqlistL，int dk )/dk在步骤for ) I=dk1； i=L.length； I ) if (l.r [ I ].keyl.r [ I-dk ].key ] { l.r [0]=l.r [ I ]； for(j=I-dk； J0(L.R[0].Keyl.R[J].Key )； j-=dk(L.R[Jdk]=L.R[J]； L.r[j dk]=L.r[0]； }voidshellinsert(sqlistL，intdelta )，int t ) (delta )是增量数组，dk的delta数组的长度for(k=0； kt； t )外壳插件(l，delta[k]； )算法分析在希尔排序开始时，递增较大，分组后仍为比较多，各组记录为http://www.Sina.com
递增数目少后，组数也为逐渐减小，各组记录数为逐渐减少。
希尔排序有效地直接插入排序，大大改进了。 对于直接插入排序，比较的步骤为1。 在这种情况下，如果较小的数据位于序列的后面部分，则必须一步一步向前移动，无疑会变慢。 步骤>； 如果采用1的方法，由于向前推进较小的数量是“飞跃”的，所以可以提高排序效率。
在很多情况下，使用每次递增除以二以递减的方法，最终的时间复杂度仍然是O(n2 )。
因此，间隔为2K-1的子序列由间隔为2K的子序列组成。
每次对子序列进行排序时，它们的数量都位于奇数位置，小数位于偶数位置。
整个序列还没有基本达成
序状态，导致最后一次对整个序列进行直接插入排序时效率大幅度降低。Hibbard提出的增量序列{2k-1,2k-1-1,7,3,1}：O(n1.5)
增量每次除以3的递减方法：O(n1.5)
空间复杂度：一个辅助空间
稳定性：不稳定
交换类排序
3. 冒泡排序又称相邻比拟法排序或起泡排序，在扫描待排序记录时，顺次比较相邻的两个记录的关键字大小，如果逆序就交换，直到所有记录都排好序为止。
第一次排序结束之后，最大的数会排到最后一个位置。
时间代价：
冒泡排序的时间代价“比较”次数“移动”次数最好的情况（关键字在记录序列中顺序有序）：O(n)
只需进行一趟起泡n-10最坏的情况
（关键字在记录序列中逆序有序）：
需进行n-1趟起泡n(n-1)/2n(n-1)/2
冒泡排序只需要一个辅助空间，所有空间复杂度为O(1)。
4. 快速排序改进冒泡排序中一次交换只能消除一个逆序的特点，即实现一次交换消除多个逆序。
基本思想：找一个一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录，均移动至该记录之前；凡其关键字大于枢轴的记录，均移动至该记录之后。
即对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。
例如，序列48 62 35 77 55 14 35 98
先选取48作为“枢轴”，然后low,high指针分别指向序列的两头48和98，然后从high开始和48比较，如果大于，就不变，向前移动一位；如果小于，就把数值换到low指向的位置，然后low向后移动，以此类推。。。直到low和high指向同一个位置（交汇处），然后将r[0]放到交汇处，就完成了一趟排序。
一趟排序之后：
最好情况：每趟排序将序列一分两半，类似于折半查找。时间复杂度为O(nlog2n)。
最坏情况：原序列有序，每次分割都会将剩余记录全部分到一个序列中，而另一个序列为空。
比较次数为∑i=1n-1 n-i = n(n-1)=O(n2)
时间复杂度为：O(n2)
平均情况为：
空间复杂度：
需要log2n个辅助空间记录枢轴位置，所以空间复杂度为O(nlog2n)，不稳定。
快速排序通过分治的策略，交换两个不相邻的元素，一次可以消除多个逆序，是目前为止最快的一种排序算法。
5. 选择类排序算法 基本思想选择类排序算法的基本思想是从n个元素中选出一个最大（小）元素，把它调到序列末（前）端，再从剩下的n-1个元素中选出最大（小）元素……反复如此，直到只剩一个元素时，就完成了排序。
常见的选择类排序算法有：简单选择排序，树型选择排序，堆排序。
举例：序列48 62 35 77 55 14 35 98
用i记录当前位置的下标，k记录最小的元素下标，j指向待比较元素的下标。一趟比较之后，最小的元素排到了最前的位置。
有n个记录的序列中，要进行n-1次扫描。
和冒泡排序相比，简单选择排序数据交换的次数得到大幅度减少，在一定程度上提升了排序的效率。
算法分析 时间性能分析简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排序情况无关。
对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为：
∑i=1n-1(n-i) = n(n-1)/2
对交换次数而言，最好情况是记录正序，无需交换；最坏情况是记录逆序，需要n-1次交换。
简单选择排序和冒泡排序一样，时间复杂度都是O(n2)
简单选择排序需要2个辅助存储空间，一个记录最小位置，一个用于数据交换缓存，因此空间复杂度为O(1)。
稳定性分析从简单选择排序的过程来看，记录交换是跳跃式进行的，因此简单选择排序是不稳定的。
从以上排序过程可以看出，在包含有n个记录的序列中，需要进行n-1趟扫描，在第i次扫描的过程中，要进行n-i-1次比较。虽然比较次数还是比较多，交换次数明显减少了。
5.2 树形排序也被称为锦标赛排序。
基本思想与体育比赛时的淘汰赛类似：
首先将n个对象的排序码进行两两比较，得到n/2个比较的优胜者，作为第一步比较的结果保留下来；
然后对这n/2个对象再进行排序码的两两比较，……如此重复，直到选出一个排序码最小的对象为止。
一颗包含n个结点的完全二叉树，当二叉树不满时，用关键字为∞的结点填满，选出的最小关键字就是这颗树的根结点。在输出了最小关键字之后，为了选择次小关键字，将最小关键字记录所对应的叶子结点的关键字置为∞。
叶子结点和其兄弟结点的关键字比较，修改从该叶子结点到根结点上各结点的值，则根结点的值被修改为次小的关键字。直到左右的结点输出为止。
下面举例图解一下，
首先两两比较，选出n/2个较小的结点，
再两两比较，选出两个较小的记录，
最后，这两个较小的比较，选出最小的13，
这个过程也是一棵完全二叉树的构建过程。二叉树的深度是logn+1，叶子结点数目n-1。
第二次比较的时候需要将上一次选出的最小的记录改为∞，只需要修改∞的那一条比较，所以需要比较logn次就可以得到次小的记录，以此类推。。。
树形选择排序减少了不同记录之间的比较次数，但是程序运行所需要的空间较多。
性能分析树形排序构成是一棵完全二叉树，其深度为log2n，其中n为待排序元素个数。
比较分析：
第一轮，n-1次；
其他轮次，log2n次。
时间复杂度为：O(nlog2n)。
空间复杂度：增加了n-1个结点存放中间比较结果。
树形选择排序是一种稳定的排序。
6. 堆排序堆是借助于完全二叉树提出的一种新的数据结构，堆是满足下列特性的完全二叉树，当一个数列满足下列性质时，我们称它为小顶（根）堆或大顶（根）堆。
性质：
堆是每个非叶子节点值都大于或等于其儿子值的完全二叉树。
归并排序，也称为合并排序，也就是将两个或两个以上的有序表逐趟进行合并，并最终合成一个新的有序表的排序方法。
这里主要介绍二路归并排序算法。
假设初始序列含有n个记录，则可看成是n个有序的子序列；每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1有序的子序列，再两两归并，……如此重复，直至得到一个长度为n的有序序列为止。这种排序方法称为2-路归并。
通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。
整个归并排序过程只需要log2n趟。
递归形式的2-路归并排序算法：
void MSort(RecordList L,RecordList CopyL,int left,int right){int middle;if(left<right){middle=(left+right)/2;MSort(L,CopyL,left,middle);MSort(L,CopyL,middle+1,right);MSort(L,CopyL,right,middle);}} 算法分析 时间复杂度：一趟归并排序的时间复杂度为O(n)。
在归并排序算法中，递归深度为O(log2n)，记录关键字的比较次数为O(log2n)。
算法总的时间复杂度为O(nlog2n)。空间复杂度
归并排序占用附加存储较多，需要一个与原待排序记录数组同样大小的辅助数组。稳定性
每次都是从左半部开始进行归并，且当左半部分的关键字与右半部的关键字相等时左半部优先，因此归并排序算法是稳定的。 8. 基数排序
链式基数类排序就是典型的分配类排序。
多关键字排序
最高位优先MSD法
先按花色将整副牌分成按花色分成4组，然后每组再按照面值从小到大进行排序，最后再将这4组牌收集到一起。
最低位优先LSD法（分配和收集交替进行）
首先按照面值从小到大把整副牌分成13组，然后将每组牌按面值大小收集到一起，再对这些牌按花色摆成4组，每组13张牌，最后把这4组牌按花色的次序收集到一起。
链式基数排序
按照数字的某一位进行排序，相同的按原来先后顺序进行排列，然后依次往后排。
可以采取顺序存储和链式存储两种方式进行；采取顺序存储方式时，所需要的时间和空间都很大；一般都用链表作存储结构，即链式基数排序。
效率分析在进行基数排序时，如果每个关键字有d位数字，需要重复执行d趟“分配”与“收集”操作。每趟对n个对象进行“分配”，对r个队列进行“收集”。因此总时间复杂度为O(d(n+r))。
如果基数r相同，对于对象个数较多而关键字位数较少的情况，使用链式基数排序比较好。
n个待排序记录序列，每个记录都有一个next域，再加上r个对了的队尾域，基数排序需增加n+r个附加链接指针。因此，空间复杂度时O(n+r)。
基数排序每次都以上一趟的结果为基准，因此基数排序是稳定的排序方法。
先整理这些吧，有需要再更新吧。。。