快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此在很多笔试面试中出现的几率很高。
直接默写出快速排序还是有一定难度的,所以一定要弄清楚原理再去记忆而不是去硬背。
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-Conque)。
最常见的实现方法是"填坑法",它的实现步骤如下:
具体的代码实现如下:
<?php
class QuickSortClass{ public function partition(array &$arr, $startIndex, $endIndex) { // 取第一个元素为基准值 $pivot = $arr[$startIndex]; $left = $startIndex; $right = $endIndex;
// 坑的位置,出事等于基准值pivot的位置 $dataIndex = $startIndex; while ($right >= $left) { // right 指针从右向左进行移动,如果当前值小于基准值则将当前元素放到坑中, // 当前元素的位置变成新坑,left向右移动一个位置,切换到left进行比较, // 否则right往左移动一个位置继续用新元素的值与基准值进行比较 while ($right >= $left) { if ($arr[$right] < $pivot) { $arr[$dataIndex] = $arr[$right]; $dataIndex = $right; $left++; break; } $right--; }
// left 指针从左往右移动,如果当前值大于基准值则将当前元素放到坑中, // 当前元素变为新坑,right向左移动一个位置,切换到right进行比较, // 否则left往右移动一个位置继续与基准值进行比较 while($right >= $left) { if ($arr[$left] > $pivot) { $arr[$dataIndex] = $arr[$left]; $dataIndex = $left; $right --; break; } $left ++; }
}
$arr[$dataIndex] = $pivot; return $dataIndex; }
public function quickSort(&$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 = new quickSortClass();$arr = [72, 6, 57, 88, 60, 42, 83, 73, 48, 85];$quickSortClass->quickSort($arr, 0, count($arr) - 1);
var_dump($arr);
填坑法的口诀可以总结成如下
1. $left=strart;$right=end;$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]
中。