计算机问题求解一论题2-10 排序与选择 2018年05月02日
计算机问题求解 – 论题2-10 - 排序与选择 2018年05月02日
问题1： 你能否利用下图解释快速排 序的基本思想？ [first灲 [splitPoint]:pivot [last] 0000O0100000000 for any element in this for any element in this segment,the key small large segment,the key is not less than pivot. is less than pivot. To be sorted recursively
[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 if p<r 2 g PARTITION(A,p,r) 3 QUICKSORT(A,p,q-1) 4 QUICKSORT(A,g+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 if p<r 2 g PARTITION(A,p,r) 3 QUICKSORT(A,p,q-1) 4 QUICKSORT(A.g+1.r) To sort an entire array A,the initial call is QUICKSORT(A,1.A.length) 问题4： 这个递归算法的时间性能递归式是什么？