快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（）算法设计策略。A、分治B、动态规划C、贪心D、回溯
题目
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（）算法设计策略。
- A、分治
- B、动态规划
- C、贪心
- D、回溯
相似考题
更多“快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（）算法设计策略。A、分治B、动态规划C、贪心D、回溯”相关问题
-
第1题：
阅读以下算法说明，根据要求回答问题1～问题3。
[说明]
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。
1．分解：选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1]中的每个元素，小于A[q+1..r]中的每个元素。q的值在划分过程中计算。
2．递归求解：通过递归的调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。
3．合并：快速排序在原地排序，故无需合并操作。
下面是快速排序的伪代码，请将空缺处(1)～(3)的内容填写完整。伪代码中的主要变量说明如下。
A：待排序数组
p,r：数组元素下标，从p到r
q：划分的位置
x：枢轴元素
i：整型变量，用于描述数组下标。下标小于或等于i的元素的值，小于或等于枢轴元素的值
j：循环控制变量，表示数组元素下标
正确答案：这是一道考查快速排序算法伪代码的分析题。快速排序是对冒泡排序的一种改进其基本思想是：通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。快速排序最核心的处理是进行划分即PARTITION操作：根据枢轴元素的值把一个较大的数组分成两个较小的子数组一个子数组的所有元素的值小于等于枢轴元素的值一个子数组的所有元素的值大于枢轴元素的值而子数组内的元素不排序。划分时以最后一个元素为枢轴元素从左到右依次访问数组的每一个元素判断其与枢轴元素的大小关系并进行元素的交换如图2-30所示。
在[问题1]所给出的伪代码中当for循环结束后A[p..i]中的值应小于等于枢轴元素值x而A[i+1..r-1]中的值应大于枢轴元素值x。此时A[i+1]是第一个比A[r]大的元素因此A[r]与A[i+1]进行交换得到划分后的两个子数组。PARTITION操作返回枢轴元素的位置因此返回值为i+l。
这是一道考查快速排序算法伪代码的分析题。快速排序是对冒泡排序的一种改进，其基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序最核心的处理是进行划分，即PARTITION操作：根据枢轴元素的值，把一个较大的数组分成两个较小的子数组，一个子数组的所有元素的值小于等于枢轴元素的值，一个子数组的所有元素的值大于枢轴元素的值，而子数组内的元素不排序。划分时，以最后一个元素为枢轴元素，从左到右依次访问数组的每一个元素，判断其与枢轴元素的大小关系，并进行元素的交换，如图2-30所示。
在[问题1]所给出的伪代码中，当for循环结束后，A[p..i]中的值应小于等于枢轴元素值x，而A[i+1..r-1]中的值应大于枢轴元素值x。此时A[i+1]是第一个比A[r]大的元素，因此A[r]与A[i+1]进行交换，得到划分后的两个子数组。PARTITION操作返回枢轴元素的位置，因此返回值为i+l。
-
第2题：
阅读下列说明、流程图和算法，将应填入(n)处的字句写在对应栏内。
【流程图说明】
下图所示的流程图5.3用N-S盒图形式描述了数组Array中的元素被划分的过程。其划分方法；以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于Array[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。
【算法说明】
将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int Array[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组Ar ray中的下标。递归函数void sort(int Array[]，int L，int H)的功能是实现数组Array中元素的递增排序。
【算法】
void sort(int Array[]，int L，int H){
if (L＜H) {
k=p(Array，L，H)；/*p()返回基准数在数组Array中的下标*/
sort((4))；/*小于基准数的元素排序*/
sort((5))；/*大于基准数的元素排序*/
}
}
正确答案：(1)j←j-1
(1)j←j-1 -
第3题：
●试题二
阅读下列说明、流程图和算法，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
下面的流程图(如图3所示)用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：
【流程图】
图3流程图
【算法说明】
将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[]，int L，int H)的功能是实现数组A中元素的递增排序。
【算法】
void sort (int A[]， int 1，int H){
if ( L<H){
k=p(A，L，R)；//p()返回基准数在数组A中的下标
sort( (4) )；//小于基准数的元素排序
sort( (5) )；//大于基准数的元素排序
}
}
正确答案：
●试题二【答案】(1)j--(2)i++(3)A[i]←pivot或[j]←pivot(4)A，L，k-1或A，L，k(5)A，k+I，H或A，k，H【解析】题目考查快速排序算法。快速排序采用了一种分治的策略，通常称为分治法。其基本思想是：将原问题分解为若干个规模更小，但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序的具体过程为：第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为基准，将所有记录分成2组，第一组各记录的排序码都小于等于该排序码，第二组各记录的排序码都大于该排序码，并把该记录排在这2组中间，这个过程称为一次划分。第二步，采用同样的方法，对划分出来的2组元素分别进行快速排序，直到所有记录都排到相应的位置为止。在进行一次划分时，若选定以第一个元素为基准，就可将第一个元素备份在变量pivot中，如图中的第①步所示。这样基准元素在数组中占据的位置就空闲出来了，因此下一步就从后向前扫描。如图中的第②步所示，找到一个比基准元素小的元素时为止，将其前移，如图中的第③步所示。然后再从前向后扫描，如图中的第④步所示，找到一个比基准元素大的元素时为止，将其后移，如图中的第⑤步所示。这样，从后向前扫描和从前向后扫描交替进行，直到扫描到同一个位置为止，如图中的第⑥步所示。由题目中给出的流程图可知，以第一个元素作为基准数，并将A[low]备份至pivot，i用于从前向后扫描的位置指示器，其初值为low，j用于从后往前扫描的位置指示器，其初值为high。当i<j时进行循环：1）从后向前扫描数组A，在i<j的情况下，如果被扫描的元素A[j]>pivot，就继续向前扫描(j--)；如果被扫描的元素A[i]<pivot就停止扫描，并将此元素的值赋给目前空闲着的A[i]。2）这时，再从前向后扫描，在i<j的情况下，如果被扫描的元素A[j]<pivot，就继续向后扫描(i++)；如果被扫描的元素A[j]>pivot就停止扫描，并将此元素的值赋给目前空闲着的A[j]。3）这时又接第(1)步，直到i>j时退出循环。退出循环时，将pivot赋给当前的A[i](A[i]←pivot)。递归函数的目的是执行一系列调用，直到到达某一点时递归终止。为了保证递归函数正常执行，应该遵守下面的规则：1）每当一个递归函数被调用时，程序首先应该检查基本的条件是否满足，例如，某个参数的值等于0，如果是这种情形，函数应停止递归。2）每次当函数被递归调用时，传递给函数一个或多个参数，应该以某种方式变得"更简单"，即这些参数应该逐渐靠近上述基本条件。例如，一个正整数在每次递归调用时会逐渐变小，以至最终其值到达0。本题中，递归函数sort(intA[]，intL，intH)有3个参数，分别表示数组A及其下界和上界。根据流程图可知，这里的L相当于流程图中的i，这里的H相当于流程图中的j。因为P()返回基准数所在数组A中的下标，也就是流程图中最后的"A[i]←pivot"中的i。根据快速排序算法，在第一趟排序后找出了基准数所在数组A中的下标，然后以该基准数为界(基准数在数组中的下标为k)，把数组A分成2组，分别是A[L，…，k-1]和A[k+l，…，H]，最后对这2组中的元素再使用同样的方法进行快速排序。 -
第4题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（请作答此空）算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n)，则快速排序算法的最好和最坏情况下的时间复杂度为（ ）。A.分治
B.动态规划
C.贪心
D.回溯答案：A解析：快速排序采用分治法的思想。快速排序最好情况的时间复杂度是O(nlog2n)。最坏情况下，即初始序列按关键字有序或者基本有序时，快速排序的时间复杂度为O(n2)。 -
第5题：
根据枢轴元素(或基准元素)划分序列而进行排序的是( )。A.快速排序
B.冒泡排序
C.简单选择排序
D.直接插入排序答案：A解析：本题考查数据结构与算法基础知识。
快速排序的基本思想是：通过一趟排序将待排的记录划分为独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行快速排序，以达到整个序列有序。
划分时从待排序列中选一个元素作为枢轴元素，将不大于枢轴元素者和不小于枢轴元素者分开。 -
第6题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（61）算法设计策略。已知确定着基准元素操作的时间复杂度为O（n），则快速排序算法的最好和最坏情况下的时间复杂度为（62）。A.O（n）和O（nlgn）
B.O（n）和O（n2）
C.O（nlgn）和O（nlgn）
D.O（nlgn）和O（n2）答案：D解析：将数据分成若干份，每份单独处理后再合并，其思想为分治。理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为O（nlgn）。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为O（n），”次操作的总复杂度为O（n2）。 -
第7题：
关于冒泡排序算法的基本思想，下列说法正确的是（）。
- A、一个轮次一个轮次地处理。将元素分成已排序元素集合和未排序元素集合两部分。开始时已排序元素集合为空，在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合，直到未排序元素集合为空时则算法结束
- B、一个元素一个元素地处理。先从第一个元素处理，依次与其它元素比较后放入到正确排序的位置，再处理下一个元素，直到处理完所有元素则算法结束
- C、一个轮次一个轮次地处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较，根据排序要求决定是否交换两个元素，直到某一轮次没有元素交换则算法结束
- D、一个元素一个元素地处理。先从最后一个元素处理，依次与其它元素比较后放入到正确排序的位置，再处理下一个元素，直到处理完所有元素则算法结束
正确答案:C -
第8题：
从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于或等于所选元素，而此时所选元素处在排序的最终位置。这种排序法称为（）排序法。
正确答案:快速 -
第9题：
在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。
- A、随机选择一个元素作为划分基准
- B、取子序列的第一个元素作为划分基准
- C、用中位数的中位数方法寻找划分基准
- D、以上皆可行。但不同方法，算法复杂度上界可能不同
正确答案:D -
第10题：
每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做（）。
- A、冒泡排序
- B、堆排序
- C、快速排序
- D、归并排序
正确答案:C -
第11题：
填空题在快速排序方法中，进行每次划分时，是从当前待排序区间的（）向（）依次查找出处于逆序的元素并交换之，最后将基准元素交换到一个确定位置，从而以该位置把当前区间划分为前后两个子区间。正确答案： 两端,中间解析： 暂无解析 -
第12题：
填空题从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于或等于所选元素，而此时所选元素处在排序的最终位置。这种排序法称为（）排序法。正确答案： 快速解析： 暂无解析 -
第13题：
通过设置基准(枢轴)元素将待排序的序列划分为两个子序列,使得其一个子序列的元素均不大于基准元素,另一个子序列的元素均不小于基准元素,然后再分别对两个子序列继续递归地进行相同思路的排序处理,这种排序方法称为()。A、快速排序
B、冒泡排序
C、简单选择排序D、归并排序
正确答案：A
-
第14题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了 (61) 算法设计策略。已知确定基准元素操作的时间复杂度为
，则快速排序算法的最好和最坏情况下的时间复杂度为 (62) 。A.分治
B.动态规划
C.贪心
D.回溯
正确答案：A
本题考查快速排序算法。快速排序算法是应用最为广泛的排序算法之一。其基本思想是将n个元素划分为两个部分：一部分元素值小于某个数；另一部分元素值大于某个数，该数的位置确定；然后进一步划分前面部分和后面部分。根据该叙述，可以知道，这里采用的是分治算法设计策略。由于已知划分操作的时间复杂度为，不需要合并子问题的答案。对于最好的情况，应该是每次划分都把n个元素划分为大约2个n/2个元素的子数组，此时T(n)=2T(n/2)+解该递归式，可得时间复杂度为。若刚好划分的极度不均衡，即每个划分刚好把n个元素划分为一边0个元素，一边n-l个元素，此时T(n)=T(n/1)+解该递归式，可得时间复杂度为。 -
第15题：
● 如果待排序序列中两个元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。 （41） 是稳定的排序方法，因为这种方法在比较相邻元素时，值相同的元素并不进行交换。
（41）
A. 冒泡排序
B. 希尔排序
C. 快速排序
D. 简单选择排序
正确答案：A
-
第16题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（ ）算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n)，则快速排序算法的最好和最坏情况下的时间复杂度为（请作答此空）。
答案：D解析：快速排序采用分治法的思想。快速排序最好情况的时间复杂度是O(nlog2n)。最坏情况下，即初始序列按关键字有序或者基本有序时，快速排序的时间复杂度为O(n2)。 -
第17题：
通过设置基准（枢轴）元素将待排序的序列划分为两个子序列,使得其一个子序列的元素均不大于基准元素,另一个子序列的元素均不小于基准元素,然后再分别对两个子序列继续递归地进行相同思路的排序处理,这种排序方法称为（ ）。A.快速排序
B.冒泡排序
C.简单选择排序
D.归并排序答案：A解析：快速排序的基本思想是,通过一轮的排序将序列分割成独立的两部分,其中一部分序列的关键字（这里主要用值来表示）均比另一部分关键字小。继续对长度较短的序列进行同样的分割，最后到达整体有序。在排序过程中,由于已经分开的两部分的元素不需要进行比较,故减少了比较次数,降低了排序时间。详细描述:首先在要排序的序列a中选取一个中轴值,而后将序列分成两个部分,其中左边的部分b中的元素均小于或者等于中轴值,右边的部分c的元素均大于或者等于中轴值,而后通过递归调用快速排序的过程分别对两个部分进行排序,最后将两部分产生的结果合并即可得到最后的排序序列。 -
第18题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（61）算法设计策略。已知确定着基准元素操作的时间复杂度为O（n），则快速排序算法的最好和最坏情况下的时间复杂度为（62）。A.分治
B.动态规划
C.贪心
D.回溯答案：A解析：将数据分成若干份，每份单独处理后再合并，其思想为分治。理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为O（nlgn）。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为O（n），”次操作的总复杂度为O（n2）。 -
第19题：
在快速排序方法中，进行每次划分时，是从当前待排序区间的（）向（）依次查找出处于逆序的元素并交换之，最后将基准元素交换到一个确定位置，从而以该位置把当前区间划分为前后两个子区间。
正确答案:两端；中间 -
第20题：
对用数组存储的线性表（16，15，32，11，6，30），用快速排序算法进行由小到大排序，若排序下标范围为0~5，选择元素16作为支点，调用一趟快速排序算法后，元素16在数组中的下标位置为（）
正确答案:3 -
第21题：
在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法对n个元素进行划分，应如何选择划分基准？下面（）答案解释最合理。
- A、随机选择一个元素作为划分基准
- B、取子序列的第一个元素作为划分基准
- C、用中位数的中位数方法寻找划分基准
- D、以上皆可行。但不同方法，算法复杂度上界可能不同
正确答案:D -
第22题：
冒泡排序算法中降序排序指的是（）
- A、从高到低排列数组元素值
- B、从低到高排列数组元素的值
- C、由横向到纵向排列数组元素的值
- D、由纵向到横向排列数组元素的值
正确答案:A -
第23题：
单选题在寻找n个元素中第k小元素问题中，如使用快速排序算法思想，运用分治算法对n个元素进行划分，应如何选择划分基准？下面（）答案解释最合理。A随机选择一个元素作为划分基准
B取子序列的第一个元素作为划分基准
C用中位数的中位数方法寻找划分基准
D以上皆可行。但不同方法，算法复杂度上界可能不同
正确答案： B解析： 暂无解析