乐趣区

快速排序填坑口诀

jiezi

快速排序由于排序效率在同为 O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想 —- 分治法也确实实用，因此在很多笔试面试中出现的几率很高。

直接默写出快速排序还是有一定难度的，所以一定要弄清楚原理再去记忆而不是去硬背。

快速排序是 C.R.A.Hoare 于 1962 年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-Conque)。

最常见的实现方法是 ” 填坑法 ”，它的实现步骤如下：

  1. 选定数列头元素为基准元素 pivot，并记住这个位置 index，这个位置相当于一个 ” 坑 ”。
  2. 设置两个指针 left 和 right，分别指向数列的最左和最右两个元素。
  3. 接下来从 right 指针开始，把指针所指向的元素和基准元素做比较，如果比 pivot 大，则 right 指针向左移动；如果比 pivot 小，则把所指向的元素放入 index 对应的位置。
  4. 将被放入坑中的元素 (right 指针移动之前指向的元素) 之前的位置赋值给 index 让这个位置变成一个新的 ” 坑 ”，同时 left 指针向右移动一位。
  5. 接下来切换到 left 指针进行比较，如果 left 当前指向的元素小于 pivot，则 left 指针向右移动；如果元素大于 pivot，则把元素放入坑中，left 指向的位置赋值给 index，使其变成一个新的 ” 坑 ”，同时 right 指针向左移动一位。
  6. 重复步骤 3，4，5 直到 left 等于 right 时，将 pivot 放入 left 和 right 重合的位置，此时数列中比 pivot 小的元素都在 pivot 左边，比 pivot 大的都在 pivot 元素位置的右边。
  7. 获取 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] 中。

退出移动版