问答题
5. 如何进行快速排序
【正确答案】快速排序是一种非常高效的排序算法，它采用“分而治之”的思想，把大的拆分为小的，小的再拆分为更小的。其原理是：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前部分的所有记录均比后部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。
具体算法步骤如下：
(1)分解：将输入的序列array[m,…,n]划分成两个非空子序列array [m,…,k]和array[k+1,…,n]，使array[m,…,k]中任一元素的值不大于array [k+1,…,n]中任一元素的值。
(2)递归求解：通过递归调用快速排序算法分别对array[m,…,k]和array [k+1,…,n]进行排序。
(3)合并：由于对分解出的两个子序列的排序是就地进行的，所以在array[m,…,k]和array [k+1,…,n]都排好序后，不需要执行任何计算，array[m,…,n]就已排好序。
以数组{49，38，65，97，76，13，27，49}为例(假设要求为升序排列)。
第一次排序过程如下：
初始化关键字[49 38 65 97 76 13 27 49]
第一次交换后：[27 38 65 97 76 13 49 49]
第二次交换后：[27 38 49 97 76 13 65 49]
j向左扫描，位置不变，第三次交换后：[27 38 13 97 76 49 65 49]
i向右扫描，位置不变，第四次交换后：[27 38 13 49 76 97 65 49]
j向左扫描[27 38 13 49 76 97 65 49]
整个排序过程如下：
初始化关键字[49 38 65 97 76 13 27 49]
一次排序之后：[27 38 13] 49 [76 97 65 49]
二次排序之后：[13] 27 [38] 49[49 65]76 [97]
三次排序之后：13 27 38 49 49[65]76 97
最后的排序结果：13 27 38 49 49 65 76 97
示例代码如下：
def quick_sort(lists, left, right):
#快速排序
if left＞=right:
return lists
key=lists[left]
low=left
high=right
while left＜right:
while left＜right and lists[right]＞=key:
right-=1
lists[left]=lists[right]
while left＜right and lists[left]＜=key:
left+=1
lists[right]=lists[left]
lists[right]=key
quick_sort(lists, low, left-1)
quick_sort(lists,left+1,high)
return lists
if __name__=='__main__":
lists=[3,4,2,8,9,5,1]
print '排序前序列为:',
for i in(lists):
print i,
print '\n排序后结果为:',
for i in (quick_sort(lists,0,len(lists)-1)):
print i,
程序的运行结果为：
排序前序列为：3 4 2 8 9 5 1
排序后结果为：1 2 3 4 5 8 9
当初始的序列整体或局部有序时，快速排序的性能将会下降，此时快速排序将退化为冒泡排序。
快速排序的相关特点如下：
(1)最坏时间复杂度
最坏情况是指每次区间划分的结果都是基准关键字的左边(或右边)序列为空，而另一边的区间中的记录项仅比排序前少了一项，即选择的基准关键字是待排序的所有记录中最小或者最大的。例如，若选取第一个记录为基准关键字，当初始序列按递增顺序排列时，每次选择的基准关键字都是所有记录中的最小者，这时记录与基准关键字的比较次数会增多。因此，在这种情况下，需要进行(n-1)次区间划分。对于第k(0＜k＜n)次区间划分，划分前的序列长度为(n-k+1)，需要进行(n-k)次记录的比较。当k从1～(n-1)时，进行的比较次数总共为n(n-1)/2，所以在最坏情况下快速排序的时间复杂度为O(n2)。
(2)最好时间复杂度
最好情况是指每次区间划分的结果都是基准关键字左右两边的序列长度相等或者相差为1，即选择的基准关键字为待排序的记录中的中间值。此时，进行的比较次数总共为nlogn，所以在最好情况下快速排序的时间复杂度为O(nlogn)。
(3)平均时间复杂度
快速排序的平均时间复杂度为O(nlogn)。虽然快速排序在最坏情况下的时间复杂度为O(n2)，但是在所有平均时间复杂度为O(nlogn)的算法中，快速排序的平均性能是最好的。
(4)空间复杂度
快速排序的过程中需要一个栈空间来实现递归。当每次对区间的划分都比较均匀时(即最好情况)，递归树的最大深度为
具体算法步骤如下：
(1)分解：将输入的序列array[m,…,n]划分成两个非空子序列array [m,…,k]和array[k+1,…,n]，使array[m,…,k]中任一元素的值不大于array [k+1,…,n]中任一元素的值。
(2)递归求解：通过递归调用快速排序算法分别对array[m,…,k]和array [k+1,…,n]进行排序。
(3)合并：由于对分解出的两个子序列的排序是就地进行的，所以在array[m,…,k]和array [k+1,…,n]都排好序后，不需要执行任何计算，array[m,…,n]就已排好序。
以数组{49，38，65，97，76，13，27，49}为例(假设要求为升序排列)。
第一次排序过程如下：
初始化关键字[49 38 65 97 76 13 27 49]
第一次交换后：[27 38 65 97 76 13 49 49]
第二次交换后：[27 38 49 97 76 13 65 49]
j向左扫描，位置不变，第三次交换后：[27 38 13 97 76 49 65 49]
i向右扫描，位置不变，第四次交换后：[27 38 13 49 76 97 65 49]
j向左扫描[27 38 13 49 76 97 65 49]
整个排序过程如下：
初始化关键字[49 38 65 97 76 13 27 49]
一次排序之后：[27 38 13] 49 [76 97 65 49]
二次排序之后：[13] 27 [38] 49[49 65]76 [97]
三次排序之后：13 27 38 49 49[65]76 97
最后的排序结果：13 27 38 49 49 65 76 97
示例代码如下：
def quick_sort(lists, left, right):
#快速排序
if left＞=right:
return lists
key=lists[left]
low=left
high=right
while left＜right:
while left＜right and lists[right]＞=key:
right-=1
lists[left]=lists[right]
while left＜right and lists[left]＜=key:
left+=1
lists[right]=lists[left]
lists[right]=key
quick_sort(lists, low, left-1)
quick_sort(lists,left+1,high)
return lists
if __name__=='__main__":
lists=[3,4,2,8,9,5,1]
print '排序前序列为:',
for i in(lists):
print i,
print '\n排序后结果为:',
for i in (quick_sort(lists,0,len(lists)-1)):
print i,
程序的运行结果为：
排序前序列为：3 4 2 8 9 5 1
排序后结果为：1 2 3 4 5 8 9
当初始的序列整体或局部有序时，快速排序的性能将会下降，此时快速排序将退化为冒泡排序。
快速排序的相关特点如下：
(1)最坏时间复杂度
最坏情况是指每次区间划分的结果都是基准关键字的左边(或右边)序列为空，而另一边的区间中的记录项仅比排序前少了一项，即选择的基准关键字是待排序的所有记录中最小或者最大的。例如，若选取第一个记录为基准关键字，当初始序列按递增顺序排列时，每次选择的基准关键字都是所有记录中的最小者，这时记录与基准关键字的比较次数会增多。因此，在这种情况下，需要进行(n-1)次区间划分。对于第k(0＜k＜n)次区间划分，划分前的序列长度为(n-k+1)，需要进行(n-k)次记录的比较。当k从1～(n-1)时，进行的比较次数总共为n(n-1)/2，所以在最坏情况下快速排序的时间复杂度为O(n2)。
(2)最好时间复杂度
最好情况是指每次区间划分的结果都是基准关键字左右两边的序列长度相等或者相差为1，即选择的基准关键字为待排序的记录中的中间值。此时，进行的比较次数总共为nlogn，所以在最好情况下快速排序的时间复杂度为O(nlogn)。
(3)平均时间复杂度
快速排序的平均时间复杂度为O(nlogn)。虽然快速排序在最坏情况下的时间复杂度为O(n2)，但是在所有平均时间复杂度为O(nlogn)的算法中，快速排序的平均性能是最好的。
(4)空间复杂度
快速排序的过程中需要一个栈空间来实现递归。当每次对区间的划分都比较均匀时(即最好情况)，递归树的最大深度为
【答案解析】[考点] 如何进行快速排序