计算机问题求解一论题2-10 排序与选择 2016年4月21日
计算机问题求解 – 论题2-10 - 排序与选择 2016年4月21日
问题1： 你能否利用下图解释快速排 序的基本思想？ [splitPoint]:pivot [first灲 [last灯 0000O000000000 for any element in for any element in this Small large this segment,the key segment,the key is not is less than pivot. To be sorted recursively less than pivot
[first] [last] for any element in this segment, the key is less than pivot. for any element in this segment, the key is not less than pivot
QUICKSORT(A,p,r) 1 ifp<r 3 g PARTITION(A,p,r) 3 QUICKSORT(A,p,q-1) 4 QUICKSORT(A,q 1,r) To sort an entire array A,the initial call is QUICKSORT(A,1,A.length) 问题2： 都是用divide-and conquer策略，这与 Mergesort有什么不同？
关键是Partition Partition过程的核心是一个循环，执行rp次。 在第飞+1次循环开始前，格局如下： k ≤x >x unrestricted 问题3： 你能否借助此图，解释利用循环不变 式如何证明这个过程的正确性？
关键是Partition Partition过程的核心是一个循环，执行r-p次。 在第k+1次循环开始前，格局如下： k
QUICKSORT(A,p,r) 1 ifp<r 2 g PARTITION(A,p,r) 3 QUICKSORT(A,p,q-1) 4 QUICKSORT(A,q+1,r) To sort an entire array A,the initial call is QUICKSORT(A,1,A.length) 问题4： 这个递归算法的时间性能递归式是什么？