首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

有没有没有递归的快速排序的Python实现?

快速排序是一种常用的排序算法,递归是快速排序算法的一种常见实现方式,但也可以通过其他方式实现快速排序而不使用递归。

以下是一种没有使用递归的快速排序的Python实现:

代码语言:txt
复制
def quick_sort(arr):
    stack = [(0, len(arr) - 1)]  # 使用栈来模拟递归调用
    while stack:
        low, high = stack.pop()
        if low < high:
            pivot = partition(arr, low, high)
            if pivot > low:
                stack.append((low, pivot - 1))
            if pivot < high:
                stack.append((pivot + 1, high))
    return arr

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# 使用示例
arr = [5, 3, 8, 4, 2, 7, 1, 6]
sorted_arr = quick_sort(arr)
print(sorted_arr)

这个实现方式使用一个栈来模拟递归调用过程。初始时,将整个数组的索引范围(0, len(arr)-1)入栈,然后进入循环。每次循环从栈顶取出一个索引范围,进行快速排序的划分操作,并根据划分结果将子数组的索引范围入栈。直到栈为空,排序完成。

这种实现方式避免了递归带来的函数调用开销,相较于递归实现有一定的性能优势。

快速排序的优势是具有较好的平均时间复杂度(O(nlogn)),在处理大规模数据时表现较好。它常被用于排序、查找中位数、求解逆序对等场景。

腾讯云提供的与快速排序相关的产品和服务包括云服务器、云数据库、云存储等,您可以根据具体的需求选择相应的产品。您可以访问腾讯云官网(https://cloud.tencent.com/)了解更多关于这些产品的详细信息。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

快速排序 数组+递归实现

快速排序 数组+递归实现 问题描述: 给定N个元素数组arr[N],需要把数组arr中数排成非递减次序并输出. 基本思想: 1....用一个自定义分割方法split()选取用来作分割元素(也称为partition主元),最简单分割方法是选定待排范围第一个数为partition主元,一趟快排完成后,主元e是数组arr中第i个元素...使用两个跟踪变量(forward和backward),递归地对从i到backward采用快速排序方法quickSort(),并递归地对从forward到i采用快速排序方法quickSort(); 3...注: 数组arr=L区间(主元e左边部分)+主元e+U(未排序部分)+R(主元e右边部分),其中区间U是区间L与区间R夹住部分,每次递归都是让U缩小,直到为0,此时快排结束......e左侧元素排序 quickSort(arr, part_pos+1, backward); // 递归地给主元e右侧元素排序 } int split(int arr[], int forward

64520

排序篇】快速排序递归实现与归并排序实现

1 快速排序递归 利用迭代方式来模仿递归快速排序递归本质也就是它可以拿到那些待排序区间,那么不就说明了只要我们右那些待排序区间就可以不再需要递归了。...好像和递归差不多,每次就是差不多,快速排序逻辑是不会变,我们只把原来递归处理改成了迭代。 将区间保存到栈中可以写一个结构体,也可以直接传,取出时也一次取两个就可以了,不影响。...DestoryStack(&s); } 快速排序总结: 快速排序整体综合性能和使用场景都是比较好,所以才敢叫快速排序 时间复杂度:O(N*logN) 空间复杂度:O(1) 稳定性:不稳定 2....归并排序核心步骤: 合并时动图: 其实归并排序很简单,像分解过程,不是和快速排序很像嘛,都是传数组和区间。...,大概会有一个区间没有走完我们只要再把那个没有走完数据区间取出即可。

11110
  • 快速排序详解(递归实现与非递归实现

    一、快速排序基本思想 快速排序是Hoare于1962年提出一种二叉树结构交换排序方法,其基本思想为:任取待排序元素序列中某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值...div); // 递归排[div+1, right) QuickSort(array, div+1, right); } 上述为快速排序递归实现主框架,会发现与二叉树前序遍历规则非常像,先取中间...QuickSort(a, left, keyi-1); QuickSort(a, keyi+1, right); //不断递归左区间和右区间 } 四、快速排序优化实现 4.1快排特殊情况 上面的写法面对绝大多数情况排序已经可以实现时间复杂度接近...QuickSort(a, keyi+1, right); } else//区间长度小于10时 { InsertSort(a + left, right - left + 1); } } 五、快速排序递归实现...快排使用到了递归思想和方法,但是递归如果递归太深的话就会有爆栈风险,所以在这里也介绍一下快速排序递归实现方法。

    28510

    递归实现快速排序

    快速排序基本思想是寻找一个元素作为基准,将其他元素划分为两部分,其中一部分比基准元素小,另一部分比基准元素大,然后如此继续对这两部分操作下去 快速排序最简单实现就是通过简单递归实现方式之一是使用双指针...,两个指针同时走,左指针找到大,右指针找到小,然后交换这两个元素位置,问题在于枢纽元素和谁交换,让右指针先走,两个指针走到相同位置时候必然是右指针走到左指针地方了,而左指针指向元素是刚刚交换完比枢纽元素小...,而枢纽元素选是第一个,因此它们进行位置交换就是正确 这里给出C版本,C++版本一般是将int *a,换成std::vector&a void QS(int *a, int low, int...腾位置给枢纽元素 a[i] = pivot; // 放置枢纽元素 QS(a, low, i - 1);// 继续排左边 QS(a, j + 1, high);// 继续排右边 } 而递归改非递归最简单改法就是使用栈...,这样基本上算法没有变化,递归本质也是栈功劳,先递归先入栈 void quickSort(std::vector &arr) { std::stack<std::pair<int,

    7510

    Python实现快速排序

    今天看了下《算法新解》这本书,很薄一本书,最开始吸引我有两点,一个是里面的大量图,内容相对来说比较清新,第二个是里面的代码是基于Python实现。...第一个是一般翻译书内容背景很难转换,老外举例子我们很多时候没有代入感。...记得大学看一个算法,花了好几个小时,结果上课时候,老师花了不到五分钟就讲完了,然后脑袋一片空白,记得当时学快速排序时候,感觉这个算法应该是很复杂,感觉理解了,但是很快就忘记了。...第四个是对递归理解。今天看了之后算是刷新自己认知。里面有句话说好:递归将人分为三个截然不同阵营,恨它,爱它,和恨了几年又爱上它。我确切说也是属于第三种。...使用循环,程序性能可能而更好,但是使用递归,程序更容易理解。 对于快速排序,算法思考方式就是由简到难。

    96370

    Python整数有没有边界?

    第一次接触 Python 时,是把它作为一个智能计算器使用。...普通计算器计算很大数时都会报错,比如计算 9 531441 次方,计算器就提示我不是数字: 然后我就试了下 Python 解释器 这个数字共有 507124 位,50 万位,不吃不喝不睡,1...秒钟读一位,要读 5 天多,足以说明,Python整数是没有边界,只是数越大,计算时间越长而已。...答:有,虽然 Python int 是没有边界,但是如果你只需要一个比其他数字更大数字,你可以使用 float('inf'), 以类似的方式,比其他所有数字都小:float('-inf') ,...Python3 sys.maxsize 和 Python2 sys.maxint,Java Long.MIN_VALUE 相当于 Python3 -sys.maxsize -1 和 Python2

    78310

    快速排序Python实现

    大家好,又见面了,我是你们朋友全栈君。 一、 算法介绍 快速排序是经常考查到排序算法,这里对快排算法做一下总结。快速排序是“交换”类排序,它通过多次划分操作实现排序!...二、演示流程 三、 Python代码实现 def quick_sort(nums: list, left: int, right: int) -> None: if left < right:...快速排序排序趟数和初始序列有关!...有多个时间复杂度为O(nlog2n)排序算法,但这里称之为快速排序算法而不是其他排序,是因为其他排序算法基本操作执行次数多项式最高项为X*nlog2,X为系数,快速排序X最小,可见它在最高级别的算法中是最好...空间复杂度分析 空间复杂度为O(log2n),快速排序递归进行,需要栈辅助!

    63110

    快速排序python实现

    快速排序python实现 快速排序 快速排序实现同样使用分治法,它原理是从序列中选择一个值作为基准值,然后分成比基准值小序列集合和比基准值小序列集合和与基准值相等序列集合。...s.extend(R) if __name__ == '__main__': s = [1, 7, 3, 5, 4] quick_sort(s) print(s) 代码中实现是列表快速排序...,类似的也可以实现其他类型序列排序 时间复杂度 快速排序时间复杂度有最优情况与最坏情况 最优情况为每一次基准值都正好为序列中位数,时间复杂度为nlog(n) 最坏情况为每一次基准值都恰好是序列最大值或最小值...就地快速排序 上面的快排使用了L,E,R存储临时序列,这样会占用内存,使用就地快速排序方式可以在原序列上完成排序,减少了内存使用 def inplace_quick_sort(s,a,b):...然后再进行递归调用两个序列​

    54120

    Python实现快速排序

    然后再按此方法对两部分数据分别进行快速排序,整个排序过程可以递归进行,直到被分割数据只有一个或零个时,递归结束,列表排序完成。...三、Python实现快速排序 # coding=utf-8 def quick_sort(array, start, end): if start >= end: return...快速排序除了需要传入待排序列表以外,还需要传入排序开始索引和结束索引,也就是说快速排序可以指定排序列表中部分数据,在递归时候就是排序部分数据。...快速排序也可以使用非递归方式实现,在非递归实现时,代码思路不变,但必须借助栈或队列,代码会稍微长一点。 四、快速排序时间复杂度和稳定性 1....在快速排序实现过程中,有两个游标从列表两边向中间移动,游标right向左移动过程中,如果数据小于基准数据,则会将数据赋值给left游标。

    87141

    归并排序递归实现

    本文主要介绍2路归并排序递归实现。 2路归并排序简单介绍 下面是归并排序流程图。 ?...可以看到,每次程序都将数字两两分组(n/2个组),组内单独排序,最后将这些组两两合并,生成n/4个组,组内再单独排序。直到最后只剩下一个组为止。 2路归并排序时间复杂度为O(logN)。...2路归并排序递归代码实现 2路归并排序代码递归实现特别简单,只要重复把当前区间[left,right]分为两半,对两边子区间[left,mid]和[mid+1,right]分别进行递归,最后将两个已经有序子区间合并为有序区间即可...问题: 怎么表达递归边界(即最后只剩下一个元素)? if(left < right) //当各自剩下一个元素时,left=right,退出if语句 拆分出来数组元素要怎么存放?...参考 算法笔记3105ProblemB 基础排序III:归并排序 版权所有:可定博客 © WNAG.COM.CN 本文标题:《归并排序递归实现》 本文链接:https://wnag.com.cn/898

    66820

    【数据结构与算法】快速排序递归实现方法

    一.前言 如果数据量过大的话,不断递归就会出现栈溢出现象,这个时候你代码是没问题,但就是跑不起来,这个时候就要把递归改成非递归。...一般有两种改法: 1.直接改,利用循环等; 2.借助栈辅助。 而快速排序递归实现方法就需要借助栈辅助。...二.非递归实现 通过观察我们发现,每次递归调用传过去是一个数组和一个区间,数组自不用说,这个区间就是我们突破点; 也就是说我们只要想办法在循环时候拿到本次要排序区间就行了,那要怎么做呢?...2.取出栈顶两个数据,分别赋给 begin 和 end ,注意在这之后要pop掉取出数据; 3.然后就是快排逻辑,有三种方法,哪种都可以; 如果不清楚这三种方法的话,请点击:快速排序三种实现方法...出一个就要pop掉一个数据 Stackpop(&st); int end = Stacktop(&st); Stackpop(&st); int keyi = begin; //以下为快速排序逻辑

    16810

    快速排序:高效分割与递归排序领域王者算法

    文章目录 前言 一、快速排序介绍 二、快速排序实现 2.1 hoare版本 为什么每次相遇位置都比key要小 2.2 挖坑法 2.3 前后指针版本 三、快速排序优化 快排最坏情况 3.1 三数取中...3.2 递归到小子区间时使用插入排序 3.3 快速排序最终代码 四、快速排序总结 快速排序特性总结: 一、快速排序介绍 快速排序是一种基于分治思想高效排序算法,由Tony Hoare于1960...二、快速排序实现 快速排序是一种基于分治思想高效排序算法其核心就是每次找到最中间位置然后再进行递归继续找到最中间位置然后再分割一直分割到只剩一个数时候那么这个数组就是有序了。...每次找到中间值之后利用分治思想,大问题化为小问题 然后递归进行排序递归完成时每个中间值都找到就是排序时候 而要搞定一个排序首先最先解决就是其中单趟排序下面就是各位大佬想出来单趟排序方法: 先把部分单趟排序搞出来后面来实现整体排序就简单多了...快排最坏情况 快速排序虽然很快时间复杂度一眼看上去都是 N*longN 但这只是最好情况: 注:最坏情况复杂度是 N*N,每次 key 选值都是最小 每次进行递归并不是完全二叉树样子

    20110

    快速排序(三种算法实现和非递归实现)

    快速排序(Quick Sort)是对冒泡排序一种改进,基本思想是选取一个记录作为枢轴,经过一趟排序,将整段序列分为两个部分,其中一部分值都小于枢轴,另一部分都大于枢轴。...对于快速排序一次排序,有很多种算法,我这里列举三种。 左右指针法 选取一个关键字(key)作为枢轴,一般取整组记录第一个数/最后一个,这里采用选取序列最后一个数为枢轴。...当left >= right时,一趟快速排序就完成了,这时将Key和array[left]值进行一次交换。...2、直接插入 由于是递归程序,每一次递归都要开辟栈帧,当递归到序列里值不是很多时,我们可以采用直接插入排序来完成,从而避免这些栈帧消耗。...,所以这里要 - 1; } ---- 非递归实现 递归算法主要是在划分子区间,如果要非递归实现快排,只要使用一个栈来保存区间就可以了。

    1.3K30

    快速排序四种python实现

    快速排序算法,简称快排,是最实用排序算法,没有之一,各大语言标准库排序函数也基本都是基于快排实现。 本文用python语言介绍四种不同快排实现。 1....array如果是个列表的话,可以通过len(array)求得长度,但是后边递归调用时候必须使用分片,而分片执行原列表复制操作,这样就达不到原地排序目的了,所以还是要传上边界和下边界。 3....用栈实现递归快排程序 先说两句题外话,一般意义上栈有两层含义,一层是后进先出数据结构栈,一层是指函数内存栈,归根结底,函数内存栈结构就是一个后进先出栈。...栈里边保存的当然是需要迭代函数参数,结束条件也是跟需要迭代参数有关。对于快速排序来说,迭代参数是数组上边界low和下边界high,迭代结束条件是low == high。...中访问是最后一个元素,所以如果程序写错了,可能其他语言会报错,但python会输出一个错误结果。

    5.5K20

    python快速排序实现

    基本思想是:通过一趟排序将要排序数据分割成独立两部分,其中一部分所有数据都比另外一部分所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列...一趟快速排序算法是: 1)设置两个变量i、j, 排序开始时候:i=0,j=N-1; 2)以第一个数组元素作为关键数据,赋值给 key,即 key=A[0]; 3)从j开始向前搜索,即由后开始向前搜索...3、4步,直到i=j; (3,4步中,没找到符合条件值,即3中A[j]不小于 key,4中A[i]不大于 key时候改变j、i值,使得j=j-1,i=i+1,直至找到为止。...找到符合条件值,进行交换时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成时候,此时令循环结束)。...python代码实现: def quickSort(L, low, high): i = low j = high if i >= j: return L

    34330

    快速排序:非递归优势与性能详解

    前言 快排性能和各个综合性能都是排序梯队里面最顶尖,虽然我们掌握递归方法来快速实现快排,但是递归堆栈消耗太大了为此我们专门还优化了快排。...文章目录 前言 一、为什么要掌握非递归 二、栈区和堆区大小对比 三、非递归实现快排思想 3.1 利用人工栈来实现递归 3.2 实现代码 四、快速排序总结 快速排序特性总结: 一、为什么要掌握非递归...其实是因为在操作系统概念中栈是一快用来快速存储区域 在32位操作系统中栈一般内存只有 10M 而堆内存划分却达到了 2G 三、非递归实现快排思想 非递归其实就是利用迭代思想来替换递归过程...既然是利用人工栈那么我们首先肯定是先来创建一个栈来把第一个区间录入进去: 然后进行循环当栈位空时候说明我们数组就递归完了 3.2 实现代码 代码演示: // 快速排序递归实现 void QuickSortNonR...快速排序特性总结: 快速排序整体综合性能和使用场景都是比较好,所以才敢叫快速排序 时间复杂度:O(N*logN) 空间复杂度:O(logN) 稳定性:不稳定

    19710
    领券