Question

快速排序是原地排序么

Answer 1

快速排序是原地排序。

快速排序是一种原地排序，只需要一个很小的栈作为辅助空间，空间复杂度为O(logN)，所以适合在数据集比较大且无序的时候使用。实现方法有经典快排和双指针快排。

快速排序也是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。

快速排序和归并排序是互补：

归并排序是将数组分成两个子数组分别排序，并将有序数组归并，这样数组就是有序的了；而快速排序将数组通过切分变成部分有序数组，然后拆成成两个子数组，当两个子数组都有序时整个数组也就有序了。

归并排序的递归调用发生在处理数组之前，快速排序的递归调用是发生在处理数组之后。