快速排序的递归深度问题对序列2，1，3进行快速排序，递归深度应该是1，可是按照最好情况下的公式，[log(n+1)](向

快速排序思想：利用分治法,将原问题分解为若干个规模更小但结构与原问题相似的子问题.递归地解这些子问题,然后将这些子问题的解组合为原问题的解.
快速排序划分步骤：
第一次划分：关键字（45）
1.（24,78,55,39,41,79,95,45）
2.（24,45,55,39,41,79,95,78）
3.（24,41,55,39,45,79,95,78）
4.（24,41,45,39,55,79,95,78）
5.（24,41,39,45,55,79,95,78）
第二次划分：关键字（24）
1.（24,41,39,55,79,95,78）
第三次划分：关键字（41）
1.（24,39,41,45,55,79,95,78）
第四次划分：关键字（55）
1.（24,39,41,45,55,79,95,78）
第五次划分：关键字（79）
1.（24,39,41,45,55,78,95,79）
2.（24,39,41,45,55,78,79,95）

出题人应该不会这么坑爹吧!表示只能给出下面回答：
（1）最坏时间复杂度
　最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个.
　因此,快速排序必须做n-1次划分,第i次划分开始时区间长度为n-i+1,所需的比较次数为n-i(1≤i≤n-1),故总的比较次数达到最大值：
Cmax = n(n-1)/2=O(n2)
　如果按上面给出的划分算法,每次取当前无序区的第1个记录为基准,那么当文件的记录已按递增序(或递减序)排列时,每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录,则快速排序所需的比较次数反而最多.
（2） 最好时间复杂度
　在最好情况下,每次划分所取的基准都是当前无序区的"中值"记录,划分的结果是基准的左、右两个无序子区间的长度大致相等.总的关键字比较次数：
0(nlgn)
注意：
　用递归树来分析最好情况下的比较次数更简单.因为每次划分后左、右子区间长度大致相等,故递归树的高度为O(lgn),而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n,故整个排序过程所需要的关键字比较总次数C(n)=O(nlgn).
　因为快速排序的记录移动次数不大于比较的次数,所以快速排序的最坏时间复杂度应为0(n2),最好时间复杂度为O(nlgn).

快速排序：设要排序的数组是A[0]……A[N-1],首先任意选取一个数据（通常选用第一个数据）作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序.

注意问题；元素的移动数最多
一趟快速排序过程：
A.
70 , 65 , 34 , 82 , 53 , 25 , 90
25 , 65 , 34 , 82 , 53 , 70 , 90
25 , 65 , 34 , 70 , 53 , 82 , 90
25 , 65 , 34 , 53 , 70 , 82 , 90
B.
82 , 53 , 25 , 70 , 65 , 34 , 90
34 , 53 , 25 , 70 , 65 , 82 , 90
C.
34 , 25 , 53 , 65 , 90 , 82 , 70
25 , 34 , 53 , 65 , 90 , 82 , 70
D.
53 , 25 , 65 , 70 , 34 , 90 , 82
34 , 25 , 65 , 70 , 53 , 90 , 82
34 , 25 , 53 , 70 , 65, 90 , 82
E.
65 , 34 , 82 , 70 , 25 , 53 , 90
53 , 34 , 82 , 70 , 25 , 65 , 90
53 , 34 , 65 , 70 , 25 , 82 , 90
53 , 34 , 25 , 70 , 65 , 82 , 90
53 , 34 , 25 , 65 , 70 , 82 , 90

其实这两个结果都不妨碍最终结果
因为 6把小于6和大于6的数分开了
已经达到了目的
而且我在算法导论里看到的快速排序里的划分和你说的划分算法是不同的
就是说目的一样 不会影响算法

以下上下对应
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]、A[7]：
24 19 32 43 38 6 13 22
初始关键数据KEY=A[0]=24,第一轮排序中一直不变
第一次从后往前搜,A[0]>A[7],变换,24 22对换,A[0]=22,A[7]=24,KEY=A[7]=24
结果：22 19 32 43 38 6 13 24
第二次从前往后搜,A[1]A[7],变换,32 24对换,A[2]=24,A[7]=32,KEY=A[2]=24
结果：22 19 24 43 38 6 13 32
第三次从后往前搜,A[2]>A[6],变换,24 13对换,A[2]=13,A[6]=24,KEY=A[6]=24
结果：22 19 13 43 38 6 24 32
第四次从前往后搜,A[3]>A[6],变换,43 24对换,A[3]=24,A[6]=43,KEY=A[3]=24
结果：22 19 13 24 38 6 43 32
第五次从后往前搜,A[3]>A[5],变换,24 6对换,A[3]=6,A[5]=24,KEY=A[5]=24
结果：22 19 13 6 38 24 43 32
第六次从后往前搜,A[4]>A[5],变换,38 24对换,A[4]=24,A[5]=38,KEY=A[4]=24
结果：22 19 13 6 24 38 43 32
即最终排序结果为：22 19 13 6 24 38 43 32
之后对24两边的子集分别按以上方法排序{22 19 13 6} 24 {38 43 32}

