经常使用快速排序是因为在同样是O(N*logN)的几种排序方式中排序效率更高，加上快速排序的思想----分而治之也是真的很实用，所以在很多笔试面试中出现的几率都很高。quicksort直接直接写出来还是有难度的，一定要弄清楚原理再背，不能死记硬背。快速排序是C.R.A.提出的分区交换排序。霍尔于1962年采用分而治之的策略，俗称分而治之（Divide-and-Conque）。最常见的实现方法是“填坑法”。它的实现步骤是：选择数组的头元素作为枢轴元素，记住这个位置索引，相当于一个“坑”。设置left和right两个指针，分别指向序列最左边和最右边的两个元素。接下来，从右指针开始，将指针指向的元素与引用元素进行比较。如果大于枢轴，则右指针向左移动；如果小于pivot，则将指向的元素放到index对应的位置。将之前放入坑中的元素（右指针移动前指向的元素）的位置赋值给index，使这个位置成为新的“坑”，同时左指针向右移动一位。接下来切换到左指针进行比较。如果left当前指向的元素小于pivot，则left指针向右移动；如果元素大于pivot，则将元素放入坑中，并将left指向的位置赋值给index，使其成为一个新的“坑”，同时right指针向左移动一位。重复步骤3、4、5，直到左等于右，将轴放在左右重合的位置。此时数组中小于pivot的元素在pivot的左边，大于pivot的元素在pivot的右边。得到pivotIndex的pivotIndex，划分控制，对pivotIndex左右的子序列分别重复上述1到6的步骤，直到子序列不能再分裂，整个序列就是一个从一开始递增的序列。具体代码实现如下：=$left){//右指针从右向左移动，如果当前值小于参考值，则将当前元素放入坑中，当前元素的位置变为a新坑。Left向右移动一个位置，然后切换到左侧进行比较。否则right向左移动一位，继续使用新元素的值与Pivot值进行比较while($right>=$left){if($arr[$right]<$pivot){$arr[$dataIndex]=$arr[$right];$dataIndex=$right;$左++；休息;}$对--;}//左指针从左向右移动，如果当前值大于参考值，则将当前元素放入坑中，当前元素成为新的坑，right向左移动一个位置，切换到right进行比较，否则left向右移动一个位置并继续与参考值比较while($right>=$left){if($arr[$left]>$pivot){$arr[$dataI索引]=$arr[$left];$dataIndex=$left;$对--;休息;}$左++;$arr[$dataIndex]=$pivot;返回$dataIndex;}publicfunctionquickSort(&$arr,$startIndex,$endIndex){//当startIndex大于或等于endIndex时递归结束if($startIndex>=$endIndex){return;}$pivotIndex=$this->partition($arr,$startIndex,$endIndex);$this->quickSort($arr,$startIndex,$pivotIndex-1);$this->quickSort($arr,$pivotIndex+1,$endIndex);}}$quickSortClass=newquickSortClass();$arr=[72,6,57,88,60,42,83,73,48,85];$quickSortClass->quickSort($arr,0,count($arr)-1);变量转储（$arr）；填坑公式如下：1.$left=strart;$右=结束；$pivot=$arr[$left];第一个坑是$arr[$left]2。$right--从后往前找一个小于$pivot的数，挖出这个数填入之前的坑$arr[$left]，$arr[$right]成为新的坑3、$left++从前到后找一个比$pivot大的数，找到后挖出这个数填入之前的坑$arr[$right]。4.重复步骤2和3直到$left==$right，将基准$pivot填入$arr[$left]。
