迹忆客 专注技术分享

当前位置:主页 > 学无止境 > 算法 >

排序算法学习之路——快速排序(非递归实现)

作者:迹忆 最近更新:2022/11/19 浏览次数:

《快速排序》这篇文章中我们介绍了快速排序的原理和步骤,以及使用递归的方式实现了该算法。而且在上篇文章中我们还提到使用非递归的方式实现该算法,本篇我们就使用非递归的方式来实现快速排序。

首先我们对其中涉及到的栈的操作步骤进行一下介绍

第一步、申请一个栈,存放排序数组的起始位置和终点位置。

第二步、将整个数组的起始位置s和终点位置e进栈

第三步、出栈数据,对出栈的数据进行排序,查找基准数据所在最终的位置 p。

第四步、判断起始位置s 是否小于基准位置p-1,如果小于则将起始位置和p-1为终点位置进栈

第五步、判断基准位置p+1 是否小于终点位置e,如果小于则将 p+1作为起始位置,e作为终点位置进栈

第六步、判断栈是否为空,如果不为空则重复第三步,否则退出操作。

使用非递归的方式整体上就是上面的这个步骤。下面我们通过代码来实现快速排序。

其中查找基准位置的函数可以和使用递归方式的相同

function FindPv(&$arr, $s, $e)
{
    $p = $s;
    //基准起始位置
    $v = $arr[$p];
    //将数组的第一个值作为基准值
    while ($s < $e) {
        while ($arr[$e] > $v && $e > $p) {
            $e--;
        }
        $arr[$p] = $arr[$e];
        $p = $e;
        while ($arr[$s] < $v && $s < $p) {
            $s++;
        }
        $arr[$p] = $arr[$s];
        $p = $s;
    }
    $arr[$p] = $v;
    return $p;
}

function PvSort(&$arr)
{
    $stack = array();
    array_push($stack, array(0, count($arr) - 1));
    while (count($stack) > 0) {
        $temp = array_pop($stack);
        $p = FindPv($arr, $temp[0], $temp[1]);
        if ($p + 1 < $temp[1]) array_push($stack, array($p + 1, $temp[1]));
        if ($temp[0] < $p - 1) array_push($stack, array($temp[0], $p - 1));
    }
}

$arr = array(10, 6, 8, 23, 4, 1, 17, 56, 32, 50, 11, 9);
PvSort($arr);
print_r($arr);

上面就是实现快速排序的非递归的方式。其实代码也并不复杂,当然PHP有更简洁的代码来实现快速排序,但是这里我们使用这种比较原始的方式,将更有助于我们对快速排序的理解。

希望本文对大家有所帮助。

转载请发邮件至 1244347461@qq.com 进行申请,经作者同意之后,转载请以链接形式注明出处

本文地址:

相关文章

Python 中的尾递归

发布时间:2023/04/24 浏览次数:94 分类:Python

本文介绍了尾递归,并演示了我们如何在 Python 中根据空间和时间优化递归。

MATLAB 对行进行排序

发布时间:2023/04/23 浏览次数:198 分类:MATLAB

本教程将讨论使用 MATLAB 中的 sortrows() 函数对矩阵中存在的行进行排序。在数据分析和处理中,排序是必不可少的,因为它可以使数据在排序时易于分析和处理。

MySQL 递归查询

发布时间:2023/04/18 浏览次数:89 分类:MySQL

在本指南中,我们将了解 MySQL 的递归查询。 如何在 SQL 中编写递归查询及其工作原理将在本指南中进行解释,以便您更好地理解。

在 Angular 中对表格进行排序

发布时间:2023/04/11 浏览次数:69 分类:Angular

我们可以按升序、降序等方式对表进行排序。现在让我们看看在 Angular 框架内创建具有排序功能的表的最佳方法。

在 C++ 中对字符串进行排序

发布时间:2023/03/31 浏览次数:102 分类:C++

本文演示了如何在 C++ 中对字符串进行排序。在本文中,我们假设字符序列存储在 std::string 对象中。

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

最新推荐

教程更新

热门标签

扫码一下
查看教程更方便