Python中的快速排序递归 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

快速排序递归详解

01 — 前言我们熟知常见的排序算法有：冒泡排序、选择排序、归并排序、插入排序、快速排序等；每种都有其不同的特点以及解法，并且每种排序都可以找到不同算法思路来解答，拿快速排序来讲，有递归和非递归的解法...，以下就讲讲递归的快速排序的解法。...02 — 快速排序概念快速排序（Quick Sort）是对冒泡排序的一种改进。...从快速排序的步骤中我们不难发现：快速排序其实使用的是分而治之的思想，它的排序过程是一个递归调用的过程。...} 04 — 总结采用分而治之的递归思想是解决快速排序一个比较好的方案，递归的思想不止是用到排序里面，也可以用于查找里面，比如当需要在大数据量之中查找某个某个值时，也可以运用这种思想，从而达到提升查询效率

8011 0

python 递归排序

大家好，又见面了，我是你们的朋友全栈君。...python 递归对序列排序，使用二分冒泡排序，将序列分割为两部分第一步：首先，设定一个初始值，假设为序列的第一个值，第二步：将序列中大于初始值的...值，放置于初始值的左边第三步：将序列中小于初始值的值，放置于初始值的右边第四步：将序列一分为二，存放小值的列表作为一个列表进入递归...存放大值的列表作为一个列表进入递归返回一个排好序的列表 def sort_list(lis, start, end): # 判断结束位置 if start < end

7164 0

您找到你想要的搜索结果了吗？

是的

没有找到

快速排序数组+递归实现

快速排序数组+递归实现问题描述：给定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

8332 0

排序算法指南：快速排序(非递归)

