快速排序算法
下面是快速排序的伪代码，请填补其中的空缺。伪代码中的主要变量说明如下。
A：待排序数组
p, r：数组元素下标，从p到r
q：划分的位置
x：枢轴元素
i：整型变量，用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值
j：循环控制变量，表示数组元素下标
QUICKSORT(A, p, r){
if (p < r){
q = PARTITION(A,p,r) ;
QUICKSORT(A, p, q-1);
QUICKSORT(A, q+1, r);
}
}
PARTITION(A, p, r){
x = A[r]; i = p - 1;
for (j = p ; j ≤ r - 1; j++){
if (A[j] ≤ x){
i = i + 1 ;
交换A[i] 和 A[j]
}
}
交换 (1) 和 （2）
return （3）
}
求解，为什么x = A[r]; i = p - 1;中i=p-1的呢？
为什么(1)和（2）的答案是A[i+1]和A[r]的呢?
[解决办法]
1. 当从数组左端向右端循环时，如果遇到的值小于x，则i=i+1后一直指向目前循环过的区间中最后一个小于x的坐标，此时i=j，则"交换A[i]和A[j]"等于没做。当遇到首个大于x的值时，不做if快内部分，继续循环时，当再次遇到小于x的值时，则进入if块，执行i=i+1,此时i指向从左到右的首个大于x的坐标，再执行"交换A[i]和A[j]"则，A[j]（小于x的值）和A[i]（首个大于x的值）交换位置，即保持小于x的值都在数组左边部分。因此，在循环中，i的值始终指向数组从左到右最后一个小于x的值的位置，再遇到需要交换的情况时，通过i=i+1即可获取首个大于x的值的坐标。
2. 根据1.中的说法，i始终指向数组从左到右最后一个小于x的值的位置，则i+1始终指向数组从左到右首个大于x的值的坐标。此时交换A[i+1]和A[r]，则保证x值的左边都是小于其的值，x的右边都是大于其的值
