排序算法-快速排序

排序算法-快速排序

<?php
/**
 * 快速排序.
 *
 * @param  array $value 待排序数组
 * @param  array $left  左边界
 * @param  array $right 右边界
 *
 * @return array
 */
function quick(&$value, $left, $right) {
    // 左右界重合 跳出
    if ($left >= $right) {
        return;
    }
    $base = $left;
    do {
        // 从最右边开始找到第一个比基准小的值,互换位置
        // 找到基准索引为止
        for ($i = $right;$i > $base;--$i) {
            if ($value[$i] < $value[$base]) {
                $tmp = $value[$i];
                $value[$i] = $value[$base];
                $value[$base] = $tmp;
                $base = $i; // 更新基准值索引
                break;
            }
        }
        // 从最左边开始找到第一个比基准大的值,互换位置
        // 找到基准索引为止
        for ($j = $left;$j < $base;++$j) {
            if ($value[$j] > $value[$base]) {
                $tmp = $value[$j];
                $value[$j] = $value[$base];
                $value[$base] = $tmp;
                $base = $j; // 更新基准值索引
                break;
            }
        }
    } while ($i > $j); // 直到左右索引重合为止
    // 开始递归
    // 以当前索引为分界
    // 开始排序左部分
    quick($value, $left, $i - 1);
    // 开始排序右边部分
    quick($value, $i + 1, $right);
    return $value;
}
/**
 * 快速排序.while版本
 *
 * @param  array $value 待排序数组
 * @param  array $left  左边界
 * @param  array $right 右边界
 *
 * @return array
 */
function quick_while(&$value, $left, $right) {
    // 左右界重合 跳出
    if ($left >= $right) {
        return;
    }
    $point = $left;
    $i = $right;
    $j = $left;
    while ($i > $j) {
        //查右边值
        while ($i > $point) {
            if ($value[$i] < $value[$point]) {
                $tmp = $value[$i];
                $value[$i] = $value[$point];
                $value[$point] = $tmp;
                $point = $i;
                break;
            }
            --$i;
        }
        //查左边值
        while ($j < $point) {
            if ($value[$j] > $value[$point]) {
                $tmp = $value[$j];
                $value[$j] = $value[$point];
                $value[$point] = $tmp;
                $point = $j;
                break;
            }
            ++$j;
        }
    }
    // 开始递归
    // 以当前索引为分界
    // 开始排序左部分
    quick_while($value, $left, $i - 1);
    // 开始排序右边部分
    quick_while($value, $i + 1, $right);
    return $value;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

浅谈程序设计中的位操作什么是位操作位操作的常用技巧位操作的应用,常见的算法题小结

位操作是一种很底层的操作二进制数据的方法,虽然比较难掌握,但是有时候却有更高的效率和难以名状的优雅感。而且,在面试或者笔试中,考察基本的位操作应用越老越普遍,所...

6610
来自专栏PHP在线

开发中遇到一个数据库字段问题

大牛不必浪费时间了,适合初学者。 今天遇到一个问题,数据库字段问题。 有一张表存储着用户消费记录,设计表时使用的是整形,后来增加需求,需要对业务做些改动,改过之...

35760
来自专栏lgp20151222

MySql 模糊查询

SQL模糊查询,使用like比较关键字,加上SQL里的通配符,请参考以下:  1、LIKE'Mc%' 将搜索以字母 Mc 开头的所有字符串(如 McBadden...

11910
来自专栏Django Scrapy

Django 数据库|models操作

相关API 1.get(**kwargs) 解释:返回与筛选条件相匹配的Model对象,返回结果有且只有一个。 说明:如果符合条件的对象多于一个抛出Multi...

34770
来自专栏ACM算法日常

trie树(字典树)-HDU1251

举一个例子,给50000个由小写字母构成的长度不超过10的单词,然后问某个公共前缀是否出现过。如果我们直接从字符串集中从头往后搜,看给定的字符串是否为字符串集中...

28110
来自专栏码匠的流水账

聊聊base62与tinyURL

base64大家肯定是很熟悉了,那base62是什么东东,它常被用来做短url的映射。

20420
来自专栏Hongten

java中的移位运算符:<<,>>,>>>总结

value >>> num     --   num 指定要移位值value 移动的位数。

26150
来自专栏PHP在线

php总结

php5.3新增魔术方法__invoke在对象实例化之后,像调用变量函数一样调用。 class testClass{ function __invoke(...

35190
来自专栏wym

Codeforces Round #483 (Div. 2) D. XOR-pyramid

For an array bb of length mm we define the function ff as

13910
来自专栏开发与安全

Mysql数据库学习(二):数据类型(数值类型 日期和时间类型 字符串类型)

数据类型 数值类型 日期和时间类型 字符串类型 ? 一、数值类型 整数 ? tinyint[M] [unsigned] [zerofill]   ...

24100

扫码关注云+社区

领取腾讯云代金券