算法面试题

排序算法

1）冒泡排序（O(N^2)）

循环数组，对比相邻两个数据，前面的数据大于后面的数据则交换位置，否则不变。循环一遍之后，最小的数据会在最前面，数组长度-1，从第二个位置继续循环数组，重复上面过程。

2）选择排序（O(N^2)）

选择排序是对冒泡排序的优化，在冒泡排序中，每次满足条件都要交换数据位置，在选择排序中，每次循环找到当前循环最小的数据，存储在临时变量中，循环完成之后与第一个数据交换，之后从第二个数据开始，重复这个操作。

3）插入排序（O(N^2)）

将数据插入到一个有序数列中，当数据是无序的，我们需要将第一个数据当成有序数列，将后面的数据依次插入。

4）希尔排序（O()）

将数据按一定间隔分成多个数组，对每个数组进行插入排序。

5）归并排序

6）快排（O(n*logn)）

①先随机找一个基准数，一般以最后一位为基准数。

②分区，将比基准数小的放到左边，比它大的放到右边。

③重复第二步直到每个区间只有一个数。

第二步详细步骤：https://www.runoob.com/w3cnote/quick-sort.html

关于排序中插入排序使用率远超过冒泡排序的原因

参考：https://zhuanlan.zhihu.com/p/147678685

两者时间复杂度都是O（n^2）

这里引入一个概念：原地排序

原地排序算法：指空间复杂度为O（1）的排序算法，空间复杂度为O（1）代表不需要额外的空间或需要少量的额外空间

如何评价一个算法？

• 最好情况，最坏情况，平均情况时间复杂度
• 时间复杂度的系数，常数，低阶
• 比较次数和交换（移动）次数
• 内存消耗
• 稳定性：指数组中存在值相等的数据，在排完序之后仍保持原来的顺序

在两种排序有相同的时间复杂度的情况下，其余情况就是要考虑的，从以上几个方向分析这两种排序算法，首先，他们都是原地排序算法，冒泡排序只需要一个额外的空间，插入排序也只需要一个额外的空间，从稳定性方面来分析，冒泡排序因为每次对比都需要交换元素位置，所以稳定性不强，而插入排序只在合适的情况下才进行交换，所以稳定性很强。