首先将后面找到比基准值小的放到基准值的位置（或者是和基准值交换）
这样就是将3放到最前面了
...
所以答案是C

是A
最坏的情况是当这个列本来就有序的情况,这样的情况是很坏的,达到了N平方的复杂度.

第一次排序：2,8,4,6,12,16,10,18,28,20,30
第二次排序：2,4,6,8,10,12,16,18,20,28,30

是的,http://blog.163.com/ainixiaobao-99/blog/static/1409888120084159263955/仔细看看这篇文章就会理解.
竟然没有分.

一般去关键字为第一个数 这里就是取20
开始:20,15,14,18,21,36,40,10
第一步:10,15,14,18,21,36,40,20
第二步:10,15,14,18,20,36,40,21
现在第一趟快速排序完成了 小于20的都在20前面 大于20的都在20的后面

先将基准5用一个中间变量保存,接着用前后两个标志,一个从前往后,另外一个从后往前,下面循环步骤执行的前提是前标志的位置小于后标志的位置
首先从后往前,如果找到第一个比5小的关键字（现在就是3）,就放到5原来的位置,
然后从前往后,直到第一个比5大（现在就是6）,放到3原来的位置
继续下去就会两个标志碰头了,循环终止
然后将基准5放到6原先的空位
这样第一趟排序的结果就是：C
比基准5小的都在其左边,比基准5大的都在其右边
接下来再对其左边与右边的分别这样排序直到序列只有一个元素为止
例如：
初始关键字：49,38,65,97,76,13,27,49*
第一趟排序后：27,38,13,49,76,97,65,49*

18 24 1 39 20 40 43
1 18 24 39 20 40 43
1 18 20 24 39 40 43
1 18 20 24 39 40 43
1 18 20 24 39 40 43
1 18 20 24 39 40 43
1 18 20 24 39 40 43
Press any key to continue

快排的规则是：在每一排序完成后,总有一个数处在它最后所应该在的位置上.然后将一个问题分成2个问题.
一趟排序完成之后,选择数有个特点,就是：
如果从小到大排列,则其左边都比它大,右边都比它小；
从大到小排列同理.
上面两个选项,可能的中间数
1)是73和68,73满足左边都比它大,右边都比它小.68左有93右有69
2)是18和93,18左有68、69,右有93,73；93左有18,右有73
2的两个数都不是,1的有一个数是.
当然是1了.

是答案C正确啊,因为每一趟都能一分为二（两边序列个数为总长度一半）,递归树高度最小,所以比较次数最少

若以第一个数7为枢轴进行升序排序的话,第一次完成后是：（1,3,5,7,9,12,8,15） ,原理不明白再问我

快速排序是从头和尾开始对元素进行比较,有可能把关键值相同的两个元素调换了位置,所有说是不稳定的,比如对 2 4 1 3 1进行排序,第一趟就把后面的1换到前面去,形成了不稳定排序

1.确定块来历不明的元素;
2块来历不明的元素.由于冒泡排序算法的条款,设置一个标志,标志记录行程排序记录交换,以确定当前的排序区域是否有自然的和有序的.冒泡排序这个问题,用最少的时间.
记录时,一直键的初始值增量有序,快速排序,因为每个选定的中间元件是最小的,它被分成左,右两个区域是空的,以及其他比原来的面积的至少一种元素,只有在旅途中的元素比较的数量小于1,所以总的时间消耗是O（N ^ 2）,所以这个问题的快速排序方法最耗费时间的.
[答案]冒泡排序,快速排序.
3.成叠的S1,S2拿出一叠
入队的时候,在
尾出队入堆栈S1,如果栈S2不为空,然后出来.
否则11到的堆栈S1,堆栈,和11进入堆栈S2,然后出来.
否则,错误
判处空间,以确定是否两个堆栈同时空气

