算法导论第七章-快速排序

7.1-1 参照图7-1的方法，说明PARTITION在数组A=<13,19,9,5,12,8,7,4,21,2,6,11>上的操作过程。
答:golang实现：

// Partition 分解重排步骤
func Partition(a QuickSortInterface, p int, r int) int {
    x := a.Get(r)
    i := p - 1
    for j := p; j < r; j++ {
        if a.Get(j) < x {
            i++
            a.Swap(i, j)
        }
    }
    a.Swap(i+1, r)
    return i + 1
}

结果为:

[9 5 8 7 4 2 6 11 21 13 19 12]

7.1-2 当数组A[p..r]中所有元素的值都相同时，PARTITION返回的q值是什么？修改PARTITION，使得当数组A[p..r]中所有元素的值都相同时，q=[(p+r)/2]
答：PARTITION返回的值为r;把第四行代码改为

if a.Get(j) < x  && j%2 == p%2

7.1-3 请简要地证明：在规模为n的子数组上，PARTITION的时间复杂度为O(n)
答：在for循环中，对于子数组的每个元素，都会做一次判断，在循环外的操作时间代价都是常数级的，所以复杂度为O(n)。

7.1-4 如何修改QUICKSORT，使得它能够以非递增进行排序？
答：将a.Get(j) < x判断条件改为a.Get(j) > x即可。