po一张复杂度先：
一些总结：
总排序趟数与初始状态无关的有：（除了快速排序和优化的冒泡，其他都是）
算法复杂度与初始状态无关的有：堆排序、归并排序、选择排序、基数排序。
元素总比较次数与初始状态无关的有：选择排序、基数排序。
元素总移动次数与初始状态无关的有：归并排序、基数排序。
直接插入排序属于稳定的排序，最坏 时间复杂性 为O(n^2)， 空间复杂度 为O(1)。 最好情况下的时间复杂度为 O(n)。
------题目------
将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是()
A、NB、2N-1
C、2N
D、N-1
解析：无论如何，两个N表最后必然至少有一个要全部离开，也就是说，理论上的最少比较次数为最短的那个表的长度。当且仅当最短表的数据都小于另一个表中任意数据时，比较次数可以取到理论最小值=最短表的长度。
在待排序的元素序列基本有序的前提下，效率最高的排序方法是______ 。
A、插入排序
B、选择排序
C、快速排序
D、归并排序
解析：直接插入排序是数据越有序越快，最快时间复杂度可达到O(n) .
选择排序无论何时都是O（n^2）
快速排序越有序越慢，它要从后到前遍历找比基准小的，时间复杂度达到O(n)
排序趟数与序列的原始状态有关的排序方法是()排序法
A、插入
B、选择
C、优化的起泡
D、快速
解析：首先区分两点 ：1.比较次数和比较趟数 2.比较的次数是与时间复杂度有关的，比较的趟数是一遍比较完接着一遍的遍次。比较的次数与排列顺序无关相当于在最坏最好一般情况下时间复杂度不变，总共有: 堆排序，归并排序，选择排序，基数排序。而此题问的是趟数，则插入和选择无论怎么样，趟数始终无影响，改良的冒泡对相等以及排好序的不在进行排序，趟数大大减少。插入排序和选择排序不管序列的原始状态是什么都要执行n-1趟。
http://www.cnblogs.com/Xieyang-blog/p/8340578.html
对关键码序列28,16,32,12,60,2,5,72快速排序,从小到大一次划分结果为()
A、(2,5,12,16)28(60,32,72)
B、(2,16,5,12)28(60,32,72)
C、(2,16,12,5)28(60,32,72)
D、(5,16,2,12)28(32,60,72)
解析：原始为：28 16 32 12 60 2 5 72
i是左到右找小于28数，j是右到左找小于28数，j先动。
j找到5，i动找到32。两者互换。有：28 16 5 12 60 2 32 72
j找到2，i找到60互换有：28 16 5 12 2 60 32 72
j i相遇，i和28换位子：2 16 5 12 28 60 32 72
下列排序法中，每经过一次元素的交换会产生新的逆序的是（ ）
A、快速排序
B、冒泡排序
C、简单插入排序
D、简单选择排序
解析：在数据元素的序列中，对于某个元素，如果其后存在一个元素小于它，则称之为存在一个逆序。冒泡排序只交换相邻元素，但不是每次移动都产生新的逆序。简单插入排序每一次比较后最多移掉一个逆序。快速排序每一次交换移动都会产生新的逆序，因为当不会有新的逆序产生时，本轮比较结束。简单选择排序的基本思想是先从所有 n 个待排序的数据元素中选择最小的元素，将该元素与第一个元素交换，再从剩下的 n-1 个元素中选出最小的元素与第 2 个元素交换，这样做不会产生逆序。