algorithms.md

算法相关

Q：冒泡排序的过程？

A：将待排序的数组想象成一排气泡，每一次从左往右扫描相邻的两个元素，如果发现左边的数比右边的大，就将它们交换位置，直到遍历完整个数组之后，如果是升序的话，最后一个元素就是最大值；接下来再对剩下的元素重复相同的过程，就能成功将这个数组排序

Q：稳定排序和不稳定排序是什么？快排为什么不稳定？

A：排序的稳定性是指，如果两个元素在比较时关键字相等，排序完成以后，它们在结果里的先后顺序还跟输入保持一致，那么就是稳定排序，如果不一致则是不稳定排序，常见的稳定排序有冒泡、插入、归并，不稳定的则有选择、快排、堆排序等；快排在做分区时会不停地把左右两边的元素成对交换，只要有两个相等元素被交换到对方位置，相对顺序就乱了，除非我们牺牲原地特性，把元素按照原次序拷贝到临时数组，否则快排天然就是不稳定的

Q：介绍一下插入排序的过程

A：插入排序就像打扑克，以最左侧元素下标 0 作为开始的基准，开始向右遍历，每次遇到一个新元素就像抽到一张新牌，就将它跟左边已经有序的区间内的元素从右到左逐个比较，遇到比当前元素大的就整体右移一格，直到找到小于等于当前元素的位置，然后插入；最坏和平均都是 n² 次比较和移动，但如果数据本来就几乎排好，只需扫描一次就结束，所以最佳是 O(n)；空间只用到一个临时变量，是原地排序，而且只在“大于”时移动，元素相等时不会互相跨越，因此是稳定的；在工程里，我通常把它用作其他复杂排序的小规模优化，比如快排分区块很小的时候改走插入排序，因为它对缓存友好、常数开销低

• 讲一下快速排序的思想

• 快排的时间复杂度是多少

• 在什么情况下快排的时间复杂度最差