Hoare划分的正确性
题目：本章中给出的PARTITION算法并不是其最初的版本。下面给出的是最初由C.A.R.Hoare设计的划分算法。
HOARE-PARTITION(A,p,r):
1 x <- A[p] 2 i <- p-1 3 j <- r+1 4 while TRUE 5 do repeat j <- j-1 6 until A[j] <= x 7 repeat i <- i+1 8 until A[i] >= x 9 if iA[j]11 else return j
问题：
a)说明HOARE-PARTITION在数组A={13,19,9,5,12,8,7,4,11,2,6,21}上的运行过程，并说明4~11行中while循环的每一轮迭代后，数组中各个元素的值和辅助值的情况。
下面3个问题要求读者具体地证明过程HOARE-PARTITION是正确地。假设子数组至少A[p,r]包括两个元素，证明以下几点都是正确的。
b)下标i和j满足这样的特点：即我们从不会访问数组A的，在子数组A[p,r]之外的元素。
c)当HOARE-PARTITION结束时，它返回的j值满足p<=j<r
d)当过程HOARE-PARTITION结束时，A[p..r]中的每个元素都小于或等于A[j+1,r]中的每一个元素。
在7.1节给出PARTITION过程中，将主元值（原来位于A[r]中）与围绕它划分形成的两个部分分割了开来。与此相反，HOARE-PARTITION过程则总是将主元值（原先是A[p]中的）放入两个划分A[p..j]和A[j+1...r]的某一个之中。因为p<=j<r，故这种划分总是非平凡的。
e)利用HOARE-PARTITION，重写QUICKSORT过程。
答案
a)
b)
A[p....r] ,x=A[p], j=r+1 , i=p-1；
在第一轮循环中：
由于 repeat j <- j-1 until A[j]<=x，所以j的最小值是p。
由于 repeat i<i+1 until A[i]>=x ，所以第一轮循环中，i==p
假设第一轮循环中，i跟j的repeat都走完，j==p,i==p，就满足 return j；
假设在第一轮循环中， p<j<r，那么交换i，j，进入第二轮循环。假设这时j=j1，这时A[j1]<=x ；
交换i,j后，A[p] =A[j1] <= x，同样 j永远不会超过p
同理，A[j1] = A[p] == x，i永远不会超过j1
c)
由于 repeat j <- j-1 until A[j]<=x，而且 A[p] = x，所以j的最小值是p。 p<=j
d)
e)
1 public class HoareQuickSort { 2 3 public static void quickSort(int[] arr) { 4 quickSort(arr, 0, arr.length - 1); 5 } 6 7 private static void quickSort(int[] arr, int l, int r) { 8 if (l < r) { 9 int mid = hoarePartition2(arr, l, r);10 quickSort(arr, l, mid );11 quickSort(arr, mid + 1, r);12 }13 }14 15 private static int hoarePartition2(int[] arr, int l, int r) {16 int e = arr[l];17 int i = l - 1, j = r + 1;18 while (true) {19 do {20 j--;21 } while (arr[j] > e);22 23 do {24 i++;25 } while (arr[i] < e);26 27 if (i < j) {28 swap(arr, i, j);29 } else {30 return j;31 }32 }33 }34 35 private static void swap(int[] arr, int i, int j) {36 int e = arr[i];37 arr[i] = arr[j];38 arr[j] = e;39 }40 41 public static void main(String[] args) {42 int arr[] = {13,19,9,5,12,8,7,4,11,2,6,21};43 HoareQuickSort.quickSort(arr);44 System.out.println(Arrays.toString(arr));45 }