快速排序正确性证明

//伪代码描述快排
QUICKSORT(A, p,r)
if(p < r) q = PATITION(A, p, r) QUICKSORT(A, p, q - 1) QUICKSORT(A, q + 1, r) PATITION()函数： 参数含义：A是数组地址，p是数组左边的下标，r是右边的下标。 作用是随机选pivot，小于等于pivot的数放左边，大于pivot的数放右边，返回pivot的下标。 证明快速排序的正确性： 1、对于元素个数为1的数组（即r-p=1），QUICKSORT()后数组有序。 2、假设对于元素个数小于等于n(其中n>=1)的数组（即r-p=n），QUICKSORT()后数组有序。下面要证明对于元素个数为n+1的数组，QUICKSORT()后数组有序。 r-p = n+1>0,即p

快速排序正确性证明最先出现在Python成神之路。