• 编程思想板块最主要的内容是数据结构经典题目及解答题目所需的编程思想，愿对您能有所帮助

七、排序

1. 对n个整数进行排序，要求时间复杂度为O(n)，空间复杂度为O(1)？

算法思路：假设待排序整数的范围为0~65535，设定一个数组int count [65535]并初始化为0，则所需空间与n无关，为0(1)。扫描一遍待排序列x[]，count[X[i]]++,时间复杂度为O(n);再扫哦9描一次count[]，当count[i]>0时，输出count[i]个i，排序完毕所需的时间复杂度也为O(n);故总的时间复杂度为O(n),空间复杂度为O(1)。假如有负整数可以给所有整数都加上一个偏移量，使之都变成正整数，再使用上述方法即可

2. 若关键字类型没有比较运算符，可事先定义宏或函数表示比较运算

3. 对于判断是否是大/小根堆的题一般用将顺序表视为一个完全二叉树，此时需对数组长度分为两种情况判断：

①　若len为偶数，则有一个单分支节点，则需先判断单分支节点再判断所有双分支节点

②　反之直接判断所有双分支结点

1）答题（画图）格式

答题（画图）格式
直接插入排序
希尔排序
归并排序
基数排序
快速排序（若题目选取中间结点则写一句：把其与第一个元素换位再写下如图步骤）
冒泡排序	（已排好的数不再写出）
堆排序	（不是画树！）
直接选择

2）折半插入排序

1. 注意：

①　一直到low>high才停止查找

②　当mid所指元素等于当前元素时，应继续令low=mid+1,以保证“稳定性，最终将当前元素插入到low所指位置（即high+1）- 与折半查找的不同之处

3）冒泡排序

1. 添加判断是否发生交换元素的flag，若某一次遍历后没发生交换则说明表已有序即退出循环

4）排序经典题目的编程思想

1. 编写双向冒泡排序算法，在正反两个方向交替进行扫描，即第一趟把关键字最大的元素放在序列的最后面，第二趟把关键字最小的元素放在序列的最前面，如此反复进行

算法思想：

这种排序方法又称双向起泡。奇数趟时，从前向后比较相邻元素的关键字，遇到逆序即交换，

直到把序列中关键字最大的元素移动到序列尾部。偶数趟时，从后往前比较相邻元素的关键字,遇到逆序即交换，直到把序列中关键字最小的元素移动到序列前端

2. 试编写一个算法，使之能够在数组L[1..n]中找出第k小的元素(即从小到大排序后处于第k个位置的元素)

算法思想：

从数组L[1..n]中选择枢轴pivot (随机或直接取第一个)进行和快速排序-样的划分操作后，表L[1..n]被划分为Ll[1...m-1] 和L[m+1..n]，其中L(m) =pivot

讨论m与k的大小关系:

①　当m=k时，显然pivot就是所要寻找的元素，直接返回pivot即可

②　当m

③　当m>k时，所要寻找的元素一定落在L[1..m-1]中，因此可对L[1..m-1]递归地查找第k小的元素

3. 已知由n(n≥2)个正整数构成的集合A={a}0≤k