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

就地交换逻辑在快速排序中不起作用,但使用temp变量进行交换起作用。为什么?

就地交换逻辑在快速排序中不起作用,但使用temp变量进行交换起作用的原因是因为快速排序算法的核心思想是通过分治法将一个大问题分解为多个小问题进行解决。在快速排序中,我们选择一个基准元素,将数组分为两部分,一部分是小于基准元素的,另一部分是大于基准元素的。然后对这两部分分别进行递归排序,最后将它们合并起来。

在快速排序的过程中,我们需要将元素进行交换以实现排序。就地交换逻辑是指直接在原数组中进行元素交换,而不使用额外的变量。然而,在快速排序中,就地交换逻辑会导致交换后的元素位置发生变化,可能会破坏原有的分区结构,从而影响排序的正确性。

使用temp变量进行交换的方式可以避免这个问题。通过将要交换的元素先保存到temp变量中,然后再进行交换,可以确保交换后的元素位置不会发生变化,从而保持了原有的分区结构,保证了排序的正确性。

总结起来,就地交换逻辑在快速排序中不起作用是因为它可能会破坏原有的分区结构,而使用temp变量进行交换可以保持分区结构的完整性,确保排序的正确性。

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

相关·内容

常见排序算法分析

4.选择排序 思想:首先设置一个变量保存元素下标,将该元素与其他元素进行比较。若大于其他元素则变换其下标,比较完后再判断其下标是否发生变化,若变化则交换两个元素的值,否则不变。...= i) { temp = x[k]; x[k] = x[i]; x[i] = temp; } } 二.其他算法的分析 1 快速排序(QuickSort) 快速排序是一个就地排序,分而治之...一般不用在数据大于1000的场合下使用插入排序,或者重复排序超过200数据项的序列。 6 冒泡排序(BubbleSort) 冒泡排序是最慢的排序算法。实际运用它是效率最低的算法。...7 交换排序(ExchangeSort)和选择排序(SelectSort) 这两种排序方法都是交换方法的排序算法,效率都是 O(n2)。实际应用处于和冒泡排序基本相同的地位。...它们只是排序算法发展的初级阶段,实际中使用较少。 8 基数排序(RadixSort) 基数排序和通常的排序算法并不走同样的路线。

73680

Java数组篇:数组排序算法大比拼

