快速排序优化方法php

手机

电脑

首先随机找出一个数（通常就拿数组的第一个数就行），把它插入一个位置，使得它左边的数都比它小，右边的数都比它大，这样就将一个数组分成了两个子数组，然后在按照同样的方法把子数组分成更小的子数组，直到不能分解为止。用比较通俗的话：挖坑填数+分而治之。

快排的一个关键因素是选好枢轴，它进行一趟排序后，枢轴元素在表中的位置被唯一确定下来，且枢轴元素将待排序列分成两个子序列，左边的序列中的元素都比 枢轴元素小，右边的序列都比枢轴元素大。然后，分别在左右序列中选择枢轴元素再开始排序，因而，快排中包含了递归。

当待排的元素初始有序时，快排的性能大大地下降。因为此时枢轴划分的子序列严重地不对称（一般选择第一个元素作为枢轴记录），快排退化为冒泡排序。

快排是不稳定的，因为在排序过程中，设置了两个指针 low 和 high 。首先从high 开始自减，寻找第一个比枢轴小的元素，并将之与枢轴记录进行交换，这种跳跃式的交换可能会造成元素的相对位置的改变。

最后就是对于快排而言，元素的初始序列与排序的趟数和比较次数是有关的。但是，平均情况下，对于内部排序而言，快排的性能是最好。平均时间复杂度为 O（n^2)，空间复杂度为O（logn）。