编程思想板块最主要的内容是数据结构经典题目及解答题目所需的编程思想，愿对您能有所帮助
- 对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)。假如有负整数可以给所有整数都加上一个偏移量，使之都变成正整数，再使用上述方法即可
-
若关键字类型没有比较运算符，可事先定义宏或函数表示比较运算
-
对于判断是否是大/小根堆的题一般用将顺序表视为一个完全二叉树，此时需对数组长度分为两种情况判断：
① 若len为偶数，则有一个单分支节点，则需先判断单分支节点再判断所有双分支节点
② 反之直接判断所有双分支结点
1）答题（画图）格式
希尔排序
归并排序
基数排序
快速排序（若题目选取中间结点则写一句：把其与第一个元素换位再写下如图步骤）
冒泡排序
（已排好的数不再写出）
堆排序
（不是画树！）
直接选择
2）折半插入排序
- 注意：
① 一直到low>high才停止查找
② 当mid所指元素等于当前元素时，应继续令low=mid+1,以保证“稳定性，最终将当前元素插入到low所指位置（即high+1）- 与折半查找的不同之处
3）冒泡排序- 添加判断是否发生交换元素的flag，若某一次遍历后没发生交换则说明表已有序即退出循环
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<k时，所要寻找的元素一 定落在L [m1..n]中，因此可对L [m+1..n]递归地查找第k- m小的元素
③ 当m>k时，所要寻找的元素一定落在L[1..m-1]中，因此可对L[1..m-1]递归地查找第k小的元素
3. 已知由n(n≥2)个正整数构成的集合A={a}0≤k<n},将其划分为两个不相交的子集A[和A2,元素个数分别是n;和M2,A1和A2中的元素之和分别为S和S2。设计一个尽可能高效的划分算法，满足|n1- n2|最小且|S1- S2|最大
分析：
① |n1- n2|最小：分的均匀
② |S1- S2|最大：大小分离
算法思想：
由题意知，将最小的Ln/2个元素放在A中，其余的元素放在A2中，分组结果即可满足题目
要求。仿照快速排序的思想，基于枢轴将n个整数划分为两个子集。根据划分后枢轴所处的位置i分别处理:
① 若i=向下取整（Ln/2）,则分组完成，算法结束
② 若i<向下取整（Ln/2）, 则枢轴及之前的所有元素均属于A1,继续对i之后的元素进行划分
③ 若i>向下取整（Ln/2）,则枢轴及之后的所有元素均属于A2,继续对i之前的元素进行划分
4. 有一种简单的排序算法，称为计数排序( count sorting).这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某个记录统计出的计数值为C，则这个记录在新有序表中的合适存放位置即为C。与简单选择排序相比较，这种方法是否更好?为什么?
简单选择排序算法比本算法好。简单选择排序的比较次数是n(n-1)/2，且只用一个交换
记录的空间;而这种方法的比较次数是n^2，且需要另一数组空
5. 设有一个数组中存放了一个无序的关键序列K1, K2,...Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n
6.
