快速排序法

定义

快速排序是一种高效的排序算法，采用《分而治之》的思想，把大的问题拆分成小的问题，小的问题再拆分成更小的问题

原理

对于给定的记录，通过一趟排序后，将原序列分为两部分，前一部分均比后一部分小，然后再依次对前后两部分进行快速排序，递归该过程，直到所有数据均有序为止。

分析

对于给定的数组A[0]...A[N-1],首先选取一个数据作为关键数据（通常为数组的第一个元素），然后将比它小的放在它的前面，比它大的放到他的后面，这个过程称为一趟快速排序。
一趟快速排序的算法如下：
①设置两个变量i, j 并初始化为：i=0, j=N-1;
②以第一个数组元素作为关键数据（假设这个关键数据为key）；
③从 j 开始向前搜索，即由后向前开始搜索（j--),找到第一个小于key的值A[j], 将A[j]与A[i] 互换；
④从i开始向后搜索，即由前向后搜索（i++),找到第一个大于key的A[i], 将A[i] 和A[j]互换；
⑤重复③④，直到i=j,③④中，没找到符合条件的值，即③中A[j]不小于key，④中A[i]不大于key的时候，改变i，j的值，使得j=j-1,i=i+1, 直到找到为止，找到的话，进行交换的时候，i ，j的指针位置不变，另外i=j 的时候，正好是i+ 或j- 完成的时候，此时循环结束

说明

以数组array(49, 38, 65, 97, 76, 13, 27, 49)为例
第一趟排序过程如下：
初始状态：[49, 38, 65, 97, 76, 13, 27, 49]
第一次交换后：[27, 38, 65, 97, 76, 13, 49, 49]
第二次交换后：[27, 38, 49, 97, 76, 13, 65, 49]
第三次交换后：[27, 38, 13, 97, 76, 49, 65, 49] j 向左扫描，位置不变
第四次交换后：[27, 38, 13, 49, 76, 97, 65, 49] i 向右扫描，位置不变
此时i和j相等为76：[27, 38, 13, 49, 76, 97, 65, 49]
整个排序过程如下：
初始状态：[49, 38, 65, 97, 76, 13, 27, 49]
一趟排序之后：[27, 38, 13] 49, [76, 97, 65, 49]
二趟排序之后：[13], 27, [38] 49, [49, 65] 76, [97]
三趟排序之后：13, 27, 38 49, 49, [65] 76, 97
最终排序结果：13, 27, 38 49, 49, 65, 76, 97

代码如下：

function quickSort(&$arr, $slow, $hight) {
    if ($slow >= $hight) {
        return ;
    }
    $first = $slow;
    $last = $hight;
    $key = $arr[$first];
    while($first < $last) {
        while($first < $last && $arr[$last] >= $key) {
            --$last;
        }
        $arr[$first] = $arr[$last];
        while($first < $last && $arr[$first] <= $key) {
            ++$first;
        }
        $arr[$last] = $arr[$first];
    }
    $arr[$first] = $key;//这个的作用是将选取的key，赋值给第一个元素（$first此时不是1哦），也即中间数，左边比它小，右边比它大。
    quickSort($arr, $slow, ($first-1));
    quickSort($arr, $first+1, $hight);
}
$arr = array(49, 38, 65, 97, 76, 13, 27, 49);
echo "排序前：";
foreach($arr as $k=>$v) {
    echo $v . ' ';
}

quickSort($arr, 0, intval(count($arr)-1));

echo PHP_EOL;
echo "排序后：";
foreach($arr as $k=>$v) {
    echo $v . ' ';
}
结果是：
没有这个是错误的：$arr[$first] = $key;
排序前：49 38 65 97 76 13 27 49 
排序后：13 38 38 97 49 65 65 97 
↓
正确结果
排序前：49 38 65 97 76 13 27 49 
排序后：13 27 38 49 49 65 76 97

网上还有一种写法

有人评价：你这个看着形似快排，快排里面是指针移动和位置交换，但你的是从新开辟空间，这样可能也能实现，但是会增加空间复杂度
↓
https://www.cnblogs.com/chenhaoyu/p/9093483.html#4251998
也可以看下这个说明
↓
https://www.imooc.com/article/247285

<?php

$a = array(2,13,42,34,56,23,67,365,87665,54,68,3);

function quick_sort($a)
{
    // 判断是否需要运行，因下面已拿出一个中间值，这里<=1
    if (count($a) <= 1) {
        return $a;
    }

    $middle = $a[0]; // 中间值

    $left = array(); // 接收小于中间值
    $right = array();// 接收大于中间值

    // 循环比较
    for ($i=1; $i < count($a); $i++) { 

        if ($middle < $a[$i]) {

            // 大于中间值
            $right[] = $a[$i];
        } else {

            // 小于中间值
            $left[] = $a[$i];
        }
    }

    // 递归排序划分好的2边
    $left = quick_sort($left);
    $right = quick_sort($right);

    // 合并排序后的数据，别忘了合并中间值
    return array_merge($left, array($middle), $right);
}

print_r(quick_sort($a));

最后编辑于：2020.09.11 16:20:56