前言：本文将通过图解与代码相结合的方式，详细介绍快速排序的非递归实现方法。虽然前文已展示递归实现方案，但在实际面试中，面试官更倾向于考察非递归版本的实现。...一、非递归实现快排的思路 1.1核心原理：手动模拟栈在标准的递归快速排序中，当我们写下 quickSort(a,left, right) 时，系统会自动分配一块内存（函数调用栈）来记住当前的...在非递归版本中，我们不需要系统帮忙，而是自己创建一个栈（Stack）数据结构。...1.2核心操作：用栈存取数组区间 ① 向栈中存储操作：存储每一次需要排序的子数组的起止下标（begin，end）。...非递归快速排序主函数 void QuickSortNonR(int* a, int left, int right) { stack st; // 初始状态入栈：注意栈是后进先出

1341 0

快速排序详解（递归实现与非递归实现）

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

6621 0

非递归式实现快速排序

快速排序基本思想是寻找一个元素作为基准，将其他元素划分为两部分，其中一部分比基准元素小，另一部分比基准元素大，然后如此继续对这两部分操作下去快速排序最简单的实现就是通过简单的递归，实现方式之一是使用双指针...，两个指针同时走，左指针找到大的，右指针找到小的，然后交换这两个元素的位置，问题在于枢纽元素和谁交换，让右指针先走，两个指针走到相同位置的时候必然是右指针走到左指针的地方了，而左指针指向的元素是刚刚交换完比枢纽元素小的...，而枢纽元素选的是第一个，因此它们进行位置交换就是正确的这里给出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,

2111 0

递归与分治之快速排序

分治法就是把一个大问题分解为多个类型相同的子问题，最后把这些子问题的解合并起来就是问题的解。快速排序（Quicksort）是对冒泡排序的一种改进，采用了分治的思想。...快排的基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，当待排序列数据个数为...具体算法步骤：对于待排序列，在一趟排序前，从待排序列中随机选取一个数据作为枢轴量，使所有小于枢轴量的数据位于其左面，所有大于枢轴量的数据位于其右面，然后再依次用该方法对其左面、右面的序列进行排序。...当待排序列个数为1时，代表该部分已经完成排序。递归可完成整个序列的排序。...python代码实现如下： 1 # coding=gbk 2 import random 3 import time 4 5 __author__ = 'ice' 6 7 8 def

9536 0

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

文章目录前言一、快速排序的介绍二、快速排序的实现 2.1 hoare版本为什么每次相遇位置都比key要小 2.2 挖坑法 2.3 前后指针版本三、快速排序的优化快排的最坏情况 3.1 三数取中...3.2 递归到小的子区间时使用插入排序 3.3 快速排序的最终代码四、快速排序的总结快速排序的特性总结：一、快速排序的介绍快速排序是一种基于分治思想的高效排序算法，由Tony Hoare于1960...二、快速排序的实现快速排序是一种基于分治思想的高效排序算法其核心就是每次找到最中间的位置然后再进行递归继续找到最中间的位置然后再分割一直分割到只剩一个数的时候那么这个数组就是有序了。...每次找到中间值之后利用分治思想，大问题化为小问题然后递归进行排序当递归完成时每个中间值都找到就是排序好的时候而要搞定一个排序首先最先解决的就是其中单趟排序下面就是各位大佬想出来的单趟排序方法：先把部分的单趟排序搞出来后面来实现整体排序就简单多了...和 right 交换并记录下新的坑位 hole 代码演示： //快速排序挖坑法 int PartSort2(int* a, int begin, int end) { //三数取中 int midi

3961 0

【模板小程序】快速排序算法实现（递归+非递归）

快速排序一定要会默写！...for(auto val:array) 15 cout<<val<<" "; 16 cout<<endl; 17 } 18 19 /*********************快速排序的划分写法...return low; 33 } 34 /*************************************************************/ 35 /**********快速排序的划分写法...for(auto val:array) 16 cout<<val<<" "; 17 cout<<endl; 18 } 19 20 /*********************快速排序的划分写法...return low; 34 } 35 /*************************************************************/ 36 /**********快速排序的划分写法

2.2K2 0

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

1 快速排序非递归利用迭代的方式来模仿递归，快速排序递归的本质也就是它可以拿到那些待排序的区间，那么不就说明了只要我们右那些待排序的区间就可以不再需要递归了。...好像和递归差不多，每次就是差不多，快速排序的逻辑是不会变的，我们只把原来的递归处理改成了迭代。将区间保存到栈中可以写一个结构体，也可以直接传，取出时也一次取两个就可以了，不影响的。...DestoryStack(&s); } 快速排序的总结：快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序时间复杂度：O(N*logN) 空间复杂度：O(1) 稳定性：不稳定 2....不同的是，因为快速排序是确定基准值，因为基准值已经到了它排序后的最终位置，后续传区间就是基准值的左右区间，但是归并排序可不是这样的，归并排序是直接找数组的中间下标，然后将数组一分为二，这样的话也就表示了再这过程中是...0, n - 1); } 归并排序的特性总结：归并排序缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题时间复杂度：O(N*logN) 空间复杂度：O(N) 稳定性：稳定

3251 0

75-递归函数练习：快速排序

思路： 1、假设列表中第一个数是中间值，比它小的数字放到smaller列表中，比它的大的数字放到larger列表中。再将这三项拼接起来。...2、因为smaller和larger仍然是无序列表，需要使用相同的方法继续分割。 3、如果列表的长度是0或1，那么就没有必要再排序了。

5371 0

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

前言快排的性能和各个综合性能都是排序梯队里面最顶尖的，虽然我们掌握递归的方法来快速实现快排，但是递归堆栈的消耗太大了为此我们专门还优化了快排。...文章目录前言一、为什么要掌握非递归二、栈区和堆区的大小对比三、非递归实现快排的思想 3.1 利用人工栈来实现递归 3.2 实现代码四、快速排序总结快速排序的特性总结：一、为什么要掌握非递归...还能来以此来检验我们的递归能力在有些场景限制递归深度的时候，例如在嵌入式系统或对递归深度有限制的环境中，非递归就是我们必须掌握的了使得我们的算法可以应用于各种场景二、栈区和堆区的大小对比为什么我们一直在说要避免栈区开调用开销...其实是因为在操作系统的概念中栈是一快用来快速存储的区域在32位操作系统中栈一般的内存只有 10M 而堆的内存划分却达到了 2G 三、非递归实现快排的思想非递归其实就是利用迭代的思想来替换递归的过程...快速排序的特性总结：快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序时间复杂度：O(N*logN) 空间复杂度：O(logN) 稳定性：不稳定

3531 0

C语言快速排序（非递归）图文详解

前言：上一期分析了快速排序的三种写法，这三种写法有一个相同点，都是采用递归形式来实现的，那么有没有非递归的方法实现呢？...答案是当然有，用非递归的方法实现快速排序，其实可以借助数据结构中的栈来模拟实现递归的过程。...（注意下面的数字代表下标）好，接下来开始用栈模拟递归：（图中栈中的数字均表示下标） 1.第一次入栈：将整个数组入栈，也就是下标为0-8 2.第一次出栈：每次出栈，对出栈的下标区间进行一次部分排序，...然后再将key的左区间和右区间分别入栈，也就是0-3和5-8 3.第二次出栈：根据栈的性质后入先出，所以我们让5-8出栈：跟上面一样，每次出栈对相应区间进行一次部分排序，排序完如下图：因为在对这个区间进行部分排序时...现在就不难感受出，这其实是在模拟递归的过程。

6321 0

快速排序 Python

碎碎念念快速排序的基本思想是：首先找一个基准数，一般选第一个数或者最后一个数作为基准数，然后先把这一串数以基准数为界限分成两部分，一部分比基准数小，另一部分比基准数大。...然后用分治法的思想，进行递归调用，对每一部分继续操作下去，直到每一部分只剩下一个数。代码 def fast(number,first,last):#从小到大排序。...if first>=last:#相同说明这小部分一排序完毕。...=j:#从两边出发，比基准数小的扔一边，比基准数大的扔另一边 while j>i and number[j]>=standard:#从右边出发，目的是找到比基准数小的数...fast(number,first,i-1)#继续排基准数左边的 fast(number,i+1,last)#继续排基准数右边的 number=[3,6,5,8,1,4,7,9,2,0

3222 0

Python|快速排序

1 快速排序的方法取一个元素s，将比s小的元素放在s的左边，将比s大的元素放在s的右边；就是将数组划分成两部分,左小右大，然后将分好的两个数组递归继续执行上述操作，直到排序完毕为止。...递归执行上述步骤；在对划分的左右进行排序，直到排序完毕。左边:left=0，right=返回的left-1 右边:left=返回的left，right=数组长度 ?...2 代码演示 # 快速排序 def passt(li, left, right): s = li[left] # 该处我们始终以第一个元素为s，即所取元素 while left...] quick_sorted(li, 0, len(li)-1) print(li) 3 总结本篇博客主要讲述了快排的排序方法，及如何用python代码来实现。...快速排序相对于其他排序方法而言，主要突出了一个“快”字，可以更快的将数组的元素进行排序。 END 主编 | 王文星责编 | W Z Y

4222 0

Python|快速排序

说明排序的定义对一序列对象根据某个关键字进行排序。...术语说明稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；内排序：所有排序操作都在内存中完成；外排序：...由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；时间复杂度：一个算法执行所耗费的时间。...return quickSort(minList) + midList + quickSort(maxList) else: return todoList 现在对10000个随机生成的数据进行排序...t2=time.time() print(t2-t1) t3=time.time() new2=bubbleSort(randomList) t4=time.time() print(t4-t3) 快速排序

5261 0

python快速排序

// python小程序 // 晚上没事儿干，用python写了个快排小程序，分享出来看看：快速排序： #!.../usr/bin/env python # -*- coding:utf8 -*- from random import randrange, shuffle ''' 基本思想：通过一趟排序将要排序的数据分割成独立的两部分...：分割点左边都是比它小的数，右边都是比它大的数。...基本流程：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列...，则把end的数字复制给start array[start] = array[end] # 同样的方法比较前半区 while start

4661 0

【C语言数据结构】排序（快速排序及多种优化|递归及非递归版本）

今日更新了快速排序的内容欢迎大家关注点赞收藏⭐️留言交换排序快速排序快排的过程图如下： hoare版代码呈现 void QuickSort(int* a, int begin,int...直到left与right相遇，就交换keyi和left对应的值。这是单趟的，后续过程重复，可以思考二叉树的递归过程，快排递归与其相似（见下图）。下图中，划红线的地方是容易出错的地方。...快排优化三数取中法选key 递归到小的子区间时，可以考虑使用插入排序三数取中法快排对于有序的数据，效率不是很高。如上图，我们前面的快排是固定选key的，也就是左边第一幅图，效率很低。...但不同的版本，单趟排序后的结果可能会不同。...先模拟递归左边，像二叉树递归那样，先入右边的数，再入左边，这样出的时候就先出左边的，然后就可以模拟先往左边递归了。

3661 0

Python实现的快速排序

这可能就是一些额外的知识补充给带给我的福利吧。第二个是对于数据结构设计上和算法的密切相关，让我突然理解了数据库中的设计方式。...记得大学看一个算法，花了好几个小时，结果上课的时候，老师花了不到五分钟就讲完了，然后脑袋一片空白，记得当时学快速排序的时候，感觉这个算法应该是很复杂，感觉理解了，但是很快就忘记了。...第四个是对递归的理解。今天看了之后算是刷新自己的认知。里面有句话说的好：递归将人分为三个截然不同的阵营，恨它的，爱它的，和恨了几年又爱上它的。我确切的说也是属于第三种。...使用循环，程序的性能可能而更好，但是使用递归，程序更容易理解。对于快速排序，算法的思考方式就是由简到难。...这样一来，三个数，四个数都是如此的思路。我们就可以使用递归来处理了。

1.1K7 0

基于Python的快速排序

快速排序（Quick Sort）是一种高效的排序算法，它采用了分而治之（Divide and Conquer）的思想。...以下是一个简单的快速排序的 Python 实现：def quick_sort(arr): if len(arr) 中数组：包含所有等于基准的元素（这一步是可选的，但为了保持算法的稳定性，我们通常也会将其包括在内）。右数组：包含所有大于基准的元素。递归排序：对左数组和右数组分别进行快速排序。...注意，由于我们已经将等于基准的元素单独拿出来了，所以在对左右数组进行排序时，不需要再考虑这些元素。合并：将已排序的左数组、中数组和右数组合并起来，得到完全排序的数组。...递归基准：快速排序是递归的，每次递归都会选择一个新的基准，并重复上述步骤，直到数组被完全排序。注意：上述代码是一个简单的快速排序实现，主要用于教学目的。

4132 0

点击加载更多

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