第一趟：20 38 10 49 75 90 66
第二趟：10 20 38 49 66 75 90

这道题的话我不清楚是不是应该把每个选项的步骤给列下来,但是我很迷惑.
快速排序实际上是以每次都以当前数组的第一位作为基准作为比较的,所以说第一位的值的位置更靠中间（排序好的）,二分法后就均匀,速度就会越快.
A选项第一次选择21将会换到17的位置,第一次变换后变为：
17,9,5,21,25,23,30
再进行一次变换,就已经排好序了
C选项同理,第一次选择将21换到30的位置,变换后变为：
5,9,17,21,25,23,30
A、C两选项第一次选择的比较次数和交换次数都相同,所以时间就看第二轮了
(17,9,5)和(5,9,17)谁快?应该是（5,9,17）快一步,因为（17,9,5）还要交换一步变成（5,9,17）,然后再剩下（5,9）,而（5,9,17）第一步不变化,然后剩下（9,17）,两个剩下的时间（即5,9和9,17再比较一次且都是已排序的）肯定都是一样的.
所以时间就差在需要交换的一步上：
（17,9,5）->(5,9,17)->(5,9)+(17)第一步需要3步比较和一次交换；
（5,9,17）->(5,9,17)->(5)+(9,17)第一步需要3步比较无需交换；
所以选C
看了你的图,我补充下：
答案对A的解释在第一步上有误啊,怎么会变成（9,17,5,21,23,25,30）呢?
A选项第一次查找将会交换25和9的位置,9只能出现在第二位的.然后再交换21和17,只会变成17,9,5,21,25,23,30啊,答案有误!
另外对于其他答案,我认为,对于算法不仅仅是交换,比较也是要算时间的,快速排序在已经排序好的数列上花的时间是最大的,平方级
但是这些在规模较小的情况下因素太多了~

23 13 51 57 26 66 81 69 76
先把66用临时变量存储起来,这样66所在的位置便空了出来,然后从右边找,发现23小于66,于是把23放在空出的位置,23原来所在位置空出,然后从左边开始找,找到比66大的数放在空出的位置,以此类推..知道两边找的位置重合 ,最后再把66放回空位,一次划分完成

1，2，3，4，5，6，7；
三次，最好 就是第一次取到4，以4为列子，就是最好取到的数是位于中间大于左面3个，小于右边3个；第一次比较比4小的放左边，大的右边。
然后第二次；以同样的方法再取，取到2，6最好啦；
比较左右各一次；共2次。（这里我把左右比较用一个循环控制比较算做一次）
n=15，就是俩个n=7就是3次了
快排也有点像二路归并：从一个无序的序列中随机取出一个值q做为支点,然后把大于q的放到一边，小于q的放到q的另一边,然后再以q为分界点，分别对q的两边
进行排序（快排时直接再对q两边重新取支点，整理，再取支点，...直到支点两旁都有序。也就是支点两旁只有一个数时）

取8为标兵
4,3,6,1,8,10,18,12,9,18
快排的原理就是每次取一个标兵,把比它小的放前面,比它大的放后面

第一次 38,13,27,49,65,97,76
第二次 13,27,38,49,65,97,76
第三次 13,27,38,49,65,97,76
第四次 13,27,38,49,65,76,97

每一趟确定一个值的位置,比它大的在右边,小的左边,然后分成两个数组接着排

(01,14,19,23,68,84,27)

快速排序的时间复杂度
最坏为n*(n-1)/2
最好为n*logn
不同的结果和用于划分的key大小有关：
最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候；
最好情况是每次划分过程产生的区间大小都为n/2 .
数据结构里说的很清楚.百度百科里也有说明的.

此题条件不明,无解
快排分很多种,就每种的实现来说也有十几种.
就最朴素的算法来说,设有n个元素,那么次数就是nlogn,你这种可能是d吧,本来就有序,所以不用进行移动,直接3次递归出解