排序算法总结及习题一、概述排序是最基础和常用的算法之一，一般情况下，排序不开比较、数据交换，怎样降低算法的时间及空间复杂性是算法设计的目标，尽管经典算法已有不少，但研究一直不断，2001年还有综合性能很好的新算法出现
为了对n个元素的线性表进行排序，至少必须扫描一遍以获取n各元素，因此排序问题的计算复杂性下界为：Ω(n)如果对输入的数据不做任何要求，则仅能通过比较来确定输入序列各元素间的顺序
无论算法采用怎样的比较策略/顺序，总能对应一个两两比较序列，考察所有可能则可对应一棵决策树
例如：a1:a2()(a1a2)(a2a1)树的非叶子结点表示一次比较，叶子结点对应一个可能的结果队列
显然树高度为比较次数
可以为任意的输入，叶子结点数目为n
高度最小情况为满二叉树，则2h=n
一般情况下：2h>=n
,则h>=log2n
>log2(n/e)n=nlogn-nloge则任意分布数据，算法复杂性下界：Ω(nlogn)二、常用基本算法及思想名次排序、冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序
名次排序（1）计算名次voidRank(Ta[],intn,intr[]){//计算a[0:n-1]中n个元素的排名for(inti=0;i
