快速排序填坑口诀
快速排序由于排序效率在同为 O (N*logN) 的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想 ---- 分治法也确实实用,因此在很多笔试面试中出现的几率很高。
直接默写出快速排序还是有一定难度的,所以一定要弄清楚原理再去记忆而不是去硬背。
快速排序是 C.R.A.Hoare 于 1962 年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法 (Divide-and-Conque)。
最常见的实现方法是 "填坑法",它的实现步骤如下:
-
选定数列头元素为基准元素 pivot,并记住这个位置 index,这个位置相当于一个 "坑"。
-
设置两个指针 left 和 right,分别指向数列的最左和最右两个元素。
-
接下来从 right 指针开始,把指针所指向的元素和基准元素做比较,如果比 pivot 大,则 right 指针向左移动;如果比 pivot 小,则把所指向的元素放入 index 对应的位置。
-
将被放入坑中的元素 (right 指针移动之前指向的元素) 之前的位置赋值给 index 让这个位置变成一个新的 "坑",同时 left 指针向右移动一位。
-
接下来切换到 left 指针进行比较,如果 left 当前指向的元素小于 pivot,则 left 指针向右移动;如果元素大于 pivot,则把元素放入坑中,left 指向的位置赋值给 index,使其变成一个新的 "坑",同时 right 指针向左移动一位。
-
重复步骤 3,4,5 直到 left 等于 right 时,将 pivot 放入 left 和 right 重合的位置,此时数列中比 pivot 小的元素都在 pivot 左边,比 pivot 大的都在 pivot 元素位置的右边。
-
获取 pivot 的位置 pivotIndex,分而制之,将 pivotIndex 左侧和右侧的子数列分别重复上述步骤 1~6,直到不能拆分子数列为止,整个数列就是一个从头开始递增的数列。
具体的代码实现如下:
<?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]
中。
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: