快速排序及其优化方法如何为一个？

快速排序 每次从当前考虑的数组中选一个元素，把这个元素想办法挪到应该排好序的位置，比如4这个元素，它就有一个性质4之前的元素都是小于它的，之后的元素都是大于它的，之后我们要做的事情是对小于4和大于4的数组分别继续使用快速排序的思路，逐渐递归下去完成整个排序过程。 对于快速排序如果把选定的元素挪到正确的位置的过程也是快速排序的核心，在这个过程中我们通常选择数组第一个元素为我们分界的标志点，我们记录这个点为 l ，之后我们逐渐的遍历右边所有没有被访问的元素，在遍历的过程中我们逐渐整理一部分是小于v这个元素的，一部分是大于v这个元素的，当让我们要有个记录那个是小于v和大于v的分界点，这个点为 j ，而当前访问的元素记录为 i。 我们如何来决定当前的元素要怎样变化才能维持当前的性质，如果当前的元素e是比v还要大的，那么他直接就放在大于v一部分的后面。 然后就考虑下一元素就好了。 如果当前的元素e是比v还要小的。 我们只需要当前橙色部分也就是j所指的位置的后一个元素和当前做考察的元素 i进行一下交换 。 之后我们进行一下位置维护 ++j，++i。 以此类推，整个数组分成三个部分，第一个元素是v，橙色部分小于v，紫色部分大于v。 最后我们需要做的是把数组 l这个位置和数组j这个位置进行交换，这样整个数组就形成了我们设想的那样，前面小于v，后面大于v。 优化 对于小规模数组, 使用插入排序进行优化； 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot。在快速排序递归过程中分成的子树不能保证每次都是平均的将整个数组一分为二，换句话来说分成的子数组可能是一大一小的。