-
快速排序和归并排序中一趟的理解(递归和非递归)
2021-01-12 12:41:09然而,我们知道,如果第一次选中的pivot处在了待排序元素最终结果中的中间位置。那么接下来的处理也是递归进行的, 如图(a)所示,在第一次调用Patition函数后,元素49被放到了最终位置,之后对49左侧位置元素调用...引:2019年408中数据结构一道考察快速排序的选择题
答案:D
定位:这道题在考察快速排序中一趟的概念。注意,基本的冒泡,插入,选择排序的一趟概念很容易理解,
接下来我们要讨论的是递归排序算法中(本文以快排和归并排序)讨论“趟”是否有意义。(先说结论,有,但并不像基本排序算法里那么简单,或者说,像基本算法里那么有普适性,归并排序只有非递归实现才有讨论趟的必要性,而快速排序更为复杂一些)
思路:
回想教材(《数据结构》严)里对一趟的定义
算法描述:
可见第一张图的过程实际上是递归形式实现的快排第一次调用Partition函数产生的结果。
然而,我们知道,如果第一次选中的pivot处在了待排序元素最终结果中的中间位置。那么接下来的处理也是递归进行的,
如图(a)所示,在第一次调用Patition函数后,元素49被放到了最终位置,之后对49左侧位置元素调用Qsort进行处理,
之后,关键关键的一步来了。
对 49左侧位置元素(27 48 13)调用Qsort处理时,首先调用Partition函数选出Pivot 27(默认第一个元素作pivot),
接下来呢?是立刻返回并去处理49右边的元素再调用一次Partition吗?并不是,这显然不是递归函数执行过程,
正确的执行过程是在对(27 48 13)这个左子表调用Partition后变为(13 27 48)接下来会继续对27左侧子表调用Qsort进行处理。
什么意思?等递归函数处理到 49右侧位置元素 时,其左侧元素都已经排好序了!
我们再看题干描述 趟 的概念:对尚未确定最终位置的所有元素进行一遍处理称为一趟。
发现问题了吗?如果是递归实现的快排,按题干的的意思,把所有尚未确定最终位置元素进行一遍处理,只有第一次选中的元素处在最终位置的边缘,才能保证有第二趟的概念,为什么?很简单,如果第一次选中的元素恰好在最终位置中间部分,比如教材里这个例子,那么严格意义上讲,这种情况下它的执行过程只有两趟(递归实现的快排)!最新更改:上面我的结论有问题,如果第一次pivot选在了中间,也是有第二趟概念的。以2019年408选择题为例:
D选项中12和32排在了最终位置,那么假设这是两趟的结果吧,那得满足什么条件?
或者说D选项怎么改才算正确?
答:2,5,12,28,16,32,72,60(只是其中一种可能)
没错,把12左侧元素改为顺序即为可能出现的情况,也就是对应的快排代码中递归的顺序是先对pivot左侧递归调用Qsort,左侧都已经有序了,
再对右侧进行一次递归调用Qsort,首先会调用Partition,那么刚进行完这次Partition后,得到的结果即为“第二趟”。注意这里的 趟 是题目定义的趟,对所有的未确定最终位置元素进行一遍处理。
(这里注意区分,我们平时讲的快速排序最坏情况下(初始情况完全有序),它的递归次数会达到最高(不是这里题目中的趟数))
简单反思下这个题纠结在哪了?快速排序我们平时记得多是Partition函数会使待排序数列产生一个位于最终位置的元素。
平时的教材中多是这样描述
就容易先入为主地认为1之后立刻执行2或者1,2同时进行(实际上的确有并行快速排序算法),
然而我们熟悉的多是递归形式实现的快速排序算法,PS:我又去查了下非递归实现的快排,多是用栈模拟..(把栈模拟出来,这难道就不算递归吗?)
这时另外一些稀奇古怪的问题冒出来了:所有的递归都可以改成非递归吗?手动压栈这种写法就不算递归了吗?(深坑,暂时不多做探讨,之所以会有这个问题是因为我看到了递归和非递归归并算法的实现)
即同样的,也有类似问题,问归并排序的“第二趟”处理结果类似问题
对序列25,57,48,37,12,82,75,29进行二路归并排序,第二趟归并后的结果为()。
A.25,57,37,48,12,82,29,75
B.25,37,48,57,12,29,75,82
C.12,25,29,37,48,57,75,82
D.25,57,48,37,12,82,75,29然而,我们平时写的也多是递归形式的,
//递归形式 void Msort(int a[], int l, int r) { mid = (l + r) / 2 Msort(a,l,mid); Msort(a,mid+1,r); merge(a,l,r,mid); //合并两个子表 }
还是和快排相似的问题:递归形式的归并排序有“趟”的概念吗?(如果按照和上一道题定义的趟的概念,是没有的!没有!)
那题就错了吗?不是,因为归并排序可以不借助栈,由循环结构实现。
非递归形式的归并排序思想是以2^k递增的间隔来划分待排序序列
void non_recur_msort(int arr[], int temp[], int left_end, int right_end) { for(int i = left_end; i <= right_end; i = 2*i) {//i 是划分长度,以2^k速度递增, for(int j = left_end; j <= right_end-i; j += 2*i) //j用来迭代处理每个划分长度下,待排序序列划分得到的子表 merge(arr, temp, j, j+i-1, Min(j + 2*i - 1 , right_end)); //子表长度为i,合并的两个子表左子表起始位置为j,mid为 j+i-1,右子表终止位置为j+2*i-1, } }
有些人会纠结奇数个元素怎么被处理的,看两张图,第一张是递归归并排序过程,第二张是非递归归并排序过程
第一张图——递归实现的归并排序是自顶向下划分(也就是划分时由大到小,再把小规模逐步求解),之后自底向上合并。
第二张图——非递归实现的归并排序的划分是由小到大(注意对比着上一张图看)
写到这,又回到了之前问题,快速排序的非递归形式会不会有类似(归并排序非递归方式)的实现?
似乎好多所谓的非递归只是手动实现了栈操作,然而我不确定这算不算是非递归。还有需要想到的应该是有没有并行快速排序的实现?
因为如果是并行实现的快排,那么同时调用Partition函数也就可以解释了
反思总结像一些最基本的排序如插入排序,冒泡排序,选择排序的实现。在讨论一趟概念的时候并不需要考虑这么多。Why?
因为这些最基本的算法思想是迭代,什么是迭代?是逐步求得结果并更新,和一趟的概念较契合:每迭代处理一次所有未排序元素,就会求解出一个未排序元素最终位置。
而快排和归并接触到的写法多是递归形式的,利用了分治的思想,既然涉及分治,就无法避免划分和求解问题的顺序问题。
出现这个问题的根源是我们用递归方式去思考问题划分问题时是正向进行的,而实际运算处理是自底向上(递归划分到最底层再向上求解)的,这一点很容易混淆。
那说了半天遇到这种问题怎么搞?
如果是快速排序问第二趟,那么只有第一趟选中的元素位于边缘,才能有第二趟的存在,第k趟以此类推,或者换句话说,快速排序如果运行产生了第2,3,4,5趟,那一定是出现了初始状态导致了最坏情况的问题(也就是初始状态基本有序,导致递归趟数最大),这种情况下,递归趟数和排序趟数是一样的。
如果是归并排序第二趟,那么默认是在讨论非递归形式的归并排序(注意不是把栈写出来就算了..从本质上讲你把栈写出来并不能算是把递归算法转化成了非递归算法)
总而言之,趟是个非常鸡肋的概念,国外教材中暂时没有见过类似于趟描述,进一步说,这个概念纯粹是造出来出题玩的,无聊至极
后记:
去stackoverflow上找了下non-recursion quicksort without a stack,没想到用英文搜问题抓到了我疑惑的实质:
非尾递归的递归转化成iterative(迭代)算法是有代价的,那就是格外的数据结构(栈),原理涉及计算理论里图灵完备性(然而我仍然纠结non-recursive这个概念,不过这玩意用了这么久总不可能所有人都错了吧..基本现在一提非递归就都在说用栈模拟...
StackOverflow上有一个人回复类似问题的角度值得记下来:
因为快速排序的思想是divide and conquer,因此在你不需要用到其他partition时候,必然需要额外的数据结构保存那些partition,因此是无法通过不添加额外数据结构来实现快速排序的
-
排序——归并排序法
2016-11-20 21:21:38归并排序法的执行流程如下: 原始序列:49 38 65 97 76 13 27 1.将原始序列看成是7个只含有一个元素的子序列...2.两两归并,形成若干有序二元组,第一趟二路归并排序结束后,结果如下: {38,49},{65,97},{13,7归并排序法的执行流程如下:
原始序列:49 38 65 97 76 13 27
1.将原始序列看成是7个只含有一个元素的子序列,显然这些子序列是有序的。
子序列1:49
子序列2:38
子序列3:65
子序列4:97
子序列5:76
子序列6:13
子序列7:27
2.两两归并,形成若干有序二元组,第一趟二路归并排序结束后,结果如下:
{38,49},{65,97},{13,76},{27}
然后再将这些序列看成是若干二元组子序列
子序列1:38 49
子序列2:65 97
子序列3:13 76
子序列4:27
3.继续两两归并,形成若干有序四元组,第二趟二路归并结束后,结果如下:
{38 49 65 79},{13 27 76}
4.最后将这些子序列在进行一次归并,就完成了整个二路归并
13 27 38 49 65 76 79时间复杂度为O(nlog(2)n)
空间复杂度O(n) -
每日一算法之归并排序
2014-03-27 11:58:16第一趟排序,两个数字一组排序后结果为{1,3}{0,0}{4,8}{6},第二趟排序,{0,0,1,3}{4,6,8}第三趟排序,{0,0,1,3,4,6,8} 显然归并排序的主要操作在于合并操作(merge). ok,不多说了,关于排序的讲解网上很多,这里...归并排序的复杂度是O(nlogn) 性能优良,基本思想是这样的:乱序的数列,这里假设,3,1,0,0,4,8,6 。
- 第一趟排序,两个数字一组排序后结果为{1,3}{0,0}{4,8}{6},
- 第二趟排序,{0,0,1,3}{4,6,8}
- 第三趟排序,{0,0,1,3,4,6,8}
显然归并排序的主要操作在于合并操作(merge).ok,不多说了,关于排序的讲解网上很多,这里直接上代码。void merge(int *a,int p,int q,int r){ int n1 = q-p+1; int n2 = r-q; int *a1 = new int[n1]; int *a2 = new int[n2]; int p1 = p; int q1 = q+1; int i = 0;int j = 0; while(i<n1) a1[i++] = a[p1++];//p--q有序数组存入a1 while(j<n2) a2[j++] = a[q1++];//q+1--r有序数组存入a2 i = 0; j = 0; while(i<n1&&j<n2) if(a1[i]<=a2[j]) a[p++] = a1[i++]; else a[p++] = a2[j++]; while(i<n1) a[p++] = a1[i++]; while(j<n2) a[p++] = a2[j++]; } void mergeSort(int *a,int p,int r){ if(p<r){ int q = (p+r)/2; mergeSort(a,p,q); mergeSort(a,q+1,r); merge(a,p,q,r); } }
-
排序算法之归并排序
2019-01-12 09:42:37因为两个表是已排序的,所以若将输出放到第三个表中,结果也是排好序的,合并算法可以通过对输入数据一趟排序来完成.递归调用分离的两个子表可求得结果. 归并算法策略 基本的合并算法是取两个输入数组A和B,一个输出...归并排序原理
该算法的基本操作是合并两个已排序的表.因为两个表是已排序的,所以若将输出放到第三个表中,结果也是排好序的,合并算法可以通过对输入数据一趟排序来完成.递归调用分离的两个子表可求得结果.
归并算法策略
基本的合并算法是取两个输入数组A和B,一个输出数组C,以及3个计数器Actr,Bctr,Cctr,它们的初始位置对应数组的开始端.A[Actr]和B[Bctr]中较小者被拷贝到C中的下一个位置,相关的计数器向前推进一步.当两个各输入表有一个用完时,则将另一个表中剩余的部分拷贝到C中.合并例程工作图如下:
如果数组A含有1,13,24,26,数组B含有2,15,27,38,那么该算法的过程如下:首先,比较在1和2之间进行,1被添加到C中,然后13和2进行比较.
2被添加到C中,然后13和15比较
13被添加到C中,接下来比较24和15,这样一直进行到26和27比较
将26添加到数组C中,数组A已经用完.
然后将数组B的其余部分拷贝到C中.
合并两个已排序的表的时间显然是线性的,因为最多进行N-1次比较,其中N是元素的总数.
归并排序代码实现
public static void mergeSort(int[] a){ int[] tmpArray = new int[a.length]; mergeSort(a,tmpArray,0,a.length-1); } public static void mergeSort(int[] a,int[] tmpArray, int left, int right){ if(left < right){ int center = (left + right )/2; mergeSort(a,tmpArray,left,center); mergeSort(a,tmpArray,center+1,right); merge(a,tmpArray,left,center+1,right); } } public static void merge(int[] a, int[] tmpArray, int leftPos, int rightPos, int rightEnd){ int leftEnd = rightPos -1; int tmpPos = leftPos; int numElements = rightEnd - leftPos + 1; while(leftPos<=leftEnd&&rightPos<=rightEnd){ if(a[leftPos]<a[rightPos]) tmpArray[tmpPos++] = a[leftPos++]; else tmpArray[tmpPos++] = a[rightPos++]; } while(leftPos<=leftEnd) tmpArray[tmpPos++] = a[leftPos++]; while(rightPos<=rightEnd) tmpArray[tmpPos++] = a[rightPos++]; for(int i = 0; i < numElements;i++,rightEnd--){ a[rightEnd] = tmpArray[rightEnd]; } }
在Java中,快速排序也用作基本类型的标准库排序.这里,比较和数据移动的开销是类似的,因此使用少得多的数据移动足以补偿那些附加的比较而且还有盈余.
时间复杂度
归并排序以
最坏情形时间运行,而所使用的比较次数几乎是最优的.
-
《大话数据结构》第9章 排序 9.8 归并排序(下)
2015-07-18 19:10:36我们来分析一下归并排序的时间复杂度,一趟归并需要将SR[1]~SR[n]中相邻的长度为h的有序序列进行两两归并。并将结果放到TR1[1]~TR1[n]中,这需要将待排序序列中的所有记录扫描一遍,因此耗费O(n)时间,而由完全... -
数据结构学习第10篇 - 排序算法的比较冒泡排序、直接插入排序、选择排序、希尔排序、快速排序、归并排序和...
2019-04-04 10:01:06排序算法的比较 内排序的方法有许多,教材上面提到的有:...需要输出每一趟排序的中间结果; 2.为方便排序算法的比较,不同排序算法请使用相同数据。 #include <stdio.h> #include <stdlib.h> #inc... -
归并排序的非递归算法
2019-07-06 01:08:41用函数实现归并排序(非递归算法),并输出每趟排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出每趟排序的结果,数据之间用一个... -
二路归并排序
2016-05-02 14:02:081、执行流程 原始序列:49、38、65、97、76、13、27 (1)将原始序列看成是7个只含有一个元素的子序列,显然这些子序列都是有序的。 子序列1:49 ...第一趟二路归并排序结束,结果如下: {38、49,},{65、 -
归并排序(非递归算法)
2014-06-06 13:14:58用函数实现归并排序(非递归算法),并输出每趟排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出每趟排序的结果,数据之间用一个... -
SCAU-8645归并排序(非递归算法)
2020-06-13 15:37:18用函数实现归并排序(非递归算法),并输出每趟排序的结果 输入格式 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 输出格式 每行输出每趟排序的结果,数据之间用一个空格分隔 ... -
数据结构与算法 (六) 归并排序
2018-12-23 16:54:22归并排序的思想 将已经排序的文件进行合并 得到完全排序的文件 合并时只要比较各个子文件的第一个记录的排序码最小的那个记录就是排序后的第1个记录 取出这记录然后继续比较各子文件的第1个记录 便可找出排序后的... -
数据结构 归并排序(非递归算法)
2010-12-13 20:06:39用函数实现归并排序(非递归算法),并输出每趟排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出每趟排序的结果,数据之间用一个空格分隔 Sample... -
8645 归并排序(非递归算法)(SCAU数据结构习题)
2020-06-09 21:27:05用函数实现归并排序(非递归算法),并输出每趟排序的结果 输入格式 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 输出格式 每行输出每趟排序的结果,数据之间用一个空格分隔 ... -
归并排序(非递归)----C语言弟弟版简单易懂
2019-03-26 14:08:57Description用函数实现归并排序(非递归算法),并输出每趟排序的结果 输入格式第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 输出格式每行输出每趟排序的结果,数据之间用一个... -
---C语言八种排序算法(冒泡排序,选择排序,直接插入排序,希尔排序,快速排序,堆排序,二路归并排序,...
2018-10-13 21:52:47一、冒泡排序 思路:首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两记录交换,然后比较第二个...此过程为第一趟冒泡排序,结果使得最大的关键字被放置到最后一个记录的位置上。 ... -
排序算法大集锦_二路归并排序_2&3(分治思想)
2015-05-26 14:28:22第一段代码和合并排序差不多,用它来和第二段代码——二路归并排序作对比。 这一系列博客的特点就是——给出每趟排序的结果 本来想着好好写一下过程,弄个图片什么的,不过觉得网上的解析太多了... -
归并算法
2011-11-19 19:11:38用函数实现归并排序(非递归算法),并输出每趟排序的结果 输入格式 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 输出格式 每行输出每趟排序的结果,数据之间用一个... -
每日一题32:排序
2015-05-31 08:41:38排序概述排序用途广泛,比如为数据库查询结果按时间排序,最小生成树算法中对边按权重排序,背包问题中对物品按大小排序等等。... //放到他正确的位置上,每一趟扫描从输入数组第一个元素开始,依次 -
排序算法
2019-11-07 23:16:42排序算法 排序算法种类 插入排序 直接插入排序 希尔排序 ...归并排序 ...通过对待排序序列从前向后(从下标较小元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前向后...第一趟排序后结果... -
常见排序算法
2021-01-23 13:27:31文章目录`冒泡排序``选择排序``插入排序``希尔排序``快速排序``归并排序``基数排序` 冒泡排序 n个数比较n-1趟,每一趟选出最大的数 在一趟中,从前往后相邻两个比较如果前面的比后面的数大,则交换顺序 优化:当某一... -
排序进阶基础
2020-09-24 18:44:443.1、排序的分类 3.1.1、排序的分类 根据排序过程所用策略的...假设记录个数为8,输入关键字序列为(56,68,25,45,90,38,10,72),每一趟插入排序的结果如图所示 第i躺插入排序若需将记录L.rcd[i+1]插入到有序区 -
第十章 排序作业及答案数据结构
2019-08-23 15:17:26分别写出希尔排序(d=5)、快速排序、堆排序、归并排序第一趟升序排序后的结果(其中堆排序的第一趟指序列完成初始建堆、将堆顶元素置为最末位置后其余元素调整为堆的结果)(每个3分)。 希尔排序: 快速排序: 堆... -
【数据库原理系列】多趟扫描算法
2020-11-28 00:01:07第一趟:划分子集,并使子集具有某种特性,如有序或相同散列值等 第二趟:处理全局性内容的操作,形成结果关系。如多子集间的归并排序,相同散列值子集的操作等 多路归并排序 内排序和外排序 内排序问题: -
java排序方法
2015-08-30 00:36:266,归并排序 一,冒泡排序 算法描叙: 设待排序记录序列中的记录个数为n 一般地,第i趟起泡排序从1到n-i+1 依次比较相邻两个记录的关键字,如果发生逆序,则交换之。 其结果是这n-i+1个记录中,... -
几种常用的排序算法C实现
2020-08-30 16:27:52几种常用的排序算法C实现冒泡排序选择排序插入排序快速...第一趟有n个数据,需要比较n-1次,可以将最大的数挪到数组最末端,第二趟只有n-1个数据了,只需要比较n-2次… 每一趟可以决出一个数,n个数只要决出n-1个数的 -
数据结构内部排序实验报告
2015-06-22 14:17:553、如果上述8个整数按照升序输入,即k1={ 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 },输出各种排序算法每一趟排序的结果,观察关键字次序的变化。 4、如果上述8个整数按照降序输入,即k2={ 68 , 45 , 33 , 30 , 21 ... -
Python语言实用教程第9章 数据结构与操作.ppt
2020-01-16 18:54:46常用的排序算法有如下8种它们分别为 选择排序冒泡排序插入排序归并排序快速排序堆排序基数排序希尔排序等 9.2.2 排序 1选择排序 基本思想选择排序的思想非常直接就是从所有序列中先找到最小或最大的然后放到第一个...
-
解放思想,实事求是,团结一致向前看
-
浙江科技学院《基础工程》复习.pdf
-
移动支付网-2020数字人民币发展研究报.pdf
-
leetcode-145:树的后序遍历
-
宪法学--期末复习知识点总结.pdf
-
基于SSM实现的房屋租赁系统【附源码】(毕设)
-
NFS 实现高可用(DRBD + heartbeat)
-
009_连通页面组件
-
【图像识别】基于LBP+LPQ算法融合人脸表情识别matlab源码
-
刑法学--期末复习题(含答案).pdf
-
用Go语言来写区块链(一)
-
MySQL 触发器
-
武汉理工大学《物理化学》期末考试试卷(含答案).pdf
-
Docker从入门到精通
-
浙江大学《微积分(1)》历年期末考试试题.pdf
-
mybatisplus的VO分页
-
C/C++反汇编解密
-
app软件测试全栈系列精品课程
-
朱老师鸿蒙系列课程第1期-3.鸿蒙系统Harmonyos源码配置和管理
-
西南科技大学《自动控制原理》试题库(含答案).pdf