牛客网习题总结二
解题思路：
排序算法中比较次数与初始元素序列排序无关的只有选择排序和基数排序，其他的都有关。
解题思路：
一般来说：(Top K问题)找出N个数据中前K大(小)的K个数， 选堆排
因为堆排序来解决 Top K 问题并不需要全部排序， 只需要维护一个大小为K的最大(小)堆。它的时间复杂度为O(nlogK)
解题思路：
一个整型常量放到一个字符变量中，实际就是把以该整型常量表示的ASCII码放到内存单元中。（ASCII码是以十进制整数表示的）
将一个字符常量放到一个字符变量中，实际上并不是把该字符本身放到内存单元中去，而是把该字符的相应ASCII代码放到存储单元中。
char i = 1;则i的ASCII就是1，在内存中就是0 0 0 0 0 0 0 1
char i = ‘1’;则i的ASCII就是字符‘1’的ASCII码49，就是0 0 1 1 0 0 0 1
上面是int和char的区别，它们的联系就是存储形式类似，就是一个是4个字节，一个是2个字节。int 可以用字符常量赋值，char也可以用整型常量赋值，它们之间的桥梁就是ASCII码，因为字符是与ASCII一一对应的。
解题思路：
D、归并排序：由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归深度为log2n的栈空间，
因此空间复杂度为O(n + logn)
解题思路：
数组可以实现顺序遍历但是插入删除操作复杂，平均移动n/2个元素
链表因为存储的地址不连续（逻辑上连续实际上不连续），可以实现顺序遍历
哈希表是随机存储，所以是离散分布，顺序遍历实现不了
队列只可以在队尾插入队头删除，不可以实现中间插入和删除，不满足条件
综上，链表最合适
解题思路：
B答案等号右面表示的内容是三行两列，与定义的两行三列矛盾，故选B
解题思路：
实际求的是对角线A[i][i]前面有多少元素，从0行开始到第i行是递增序列
- 第0行，一个元素
- 第1行，两个元素
- 第2行，三个元素
- ……第i行，i+1个元素
等差数列求和公式：Sn=na1+n(n-1)d/2 经过代入整理得出：i(i+3)/2+1个元素，由于从0开始存储，所以i(i+3)/2，最终选A。
解题思路：
ABC
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法
解题思路：
A. 计数排序是一种基于 统计 的排序算法，错误。
B. 需要遍历所有数据，时间复杂度 O(N) ，但最后输出排序后的序列更合理，设 k 为数据范围（最大值 - 最小值），则遍历标记数组需要 O(k) ，总共 O(N+k) 。
C. 当数据范围是 k 时，空间复杂度 O(k) 。
D. 原地排序是指不申请多余空间排序，松一点的说法是可以用很小的固定的辅助空间。但计数排序需要一个标记数组（或者 hash map）辅助统计，这个数组大小与数据范围大小相关，因此计数排序不是原地的。