10.09面试题目记录

艾融软件 - 线上面试题

排序算法的时间复杂度

O(n^2）：冒泡，选择，插入
O(logn）：折半插入排序
O(nlogn)：希尔，归并，快速，堆
O(n+k)：桶，计数，基数
（K表示桶的个数）

聚合函数

什么是聚合函数？ 聚合函数作用于一组数据，并对一组数据返回一个值。
聚合函数：AVG() SUM() MAX() MIN() COUNT()

相关知识点

排序算法的稳定性

在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
稳定的排序：冒泡排序、直接插入排序、折半插入排序、归并排序
不稳定的排序：堆排序、快速排序、希尔排序、直接选择排序

排序算法的时间复杂度

1）一重循环的时间复杂度为O（n），两重循环的时间复杂度为O（n^2）， 三重循环的时间复杂度为 O（n^3），依次类推；
2）二分的时间复杂度为O（logn）；
3）一个循环里套一个二分的时间复杂度为O（nlogn）。

排序算法的思想

• 冒泡排序：需要进行n-1轮排序，第i轮排序中将从第0个元素到第n-i-1个元素进行两两比较将该轮排序中的最大值一步一步移动都最后的位置。
• 插入排序： 先假定序列中第0个元素是有序的，从序列中第1个元素开始遍历，将遍历取出的元素与其前面已经排好序的元素进行比较将其插入到有序序列中的合适位置。
• 快速排序：先从序列中挑出第一个元素作为后期比较的基准。将所有比基准小的元素摆放在基准的左边，所有比基准大的元素摆放在基准的右边，所有和基准相同的元素摆放在基准的任一边。在这个分区结束之后，该基准就处于序列的中间位置。递归地把左分区的元素和右分区的元素再进行排序。
• 选择排序：就是不断地从未排序的元素中选择最大（或最小）的元素放入已排好序的元素集合中，直到未排序中仅剩一个元素为止，一般假定第一个元素是最小值
• 希尔排序：先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了
• 归并排序：将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组
• 堆排序：把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换….如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了
• 基数排序：先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小进行排序
• 计数排序：就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。
• 桶排序：把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，最后将桶进行汇总排序。