int temp = array[j];:如果当前元素大于下一个元素,准备交换它们,首先保存当前元素的值到临时变量temp。...array[j + 1] = temp;:将临时变量temp的值(原当前元素的值)赋给下一个元素,完成交换。swapped = true;:设置swapped标志为true,表示发生了交换。if (!...此外,插入排序排序过程可以逐步产生部分排序的数组,这在某些应用场景中非常有用。归并排序归并排序采用分治法,将数组分为两部分,分别对它们进行排序,然后合并结果。...归并排序需要O(n)的额外空间来存储递归调用创建的临时数组,这使得它在空间复杂度上不如一些就地排序算法高效。然而,归并排序的高效率和稳定性使其处理大量数据时非常有用。...array[j] = temp;:将临时变量temp的值复制到j位置,完成交换。i++;:由于进行交换,递增i以指向新的比基准小的元素的最后一个位置。

11821
  • 极客算法训练笔记(五),十大经典排序之冒泡,选择,插入排序

    第二次排序,我们用的是稳定的排序算法,所以经过第二次排序之后,相同金额的订单仍然保持下单时间从早到晚有序。...是否原地(原址,就地排序 维基百科说的原地排序就是指在排序过程不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。简单理解为,允许借助几个变量,不需要额外开数组。...属于原地排序的是:希尔排序、冒泡排序、插入排序、选择排序、堆排序快速排序,他们都会有一项比较且交换操作(swap(i,j))的逻辑在其中;而合并排序,计数排序,基数排序等不是原地排序。...交换旗帜变量 = 假 (False) 从 i = 1 到 最后一个没有排序过元素的指数 如果 左边元素 > 右边元素 交换(左边元素,右边元素) 交换旗帜变量 = 真(True...) while 交换旗帜变量 动图演示 冒泡排序动画 ?

    53920

    排序(Sort) 原

    3、交换排序 交换排序的基本思想: 两两比较待排序记录的关键字,发现两个记录的次序相反时,即进行交换,直到没有反序的记录为止。 应用交换排序基本思想的主要排序方法有冒泡和快速排序。...②稳定性 冒泡排序就地排序,且它是稳定的。 2.快速排序(Quick Sort) 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。...2>算法步骤 快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。...(arr, maxIndex + 1, right); } } 4>算法分析 快速排序的时间主要耗费划分操作上,对长度为k的区间进行划分,共需k-1次关键字的比较。...②稳定性 直接选择排序是一个就地排序,并且是不稳定的。 2.堆排序(Heap Sort) 堆排序是利用完全二叉树进行排序的方法。

    1K20

    数据结构之内外排序

    中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为{5,3,3,4,3,8,9,10,11},现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法...快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序就地版本。快速排序可以由下面四步组成。 ⑴如果不多于1个数据,直接返回。...例如,序列{5,8,5,2,9},第一趟选择第1个元素5会和2交换,那么原序列2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。 实际应用处于和冒泡排序基本相同的地位。...它们只是排序算法发展的初级阶段,实际中使用较少。...可以发现,1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,短的有序序列合并的过程,稳定是是否受到破坏?

    29430

    C++不知算法系列之排序从玩转冒泡算法开始

    前言 所谓排序,就是把数据群体按个体数据的特征按从大到小或从小到大的顺序存放。 排序应用开发很常见,如对商品按价格、人气、购买数量等排序,便于使用快速找到数据。...并介绍与此相似的选择、插入、快速排序算法。 2. 冒泡排序算法 排序算法可以认为是在给定的数列先找出最大值或最小值,然后剩下的数据再找最大值(或最小值),重复此过程……最后让数列变得有序。...选择排序算法 选择排序算法是冒泡排序的变种,本质还是找最大(小)值,冒泡排序是一路比较一路交换为什么要这样,因为不知道数列哪一个数字是最大(小)值,所以只能不停的比较不停的交换。...不是说,找到一个小的就交换,因为有可能还有比之更小的,只有当后续所有数字找完后,再确定进行交换, 依然使用擂台算法实现找最大(小)值,找到后交换位置。...总结 除了冒泡、选择、插入、快速排序算法,还有很多其它的排序算法,冒泡、选择 、插入算法很类似,有其相似的比较、交换内部逻辑快速排序使用了分治理念,可从减少时间复杂度。

    24520

    《算法导论》 — Chapter 7 高速排序

    且O(nlgn)隐含的常数因子非常小。另外它还能够进行就地排序虚拟环境也能非常好的工作。...使得array[low…temp-1]的每个元素都小于等于array[temp],而array[temp+1…high]的每个元素都大于array[temp],下标temp也是在这个过程中被计算出来...对子数组array[low…temp-1],array[temp+1…high]进行排序; 合并:由于两个子数组是就地排序的。...quickSort(int * array, int low, int high); //求切割点 int partition(int * array, int low, int high); //交换两个变量的值...将该元素交换至段尾,依旧调用partition函数求切割点。 高速排序性能分析 高速排序的执行时间与划分是否对称有关。而后者又与选择了哪一个元素进行划分有关。

    29020

    PHP数据结构-交换排序:冒泡、快排(有彩蛋)

    不过首先还是要搞明白这个“交换”指的是什么意思。 上篇文章的插入排序,指的是直接将数据插入到指定的位置。而交换的意思,则是让两个位置的数据进行比对后直接交换。...这里其实从代码我们能够从一个地方很快地分辨出一段排序代码是否是交换排序,那就是他们会有一个对于两个元素进行数据交换的过程,而且往往普通情况下会使用一个中间变量。这个我们一会看代码就可以看到。...属于效率一般非常好理解的一种算法,而且它是一个稳定的排序算法。 快速排序 冒泡的感觉咋样?...快速排序的效率提升可达不到那么高,毕竟排序还是比查找要复杂些。而且它是冒泡的基础上进行的改良,同样也使用了二分的思想,也就是分而治之的一种理念。让每次的比较不再只是两个相邻的元素一个一个地比较。...没错,快速排序使用到了递归。这个递归其实也包含着分治的思想,就像秦国统一六国一样,分而治之。

    67230

    十大排序算法详解(一)冒泡排序、选择排序、插入排序快速排序、希尔排序

    具体的做法是每趟比较时,引入一个boolean型变量isSwap,来判断下次比较还有没有必要进行。...之所以对此有疑问,可能是没太清楚isSwap变量的作用,该变量的作用是“假如本趟比较过程没有交换发生,则不必进行下一趟比较”,第2趟比较过程,发生了交换动作,所以第3趟比较仍会进行。...= arr[i]; arr[i] = arr[j]; arr[j] = temp; } 1.3 冒泡排序的稳定性、复杂度和适用场景 1.3.1 稳定性   冒泡排序,遇到相等的值,是不进行交换的...4.3 快速排序的稳定性、复杂度和适用场景 4.3.1 稳定性   使用快速排序时,每次元素分堆都要选择基准因子。...; } } 5.3 希尔排序的稳定性、复杂度及适用场景 5.3.1 稳定性   希尔排序是直接插入排序的优化版,排序过程,会根据间隔将一个序列划分为不同的逻辑分组,不同的逻辑分组

    69550

    单链表的冒泡,快排,选择,插入,归并5种排序算法详解(多图+代码实现)

    0.稳定排序和原地排序的定义 稳定排序:   假定在待排序的记录序列,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列,ri=rj,且rirj之前,而在排序后的序列...像冒泡排序,插入排序,基数排序,归并排序等都是稳定排序 原地排序:   基本上不需要额外辅助的的空间,允许少量额外的辅助变量进行排序。就是原来的排序数组中比较和交换排序。...像选择排序,插入排序,希尔排序快速排序,堆排序等都会有一项比较且交换操作(swap(i,j))的逻辑在其中,因此他们都是属于原地(原址、就地)排序,而合并排序,计数排序,基数排序等不是原地排序 1.冒泡排序...假如原本p->data > q->data,则进行交换。变成q->data和p->data比较, *不会进行交换,所以排序就会错误。有兴趣的可以调试下。...,从头开始进行第二轮*/ p = phead; q = phead->next; } head = phead; return head; } 2.快速排序 基本思想   我们从数组中选择一个元素

    10.9K41

    代码面试

    用单个迭代器来回进行此操作对于时间和空间复杂度而言效率低下-一种称为渐近分析的概念。尽管使用1个指针的强力或幼稚的解决方案将起作用,但它将产生类似于O(n²)的东西。...通过以不同的速度移动(例如,循环链表),该算法证明两个指针必然会合。一旦两个指针都处于循环循环中,快速指针应捕获慢速指针。 您如何确定何时使用快速和慢速模式?...某些情况下,您不应该使用“两指针”方法,例如在单链列表,您不能向后移动。何时使用快速和慢速模式的一个示例是当您试图确定链接列表是否为回文式时。...您可以尝试将数字放置正确的索引这会导致O(n ^ 2)的复杂度不是最优的,因此是循环排序模式。 [图片上传失败......您可以使用递归(或使用堆栈进行迭代)遍历时跟踪所有先前的(父)节点。

    1.8K31

    快速排序python实现

    快速排序python实现 快速排序 快速排序的实现同样使用分治法,它的原理是从序列中选择一个值作为基准值,然后分成比基准值小的序列集合和比基准值小的序列集合和与基准值相等的序列集合。...每次分割都是以序列的第一个值作为基准值,经过拆分后自然就变成了有顺序的 具体算法 def quick_sort(s): """快速排序,s为列表""" # 结束条件 if len...有意思的是如果每次选第一个数做基准值,每次这个数又是最小值,那么序列本身就是有序的,时间复杂度也是最高的 要想 要想优化时间复杂度,基准值的选择很关键,可以使用类似的从序列中选几个数,再求出他们的中位数做基准值...就地快速排序 上面的快排使用了L,E,R存储临时的序列,这样会占用内存,使用就地快速排序的方式可以原序列上完成排序,减少了内存的使用 def inplace_quick_sort(s,a,b):...,并将left向右移动,right向左移动,继续重复进行 直到left>right,也就是全部扫描一遍后,将基准值s[b]与最后的left位置交换 这样就完成了分割 然后再进行递归调用两个序列​

    53620

    Go语言实现冒泡和快速排序

    冒泡和快速排序都属于交换排序,所谓交换排序是指借助数据元素之间互相交换进行排序的方法。 冒泡排序法 冒泡排序法是一种最简单的交换排序方法,它是通过相邻数据的交换逐步将线性表变成有序。...如此下去,重复以上过程,直至最终完成排序。 由于排序过程总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。...它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列...一趟快速排序的算法是: 1)设置两个变量i、j,排序开始的时候:i=0,j=N-1; 2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0]; 3)从j开始向前搜索,即由后开始向前搜索(j...func=retitle 用动态图描述的快速排序的算法逻辑。 ?

    67170

    快速排序原理JAVA和Scala实现-函数式编程的简洁演示

    高快省的排序算法 有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。...232129ogop8gk0r8y7l70k.png 这是为什么呢?快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。...这样每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然最坏的情况下,仍可能是相邻的两个数进行交换。...C语言快速排序实现 #include int a[101],n;//定义全局变量,这两个变量需要在子函数中使用 void quicksort(int left,int right...=a[left]; //temp存的就是基准数 i=left; j=right; while(i!

    1.1K50

    Go语言实现冒泡和快速排序

    冒泡和快速排序都属于交换排序,所谓交换排序是指借助数据元素之间互相交换进行排序的方法。 冒泡排序法 冒泡排序法是一种最简单的交换排序方法,它是通过相邻数据的交换逐步将线性表变成有序。...如此下去,重复以上过程,直至最终完成排序。 由于排序过程总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。...它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列...一趟快速排序的算法是: 1)设置两个变量i、j,排序开始的时候:i=0,j=N-1; 2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0]; 3)从j开始向前搜索,即由后开始向前搜索(j...func=retitle 用动态图描述的快速排序的算法逻辑。 ?

    55960

    排序算法之冒泡排序快速排序(快排)

    因为排序的过程,各元素不断接近自己的位置,如果一趟比较下来没有进行交换,就说明序列有序,因此要在排序过程设置一个标志flag判断元素是否进行交换。从而减少不必要的比较。...(这里说的优化,可以冒泡排序写好后,进行) 思路图 ?...基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列...快速排序法应用实例: 要求: 对 [-9,78,0,23,-567,70] 进行从小到大的 排序,要求使用快速排序法。...=0;//辅助变量,交换数据时使用 //while循环的作用是让比pivot值小的放在左边,比pivot值大的放在右边 while (l<r){

    36510

    Java数据结构和算法总结-冒泡排序、选择排序、插入排序算法分析

    前言:排序算法的地位自然不必多说,许多工作中都用到了排序,就像学生成绩统计名次、商城商品销量排名、新闻的搜索热度排名等等。...本篇博文主要介绍常见的八种排序算法,总得来说,不同的排序算法不同的场景下都有着自己独特的优点,例如一下简单的冒泡排序、选择排序、插入排序不仅思路简单,有利于我们理解,而且小规模的数据量的处理并不逊色...  冒泡排序非常简单,也很易于理解,其逻辑思路就像水里面冒气泡一样,越往上气泡越大,也因此而得名冒泡排序,其具体规则如下:   1、从一组的数据的起始位置开始依次向后比较相邻两个数,   2、如果前一个数比后一个数大则交换位置...,某些理想情况下插入排序的时间复杂度可以达到 O(N),通常情况下,插入平均时间复杂度为:O(N^2)。...本篇的三种排序对比如下: 排序名称 时间复杂度 分析 级别 冒泡排序 O(N^2) 速度慢,交换次数多。

    97890

    Java基础算法详解

    万变不离其宗,只要熟悉了思想,灵活运用也不是难事。一般面试中最常考的是快速排序和归并排序,并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。...其实选择排序可以看成冒泡排序的优化,因为其目的相同,只是选择排序只有确定了最小数的前提下才进行交换,大大减少了交换的次数。...快速排序虽然高端,其实其思想是来自冒泡排序,冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端,而快速排序是比较和交换小数和大数,这样一来不仅把小数冒泡到上面同时也把大数沉到下面。...,上面代码基准数已经pivotKey中保存了,所以不需要每次交换都设置一个temp变量交换左右指针的时候只需要先后覆盖就可以了。...从平均时间来看,快速排序是效率最高的,快速排序最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是,n较大时归并排序使用时间较少,使用辅助空间较多。   2.

    25110

    算法和数据结构:堆排序

    很多应用,我们通常需要按照优先级情况对待处理对象进行处理,比如首先处理优先级最高的对象,然后处理次高的对象。...二叉堆的表现形式:我们可以使用数组的索引来表示元素二叉堆的位置。 ?...三 堆排序 ? 概念 运用二叉堆的性质,可以利用它来进行一种就地排序,该排序的步骤为: 1. 使用序列的所有元素,创建一个最大堆。 2. 然后重复删除最大元素。...经典的合并排序不是就地排序,它需要线性长度的额外空间,而快速排序其最坏时间复杂度为N2 ? 缺点:堆排序对时间和空间都进行了优化,但是: 1. 其内部循环要比快速排序要长。 2....并且其操作N和N/2之间进行比较和交换,当数组长度比较大的时候,对CPU缓存利用效率比较低。 3. 非稳定性排序

    69630

    快速排序Java实现_快速排序实现java

    高快省的排序算法 有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。 假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。...细心的同学可能已经发现,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。 这是为什么呢?...快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。...这样每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然最坏的情况下,仍可能是相邻的两个数进行交换。...因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。我们后面还会遇到“二分”思想,到时候再聊。

    1.4K10
    领券